text: Contents 1. Introduction Photomultiplier tubes (PMTs) are currently one of the most widely used photodetectors due to their large collection area and high gain. In radiation detectors using xenon as an active medium, vacuum ultraviolet (VUV)-sensitive PMTs are used to detect the 175 nm xenon scintillation light [1, 2]. For photon-counting and calorimetry applications, the single-photon response of PMTs must be well characterized to understand the overall detector behavior. The most important contribution to the PMT photon detection efﬁciency is the quantum efﬁciency (QE), which is deﬁned as the ratio of electrons produced in the photocathode (referred to as photoelectrons, or phe) divided by the number of incident photons [3]. QE is often incorrectly treated as the probability of an incident photon to produce a photoelectron, but if more than one photoelectron is produced by a single photon, this equivalence is no longer valid. QE is a function of the incoming photon wavelength due to a number of competing factors, including the PMT window transmission probability and the photon absorption length in the photocathode. QE is ∼ typically limited to 30% at 400 nm, with decreasing sensitivity at lower wavelengths. For PMTs specially designed to be sensitive to the VUV band, the QE shows a marked enhancement below 200 nm and above the transmission cutoff of the synthetic silica window at 160–170 nm[1, 2, 4]. The present work was prompted by observed differences in the PMT pulse height and area spectra for single photons of xenon scintillation light and blue LED light in LUX[5, 6]. Speciﬁcally, a feature like the one discussed in Section of this document, led us to start investigating not only the efﬁciency, but also the shape of the single photon response of LUX PMTs as a function of incoming wavelength. The process of emitting two photoelectrons from the photocathode from a single incoming photon, referred to as double photoelectron emission (DPE), has been studied before in the context of the photoelectric effect on metallic surfaces [7, 8, 9]. PMT photocathodes are expected to exhibit a similar behavior, provided that the incoming photon is sufﬁciently energetic (greater than twice the photocathode work function). We have found in this study that for wavelengths lower ∼ than 250 nm, the DPE probability is non-negligible for all three VUV-sensitive Hamamatsu R11410 (3-inch circular photocathode), Hamamatsu R8778 (2-inch circular) and R8520 (1-inch square). The R8520 PMT was used in the XENON10, XENON100, Panda-X (top array) and LZ (xenon veto region) experiments. The R8778 was utilized in the LUX experiment, while a variant (R10789 hexagonal head) was used in the XMASS experiment. Lastly, the larger R11410 has been used in the Panda-X experiment (bottom array) and will be used by next-generation dark matter experiments, such as LZ, XENON1T/NT, and RED, among others. – 1 – ##LTLine## ##LTLine##

text: Contents

text: Introduction

text: Photomultiplier

text: tubes

text: (PMTs)

text: are

text: currently

text: one

text: of

text: the

text: most

text: widely

text: used

text: photodetectors

text: due

text: to

text: their

text: large

text: collection

text: area

text: and

text: high

text: gain.

text: In

text: radiation

text: detectors

text: using

text: xenon

text: as

text: an

text: active

text: medium,

text: vacuum

text: ultraviolet

text: (VUV)-sensitive

text: PMTs

text: are

text: used

text: to

text: detect

text: the

text: nm

text: xenon

text: scintillation

text: light

text: For

text: photon-counting

text: and

text: calorimetry

text: applications,

text: the

text: single-photon

text: response

text: of

text: PMTs

text: must

text: be

text: well

text: characterized

text: to

text: understand

text: the

text: overall

text: detector

text: behavior.

text: The

text: most

text: important

text: contribution

text: to

text: the

text: PMT

text: photon

text: detection

text: efﬁciency

text: is

text: the

text: quantum

text: efﬁciency

text: (QE),

text: which

text: is

text: deﬁned

text: as

text: the

text: ratio

text: of

text: electrons

text: produced

text: in

text: the

text: photocathode

text: (referred

text: to

text: as

text: photoelectrons,

text: or

text: phe)

text: divided

text: by

text: the

text: number

text: of

text: incident

text: photons

text: QE

text: is

text: often

text: incorrectly

text: treated

text: as

text: the

text: probability

text: of

text: an

text: incident

text: photon

text: to

text: produce

text: a

text: photoelectron,

text: but

text: if

text: more

text: than

text: one

text: photoelectron

text: is

text: produced

text: by

text: a

text: single

text: photon,

text: this

text: equivalence

text: is

text: no

text: longer

text: valid.

text: QE

text: is

text: a

text: function

text: of

text: the

text: incoming

text: photon

text: wavelength

text: due

text: to

text: a

text: number

text: of

text: competing

text: factors,

text: including

text: the

text: PMT

text: window

text: transmission

text: probability

text: and

text: the

text: photon

text: absorption

text: length

text: in

text: the

text: photocathode.

text: QE

text: is

text: typically

text: limited

text: to

text: at

text: nm,

text: with

text: decreasing

text: sensitivity

text: at

text: lower

text: wavelengths.

text: For

text: PMTs

text: specially

text: designed

text: to

text: be

text: sensitive

text: to

text: the

text: VUV

text: band,

text: the

text: QE

text: shows

text: a

text: marked

text: enhancement

text: below

text: nm

text: and

text: above

text: the

text: transmission

text: cutoff

text: of

text: the

text: synthetic

text: silica

text: window

text: at

text: The

text: present

text: work

text: was

text: prompted

text: by

text: observed

text: differences

text: in

text: the

text: PMT

text: pulse

text: height

text: and

text: area

text: spectra

text: for

text: single

text: photons

text: of

text: xenon

text: scintillation

text: light

text: and

text: blue

text: LED

text: light

text: in

text: Speciﬁcally,

text: a

text: feature

text: like

text: the

text: one

text: discussed

text: in

text: Section

text: of

text: this

text: document,

text: led

text: us

text: to

text: start

text: investigating

text: not

text: only

text: the

text: efﬁciency,

text: but

text: also

text: the

text: shape

text: of

text: the

text: single

text: photon

text: response

text: of

text: LUX

text: PMTs

text: as

text: a

text: function

text: of

text: incoming

text: wavelength.

text: The

text: process

text: of

text: emitting

text: two

text: photoelectrons

text: from

text: the

text: photocathode

text: from

text: a

text: single

text: incoming

text: photon,

text: referred

text: to

text: as

text: double

text: photoelectron

text: emission

text: (DPE),

text: has

text: been

text: studied

text: before

text: in

text: the

text: context

text: of

text: the

text: photoelectric

text: effect

text: on

text: metallic

text: surfaces

text: PMT

text: photocathodes

text: are

text: expected

text: to

text: exhibit

text: a

text: similar

text: behavior,

text: provided

text: that

text: the

text: incoming

text: photon

text: is

text: sufﬁciently

text: energetic

text: (greater

text: than

text: twice

text: the

text: photocathode

text: work

text: function).

text: We

text: have

text: found

text: in

text: this

text: study

text: that

text: for

text: wavelengths

text: lower

text: than

text: nm,

text: the

text: DPE

text: probability

text: is

text: non-negligible

text: for

text: all

text: three

text: VUV-sensitive

text: Hamamatsu

text: circular

text: photocathode),

text: Hamamatsu

text: circular)

text: and

text: square).

text: The

text: PMT

text: was

text: used

text: in

text: the

text: Panda-X

text: (top

text: array)

text: and

text: LZ

text: (xenon

text: veto

text: region)

text: experiments.

text: The

text: was

text: utilized

text: in

text: the

text: LUX

text: experiment,

text: while

text: a

text: variant

text: hexagonal

text: head)

text: was

text: used

text: in

text: the

text: XMASS

text: experiment.

text: Lastly,

text: the

text: larger

text: has

text: been

text: used

text: in

text: the

text: Panda-X

text: experiment

text: (bottom

text: array)

text: and

text: will

text: be

text: used

text: by

text: next-generation

text: dark

text: matter

text: experiments,

text: such

text: as

text: LZ,

text: and

text: RED,

text: among

text: others.

text: ##LTLine##

text: ##LTLine##


text: if there are two paths using two corners each, and two sides of the rectangle, from the remaining ﬁve paths, there are three of them that are intervals contained in the same side of the rectangle, a contradiction. This completes the proof. (cid:50) Proposition 13 The thick spider S is not a B -EPG graph. 7 1 Proof. By contradiction, suppose that S admits a B -EPG representation. Let us P 7 1 consider the path corresponding to a vertex c of the clique and the paths corresponding c P to its 6 neighbors in the stable set S. The path has edges on at most two lines (one row c and one column) of the grid. Thus, it intersects at least 3 paths corresponding to neighbors in S on a same line x. Without loss of generality, we may assume that x corresponds to a row of the grid. Consider now the 3 intervals on row x belonging to the 3 paths mentioned above. Since the corresponding vertices are pairwise non adjacent, they admit some order I I I on row x, say , , , corresponding to vertices s , s , s , respectively. Having at most i j k i j k one bend each, the paths corresponding to s and s do not have edges in a common column i k (and they do not have edges in a row diﬀerent from x, or more than one interval on x). P So there is no way for the path corresponding to the vertex c of the clique that is not cj I j adjacent to s of avoiding the interval while intersecting the paths corresponding to s j j i and s using only one bend. (cid:50) k Acknowledgement. We would like to thank Marty Golumbic whose lectures about EPG graphs have motivated this research, and to Jayme Szwarcﬁter, who posed some of these questions at LAGOS’09. References [1] L. Alco´n, F. Bonomo, G. Dura´n, M. Gutierrez, P. Mazzoleni, B. Ries, and M. Valencia- Pabon. On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Electronic Notes in Discrete Mathematics. To appear. [2] A. Asinowski and B. Ries. Some properties of edge intersection graphs of single-bend paths on a grid. Discrete Mathematics, 312:427–440, 2012. [3] A. Asinowski and A. Suk. Edge intersection graphs of systems of paths on a grid with a bounded number of bends. Discrete Applied Mathematics, 157:3174–3180, 2009. [4] T. Biedl and M. Stern. On edge intersection graphs of k-bend paths in grids. Discrete Mathematics & Theoretical Computer Science, 12(1):1–12, 2010. [5] J.A. Bondy and U.S.R. Murty. Graph Theory. Springer, New York, 2007. [6] Y. Cao, L.N. Grippo, and M.D. Safe. Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection. arXiv:1405.0329v1 [cs.DM], May 2014. 13

text: if

label: paragraph

text: there

text: are

text: two

text: paths

text: using

text: two

text: corners

text: each,

text: and

text: two

text: sides

text: of

text: the

text: rectangle,

text: from

text: the

text: remaining

text: ﬁve

text: paths,

text: there

text: are

text: three

text: of

text: them

text: that

text: are

text: intervals

text: contained

text: in

text: the

text: same

text: side

text: of

text: the

text: rectangle,

text: a

text: contradiction.

text: This

text: completes

text: the

text: proof.

text: Proposition

text: The

text: thick

text: spider

text: S

text: is

text: not

text: a

text: B

text: -EPG

text: graph.

text: Proof.

text: By

text: contradiction,

text: suppose

text: that

text: S

text: admits

text: a

text: B

text: -EPG

text: representation.

text: Let

text: us

text: P

text: consider

text: the

text: path

text: corresponding

text: to

text: a

text: vertex

text: c

text: of

text: the

text: clique

text: and

text: the

text: paths

text: corresponding

text: c

text: P

text: to

text: its

text: neighbors

text: in

text: the

text: stable

text: set

text: S.

text: The

text: path

text: has

text: edges

text: on

text: at

text: most

text: two

text: lines

text: (one

text: row

text: c

text: and

text: one

text: column)

text: of

text: the

text: grid.

text: Thus,

text: it

text: intersects

text: at

text: least

text: paths

text: corresponding

text: to

text: neighbors

text: in

text: S

text: on

text: a

text: same

text: line

text: x.

text: Without

text: loss

text: of

text: generality,

text: we

text: may

text: assume

text: that

text: x

text: corresponds

text: to

text: a

text: row

text: of

text: the

text: grid.

text: Consider

text: now

text: the

text: intervals

text: on

text: row

text: x

text: belonging

text: to

text: the

text: paths

text: mentioned

text: above.

text: Since

text: the

text: corresponding

text: vertices

text: are

text: pairwise

text: non

text: adjacent,

text: they

text: admit

text: some

text: order

text: I

text: I

text: I

text: on

text: row

text: x,

text: say

text: corresponding

text: to

text: vertices

text: s

text: s

text: s

text: respectively.

text: Having

text: at

text: most

text: i

text: j

text: k

text: i

text: j

text: k

text: one

text: bend

text: each,

text: the

text: paths

text: corresponding

text: to

text: s

text: and

text: s

text: do

text: not

text: have

text: edges

text: in

text: a

text: common

text: column

text: i

text: k

text: (and

text: they

text: do

text: not

text: have

text: edges

text: in

text: a

text: row

text: diﬀerent

text: from

text: x,

text: or

text: more

text: than

text: one

text: interval

text: on

text: x).

text: P

text: So

text: there

text: is

text: no

text: way

text: for

text: the

text: path

text: corresponding

text: to

text: the

text: vertex

text: c

text: of

text: the

text: clique

text: that

text: is

text: not

text: cj

text: I

text: j

text: adjacent

text: to

text: s

text: of

text: avoiding

text: the

text: interval

text: while

text: intersecting

text: the

text: paths

text: corresponding

text: to

text: s

text: j

text: j

text: i

text: and

text: s

text: using

text: only

text: one

text: bend.

text: k

text: Acknowledgement.

text: We

text: would

text: like

text: to

text: thank

text: Marty

text: Golumbic

text: whose

text: lectures

text: about

text: EPG

text: graphs

text: have

text: motivated

text: this

text: research,

text: and

text: to

text: Jayme

text: Szwarcﬁter,

text: who

text: posed

text: some

text: of

text: these

text: questions

text: at

text: References

text: L.

text: Alco´n,

text: F.

text: Bonomo,

text: G.

text: Dura´n,

text: M.

text: Gutierrez,

text: P.

text: Mazzoleni,

text: B.

text: Ries,

text: and

text: M.

text: Valencia-

text: Pabon.

text: On

text: the

text: bend

text: number

text: of

text: circular-arc

text: graphs

text: as

text: edge

text: intersection

text: graphs

text: of

text: paths

text: on

text: a

text: grid.

text: Electronic

text: Notes

text: in

text: Discrete

text: Mathematics.

text: To

text: appear.

text: A.

text: Asinowski

text: and

text: B.

text: Ries.

text: Some

text: properties

text: of

text: edge

text: intersection

text: graphs

text: of

text: single-bend

text: paths

text: on

text: a

text: grid.

text: Discrete

text: Mathematics,

text: A.

text: Asinowski

text: and

text: A.

text: Suk.

text: Edge

text: intersection

text: graphs

text: of

text: systems

text: of

text: paths

text: on

text: a

text: grid

text: with

text: a

text: bounded

text: number

text: of

text: bends.

text: Discrete

text: Applied

text: Mathematics,

text: T.

text: Biedl

text: and

text: M.

text: Stern.

text: On

text: edge

text: intersection

text: graphs

text: of

text: k-bend

text: paths

text: in

text: grids.

text: Discrete

text: Mathematics

text: Theoretical

text: Computer

text: Science,

text: J.A.

text: Bondy

text: and

text: U.S.R.

text: Murty.

text: Graph

text: Theory.

text: Springer,

text: New

text: York,

text: Y.

text: Cao,

text: L.N.

text: Grippo,

text: and

text: M.D.

text: Safe.

text: Forbidden

text: induced

text: subgraphs

text: of

text: normal

text: Helly

text: circular-arc

text: graphs:

text: Characterization

text: and

text: detection.

text: [cs.DM],

text: May


text: Proposition 3 The thick spider S is not in B -EPR. 13 3 Proof. By contradiction, suppose that S admits a B -EPR representation. Clearly, 13 3 at most four of the paths corresponding to vertices in the stable set contain a corner of the rectangle, since they are pairwise non adjacent. So, from the remaining 9 paths, repre- senting vertices in the stable set, at least three of them are intervals completely contained P P P in one side of the rectangle. Let us denote these paths in order by , , , representing i j k P vertices s , s , s . The path corresponding to vertex c in the clique has to intersect , P i j kP j i and avoiding , so it necessarily needs four bends, a contradiction. (cid:50) k j We will now consider normal circular-arc graphs and show that their bend number with respect to EPR representations is equal to 2. Theorem 4 Every NCA graph is a B -EPR graph. 2 A C Proof. Let ( , ) be a NCA model of a circular-arc graph. Without loss of generality, we may assume that the endpoints of the arcs are pairwise diﬀerent. Let p be a point of C A that is not the endpoint of an arc of . Since the model is normal, the union of the A C C arcs of that contain p does not cover . Thus, there exists a point q in that is not A A the endpoint of an arc of and is not contained in the union of the arcs of containing p. We can then embed our model on a rectangle of the grid in the following way (arcs C will correspond to paths and will correspond to the rectangle): two consecutive corners correspond to point p of the circle and the remaining two corners correspond to point q of A the circle. In this way, since no arc of contains both p and q, paths corresponding to arcs containing either p or q have two bends, while paths corresponding to arcs containing neither p nor q have no bend. (cid:50) In order to show that the bend number of NCA graphs with respect to EPR represen- tations is equal to 2, consider the graph S . S is not in NHCA [6], so in particular it is 3 3 not in B -EPR (see Theorem 11), but it is in B -EPG [12] and it is also in NCA (see for 1 1 example [6]). Let us also show that there exist B -EPR graphs that are not in NCA. 2 \ Proposition 5 The thick spider S is in B -EPR NCA. 6 2 A C Proof. Let ( , ) be a circular-arc model of S . Without loss of generality, we may A A 6 assume that the disjoint arcs , . . . , representing the vertices s , . . . , s in the stable 1 6 1 6 set are in clockwise order. It is not diﬃcult to see that the arcs representing vertices c 1 and c cover the circle. Thus, S is not in NCA. A B -EPR representation of S is given 4 6 2 6 in Figure 2. (cid:50) We will now focus on B -EPR graphs and show that they are NHCA graphs. 1 ⊆ Lemma 6 B -EPR NHCA. 1 6

text: Proposition

text: The

text: thick

text: spider

text: S

text: is

text: not

text: in

text: B

text: -EPR.

text: Proof.

text: By

text: contradiction,

text: suppose

text: that

text: S

text: admits

text: a

text: B

text: -EPR

text: representation.

text: Clearly,

text: at

text: most

text: four

text: of

text: the

text: paths

text: corresponding

text: to

text: vertices

text: in

text: the

text: stable

text: set

text: contain

text: a

text: corner

text: of

text: the

text: rectangle,

text: since

text: they

text: are

text: pairwise

text: non

text: adjacent.

text: So,

text: from

text: the

text: remaining

text: paths,

text: repre-

text: senting

text: vertices

text: in

text: the

text: stable

text: set,

text: at

text: least

text: three

text: of

text: them

text: are

text: intervals

text: completely

text: contained

text: P

text: P

text: P

text: in

text: one

text: side

text: of

text: the

text: rectangle.

text: Let

text: us

text: denote

text: these

text: paths

text: in

text: order

text: by

text: representing

text: i

text: j

text: k

text: P

text: vertices

text: s

text: s

text: s

text: The

text: path

text: corresponding

text: to

text: vertex

text: c

text: in

text: the

text: clique

text: has

text: to

text: intersect

text: P

text: i

text: j

text: kP

text: j

text: i

text: and

text: avoiding

text: so

text: it

text: necessarily

text: needs

text: four

text: bends,

text: a

text: contradiction.

text: k

text: j

text: We

text: will

text: now

text: consider

text: normal

text: circular-arc

text: graphs

text: and

text: show

text: that

text: their

text: bend

text: number

text: with

text: respect

text: to

text: EPR

text: representations

text: is

text: equal

text: to

text: Theorem

text: Every

text: NCA

text: graph

text: is

text: a

text: B

text: -EPR

text: graph.

text: A

text: C

text: Proof.

text: Let

text: be

text: a

text: NCA

text: model

text: of

text: a

text: circular-arc

text: graph.

text: Without

text: loss

text: of

text: generality,

text: we

text: may

text: assume

text: that

text: the

text: endpoints

text: of

text: the

text: arcs

text: are

text: pairwise

text: diﬀerent.

text: Let

text: p

text: be

text: a

text: point

text: of

text: C

text: A

text: that

text: is

text: not

text: the

text: endpoint

text: of

text: an

text: arc

text: of

text: Since

text: the

text: model

text: is

text: normal,

text: the

text: union

text: of

text: the

text: A

text: C

text: C

text: arcs

text: of

text: that

text: contain

text: p

text: does

text: not

text: cover

text: Thus,

text: there

text: exists

text: a

text: point

text: q

text: in

text: that

text: is

text: not

text: A

text: A

text: the

text: endpoint

text: of

text: an

text: arc

text: of

text: and

text: is

text: not

text: contained

text: in

text: the

text: union

text: of

text: the

text: arcs

text: of

text: containing

text: p.

text: We

text: can

text: then

text: embed

text: our

text: model

text: on

text: a

text: rectangle

text: of

text: the

text: grid

text: in

text: the

text: following

text: way

text: (arcs

text: C

text: will

text: correspond

text: to

text: paths

text: and

text: will

text: correspond

text: to

text: the

text: rectangle):

text: two

text: consecutive

text: corners

text: correspond

text: to

text: point

text: p

text: of

text: the

text: circle

text: and

text: the

text: remaining

text: two

text: corners

text: correspond

text: to

text: point

text: q

text: of

text: A

text: the

text: circle.

text: In

text: this

text: way,

text: since

text: no

text: arc

text: of

text: contains

text: both

text: p

text: and

text: q,

text: paths

text: corresponding

text: to

text: arcs

text: containing

text: either

text: p

text: or

text: q

text: have

text: two

text: bends,

text: while

text: paths

text: corresponding

text: to

text: arcs

text: containing

text: neither

text: p

text: nor

text: q

text: have

text: no

text: bend.

text: In

text: order

text: to

text: show

text: that

text: the

text: bend

text: number

text: of

text: NCA

text: graphs

text: with

text: respect

text: to

text: EPR

text: represen-

text: tations

text: is

text: equal

text: to

text: consider

text: the

text: graph

text: S

text: S

text: is

text: not

text: in

text: NHCA

text: so

text: in

text: particular

text: it

text: is

text: not

text: in

text: B

text: -EPR

text: (see

text: Theorem

text: but

text: it

text: is

text: in

text: B

text: -EPG

text: and

text: it

text: is

text: also

text: in

text: NCA

text: (see

text: for

text: example

text: Let

text: us

text: also

text: show

text: that

text: there

text: exist

text: B

text: -EPR

text: graphs

text: that

text: are

text: not

text: in

text: NCA.

text: Proposition

text: The

text: thick

text: spider

text: S

text: is

text: in

text: B

text: -EPR

text: NCA.

text: A

text: C

text: Proof.

text: Let

text: be

text: a

text: circular-arc

text: model

text: of

text: S

text: Without

text: loss

text: of

text: generality,

text: we

text: may

text: A

text: A

text: assume

text: that

text: the

text: disjoint

text: arcs

text: representing

text: the

text: vertices

text: s

text: s

text: in

text: the

text: stable

text: set

text: are

text: in

text: clockwise

text: order.

text: It

text: is

text: not

text: diﬃcult

text: to

text: see

text: that

text: the

text: arcs

text: representing

text: vertices

text: c

text: and

text: c

text: cover

text: the

text: circle.

text: Thus,

text: S

text: is

text: not

text: in

text: NCA.

text: A

text: B

text: -EPR

text: representation

text: of

text: S

text: is

text: given

text: in

text: Figure

text: We

text: will

text: now

text: focus

text: on

text: B

text: -EPR

text: graphs

text: and

text: show

text: that

text: they

text: are

text: NHCA

text: graphs.

text: Lemma

text: B

text: -EPR

text: NHCA.


text: y-axis ρ φ θ 2 θ 1 θ x-axis (0, 0) θ1 φ ρ 2 ρ (x¯, 0) Figure 10. RL path A feasible solution was also obtained by discretizing the angles at each target (32 values) and applying the above transformation procedure. The comparison of the cost of the feasible solution with respect to the optimal Euclidean TSP cost and the lower bound (corresponding to 32 intervals at each target) for the 25 instances is shown in Fig. 12. The average deviation of the cost of the feasible solution from its corresponding lower bound is 5.2%, while the average deviation of the cost of the feasible solution from its corresponding ETSP cost is 29.2%. In one of the instances, we found the cost of the feasible solution from its corresponding lower bound improved by approximately 44%. These results show that the proposed approach can be used to obtain tight lower bounds for the DTSP. A feasible DTSP solution and an optimal solution corresponding to the lower bound for an instance are shown in Fig. 13. 6. Conclusion We provide a systematic procedure to ﬁnd lower bounds for the DTSP. This article provides a new direc- tion for developing approximation algorithms for the DTSP. Currently, the transformation method increases the size of the one-in-a-set TSP by 2 or 3 times, resulting in a large TSP. Computationally, more efﬁcient tools for directly solving the one-in-a-set TSP will be useful in ﬁnding tighter lower and upper bounds for the DTSP. Future work can also address the same problem with multiple vehicles and other precedence constraints. References 3.1.2. Optimizing RLR and LRL paths. [1] S. Rathinam, R. Sengupta, and S. Darbha, “A resource allocation algorithm for multivehicle systems with nonholonomic constraints,” IEEE Transactions Automation Science and Engineering, vol. 4, pp. 98–104, 2007. [2] J. Le Ny, E. Feron, and E. Frazzoli, “On the dubins traveling salesman problem.” IEEE Trans. Automat. Contr., vol. 57, no. 1, pp. 265–270, 2012. [3] P. Chandler and M. Pachter, “Research issues in autonomous control of tactical uavs,” in American Control Conference, 1998. Proceedings of the 1998, vol. 1, Jun 1998, pp. 394–398 vol.1. ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: y-axis

font: default

text: ρ

text: φ

text: θ

text: θ

text: θ

text: x-axis

text: θ1

text: φ

text: ρ

text: ρ

text: (x¯,

text: Figure

font: ARHZQZ+NimbusSanL-Bold

text: RL

label: caption

text: path

text: A

text: feasible

text: solution

text: was

text: also

text: obtained

text: by

text: discretizing

text: the

text: angles

text: at

text: each

text: target

text: values)

text: and

text: applying

text: the

text: above

text: transformation

text: procedure.

text: The

text: comparison

text: of

text: the

text: cost

text: of

text: the

text: feasible

text: solution

text: with

text: respect

text: to

text: the

text: optimal

text: Euclidean

text: TSP

text: cost

text: and

text: the

text: lower

text: bound

text: (corresponding

text: to

text: intervals

text: at

text: each

text: target)

text: for

text: the

text: instances

text: is

text: shown

text: in

text: Fig.

text: The

text: average

text: deviation

text: of

text: the

text: cost

text: of

text: the

text: feasible

text: solution

text: from

text: its

text: corresponding

text: lower

text: bound

text: is

text: while

text: the

text: average

text: deviation

text: of

text: the

text: cost

text: of

text: the

text: feasible

text: solution

text: from

text: its

text: corresponding

text: ETSP

text: cost

text: is

text: In

text: one

text: of

text: the

text: instances,

text: we

text: found

text: the

text: cost

text: of

text: the

text: feasible

text: solution

text: from

text: its

text: corresponding

text: lower

text: bound

text: improved

text: by

text: approximately

text: These

text: results

text: show

text: that

text: the

text: proposed

text: approach

text: can

text: be

text: used

text: to

text: obtain

text: tight

text: lower

text: bounds

text: for

text: the

text: DTSP.

text: A

text: feasible

text: DTSP

text: solution

text: and

text: an

text: optimal

text: solution

text: corresponding

text: to

text: the

text: lower

text: bound

text: for

text: an

text: instance

text: are

text: shown

text: in

text: Fig.

text: Conclusion

text: We

text: provide

text: a

text: systematic

text: procedure

text: to

text: ﬁnd

text: lower

text: bounds

text: for

text: the

text: DTSP.

text: This

text: article

text: provides

text: a

text: new

text: direc-

text: tion

text: for

text: developing

text: approximation

text: algorithms

text: for

text: the

text: DTSP.

text: Currently,

text: the

text: transformation

text: method

text: increases

text: the

text: size

text: of

text: the

text: one-in-a-set

text: TSP

text: by

text: or

text: times,

text: resulting

text: in

text: a

text: large

text: TSP.

text: Computationally,

text: more

text: efﬁcient

text: tools

text: for

text: directly

text: solving

text: the

text: one-in-a-set

text: TSP

text: will

text: be

text: useful

text: in

text: ﬁnding

text: tighter

text: lower

text: and

text: upper

text: bounds

text: for

text: the

text: DTSP.

text: Future

text: work

text: can

text: also

text: address

text: the

text: same

text: problem

text: with

text: multiple

text: vehicles

text: and

text: other

text: precedence

text: constraints.

text: References

text: Optimizing

text: RLR

text: and

text: LRL

text: paths.

text: S.

text: Rathinam,

text: R.

text: Sengupta,

text: and

text: S.

text: Darbha,

text: “A

text: resource

text: allocation

text: algorithm

text: for

text: multivehicle

text: systems

text: with

text: nonholonomic

text: constraints,”

text: IEEE

text: Transactions

text: Automation

text: Science

text: and

text: Engineering,

text: vol.

text: pp.

text: J.

text: Le

text: Ny,

text: E.

text: Feron,

text: and

text: E.

text: Frazzoli,

text: “On

text: the

text: dubins

text: traveling

text: salesman

text: problem.”

text: IEEE

text: Trans.

text: Automat.

text: Contr.,

text: vol.

text: no.

text: pp.

text: P.

text: Chandler

text: and

text: M.

text: Pachter,

text: “Research

text: issues

text: in

text: autonomous

text: control

text: of

text: tactical

text: uavs,”

text: in

text: American

text: Control

text: Conference,

text: Proceedings

text: of

text: the

text: vol.

text: Jun

text: pp.

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: with motion constraints,” in ASME 2012 5th Annual Dynamic Systems and Control Conference joint with the JSME 2012 11th Motion and Vibration Conference. American Society of Mechanical Engineers, 2012, pp. 695–701. [20] S. G. Manyam, S. Rathinam, and S. Darbha, “Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints,” in Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on. IEEE, 2013, pp. 2378–2383. [21] S. Manyam, S. Rathinam, D. Casbeer, and E. Garcia, “Shortest paths of bounded curvature for the dubins interval problem,” arXiv preprint arXiv:1507.06980, 2015. [22] C. E. Noon and J. C. Bean, “A lagrangian based approach for the asymmetric generalized traveling salesman problem,” Op- erations Research, vol. 39, no. 4, pp. 623–632, July 1991. [Online]. Available: http://or.journal.informs.org/content/39/4/623 [23] G. Gutin and A. P. Punnen, Eds., The traveling salesman problem and its variations, ser. Combinatorial optimization. Dordrecht, London: Kluwer Academic, 2002. [Online]. Available: http://opac.inria.fr/record=b1120710 [24] D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study (Prince- ton Series in Applied Mathematics). Princeton, NJ, USA: Princeton University Press, 2007. [25] L.E.Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,” American Journal of Mathematics, vol. 79, no. 3, pp. 487–516, 1957. [26] X. Goaoc, H.-S. Kim, and S. Lazard, “Bounded-curvature shortest paths through a sequence of points using convex optimization,” SIAM Journal on Computing, vol. 42, no. 2, pp. 662–684, 2013. [Online]. Available: http://dx.doi.org/10.1137/100816079 [27] J.-D. Boissonnat, A. Ce´re´zo, and J. Leblond, “Shortest paths of bounded curvature in the plane,” Journal of Intelligent and Robotic Systems, vol. 11, no. 1-2, pp. 5–20, 1994. [Online]. Available: http://dx.doi.org/10.1007/BF01258291 7. Appendix 7.1. Proof of Lemma 4.1 Using Fig. 9, one can relate L and φ to θ using the following equations: 1 ρ sinφ + Lcosφ = x¯− ρ sinθ1, ρ cosφ − Lsinφ = ρ cosθ1. (20) The arrival angle θ2(RS,θ1) at target 2 is equal to 2π −φ. We now consider two different cases: x¯ > 2ρ and x¯ ≤ 2ρ (the RS path does not exist for a subset of angles of θ1 if x¯ < 2ρ). Case 1: x¯ > 2ρ. The length of the RS path is D := (θ1 + φ)ρ + L. Therefore, ddθD := (1 + ddθφ )ρ + ddθL . The derivatives of φ and L with respect to θ can be obtained by differentiating (20) 1as follows: 1 1 1 dφ dL (ρ cosφ − Lsinφ)dθ + cosφ dθ = −ρ cosθ1, (21) 1 1 dφ dL −(ρ sinφ + Lcosφ)dθ − sinφ dθ = −ρ sinθ1. (22) 1 1 Solving these equations and simplifying further, we obtain the following: dφ x¯ = cosφ − 1, (23) dθ L 1 dL ρx¯ dθ = − L cosθ1. (24) 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: with

label: reference

text: motion

text: constraints,”

text: in

text: ASME

text: Annual

text: Dynamic

text: Systems

text: and

text: Control

text: Conference

text: joint

text: with

text: the

text: JSME

text: Motion

text: and

text: Vibration

text: Conference.

text: American

text: Society

text: of

text: Mechanical

text: Engineers,

text: pp.

text: S.

text: G.

text: Manyam,

text: S.

text: Rathinam,

text: and

text: S.

text: Darbha,

text: “Computation

text: of

text: lower

text: bounds

text: for

text: a

text: multiple

text: depot,

text: multiple

text: vehicle

text: routing

text: problem

text: with

text: motion

text: constraints,”

text: in

text: Decision

text: and

text: Control

text: (CDC),

text: IEEE

text: Annual

text: Conference

text: on.

text: IEEE,

text: pp.

text: S.

text: Manyam,

text: S.

text: Rathinam,

text: D.

text: Casbeer,

text: and

text: E.

text: Garcia,

text: “Shortest

text: paths

text: of

text: bounded

text: curvature

text: for

text: the

text: dubins

text: interval

text: problem,”

text: arXiv

text: preprint

text: C.

text: E.

text: Noon

text: and

text: J.

text: C.

text: Bean,

text: “A

text: lagrangian

text: based

text: approach

text: for

text: the

text: asymmetric

text: generalized

text: traveling

text: salesman

text: problem,”

text: Op-

text: erations

text: Research,

text: vol.

text: no.

text: pp.

text: July

text: [Online].

text: Available:

text: G.

text: Gutin

text: and

text: A.

text: P.

text: Punnen,

text: Eds.,

text: The

text: traveling

text: salesman

text: problem

text: and

text: its

text: variations,

text: ser.

text: Combinatorial

text: optimization.

text: Dordrecht,

text: London:

text: Kluwer

text: Academic,

text: [Online].

text: Available:

text: D.

text: L.

text: Applegate,

text: R.

text: E.

text: Bixby,

text: V.

text: Chvatal,

text: and

text: W.

text: J.

text: Cook,

text: The

text: Traveling

text: Salesman

text: Problem:

text: A

text: Computational

text: Study

text: (Prince-

text: ton

text: Series

text: in

text: Applied

text: Mathematics).

text: Princeton,

text: NJ,

text: USA:

text: Princeton

text: University

text: Press,

text: L.E.Dubins,

text: “On

text: curves

text: of

text: minimal

text: length

text: with

text: a

text: constraint

text: on

text: average

text: curvature,

text: and

text: with

text: prescribed

text: initial

text: and

text: terminal

text: positions

text: and

text: tangents,”

text: American

text: Journal

text: of

text: Mathematics,

text: vol.

text: no.

text: pp.

text: X.

text: Goaoc,

text: H.-S.

text: Kim,

text: and

text: S.

text: Lazard,

text: “Bounded-curvature

text: shortest

text: paths

text: through

text: a

text: sequence

text: of

text: points

text: using

text: convex

text: optimization,”

text: SIAM

text: Journal

text: on

text: Computing,

text: vol.

text: no.

text: pp.

text: [Online].

text: Available:

text: J.-D.

text: Boissonnat,

text: A.

text: Ce´re´zo,

text: and

text: J.

text: Leblond,

text: “Shortest

text: paths

text: of

text: bounded

text: curvature

text: in

text: the

text: plane,”

text: Journal

text: of

text: Intelligent

text: and

text: Robotic

text: Systems,

text: vol.

text: no.

text: pp.

text: [Online].

text: Available:

text: Appendix

text: Proof

text: of

text: Lemma

text: Using

text: Fig.

text: one

text: can

text: relate

text: L

text: and

text: φ

text: to

text: θ

text: using

text: the

text: following

text: equations:

text: ρ

text: sinφ

text: Lcosφ

text: x¯−

text: ρ

text: ρ

text: cosφ

text: Lsinφ

text: ρ

text: The

text: arrival

text: angle

text: at

text: target

text: is

text: equal

text: to

text: 2π

text: −φ.

text: We

text: now

text: consider

text: two

text: different

text: cases:

text: x¯

text: 2ρ

text: and

text: x¯

text: 2ρ

text: (the

text: RS

text: path

text: does

text: not

text: exist

text: for

text: a

text: subset

text: of

text: angles

text: of

text: θ1

text: if

text: x¯

text: Case

text: x¯

text: The

text: length

text: of

text: the

text: RS

text: path

text: is

text: D

text: φ)ρ

text: L.

text: Therefore,

text: ddθD

text: ddθφ

text: )ρ

text: ddθL

text: The

text: derivatives

text: of

text: φ

text: and

text: L

text: with

text: respect

text: to

text: θ

text: can

text: be

text: obtained

text: by

text: differentiating

text: follows:

text: dφ

text: dL

text: (ρ

text: cosφ

text: Lsinφ)dθ

text: cosφ

text: dθ

text: −ρ

text: dφ

text: dL

text: −(ρ

text: sinφ

text: Lcosφ)dθ

text: sinφ

text: dθ

text: −ρ

text: Solving

text: these

text: equations

text: and

text: simplifying

text: further,

text: we

text: obtain

text: the

text: following:

text: dφ

text: x¯

text: cosφ

text: dθ

text: L

text: dL

text: ρx¯

text: dθ

text: L

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: the distance of the shortest path of type T that starts at (x1,y1) with a departure angle of θ1 and arrives at (x2,y2) with an arrival angle in I2. In this case, the arrival angle at (x2,y2) will be a function of θ1 and T and is denoted as θ2(T ,θ1). T 1(θ1) is set to ∞ if a path of type T does not exist or if θ2(T ,θ1) ∈/ I2. Similarly, let T 2(θ2) denote the distance of the shortest path of type T that starts at (x1,y1) with a departure angle in I1 and arrives at (x2,y2) with an arrival angle of θ2. In this case, the departure angle at (x1,y1) will be a function of θ2 and T and is denoted as θ1(T ,θ2). T 2(θ2) is set to ∞ if the path of type T does not exist or if θ1(T ,θ2) ∈/ I1. From the deﬁnitions, note that minθ1∈I1 T 1(θ1) = minθ2∈I2 T 2(θ2). The following theorem provides a way to further simplify equation (1) and solve the Dubins interval problem: Theorem 3.1. min min{d12(θ1,θ2)} = min{d∗, min{RS1(θ1),SR1(θ1),LS1(θ1),SL1(θ1),LR1(θ1),RL1(θ1)}} (2) θ1∈I1 θ2∈I2 θ1∈I1 where d∗ := min{d12(θ1min,θ2min),d12(θ1max,θ2min),d12(θ1min,θ2max),d12(θ1max,θ2max)}. In English, this theorem states that an optimal path to the Dubins interval problem must be one of the following: 1. An optimal Dubins path consisting of at most three segments such that both the arrival and departure angles at each target belong to one of the boundary values of the respective intervals, or 2. An optimal Dubins path consisting of at most two segments such that the angle constraints are satis- ﬁed. After proving this theorem in the next subsection, we will provide algorithms to solve for the optimal Dubins paths with at most two segments (i.e., to solve minθ1∈I1 P(θ1) for any path P ∈ {RS1,SR1,LS1,SL1,LR1,RL1}). As d∗ in the above theorem can already be computed directly using Dubins’s result [25], one can then com- pute the optimal cost for the Dubins interval problem and the corresponding departure and arrival angles. 3.1. Proof of Theorem 3.1 This theorem will be proved in two parts. First, we will ﬁrst show how to simplify minθ1∈I1,θ2∈I2 P(θ1,θ2) for any path P ∈ {RSR,RSL,LSR,LSL}. Then we will address the LRL and the RLR paths. The following result is known [26] for each of the paths P ∈ {RSR,RSL,LSR,LSL} from (x1,y1,θ1) to (x2,y2,θ2): Lemma 3.1. For any P ∈ {RSR,RSL,LSR,LSL} and i = 1,2, either ∂P∂(θθ1,θ2) ≥ 0 ∀ θi or ∂P∂(θθ1,θ2) ≤ 0 ∀ θi when P exists and none of its curved segments vanish. i i Now let us apply the above lemma to the RSL path. The RSL path ceases to exist when the segment S vanishes, i.e., the RSL path reduces to an RL path. In addition, when one of the curved segments vanishes, the RSL path reduces to either the RS or the SL path (refer to Fig. 5). Therefore, given θ , the optimum for 1 ##LTLine## ##LTLine##

text: the

text: distance

text: of

text: the

text: shortest

text: path

text: of

text: type

text: T

text: that

text: starts

text: at

text: with

text: a

text: departure

text: angle

text: of

text: θ1

text: and

text: arrives

text: at

text: with

text: an

text: arrival

text: angle

text: in

text: In

text: this

text: case,

text: the

text: arrival

text: angle

text: at

text: will

text: be

text: a

text: function

text: of

text: θ1

text: and

text: T

text: and

text: is

text: denoted

text: as

text: T

text: is

text: set

text: to

font: TVVISR+StandardSymL

text: if

text: a

text: path

text: of

text: type

text: T

text: does

text: not

text: exist

text: or

text: if

text: Similarly,

text: let

text: T

text: denote

text: the

text: distance

text: of

text: the

text: shortest

text: path

text: of

text: type

text: T

text: that

text: starts

text: at

text: with

text: a

text: departure

text: angle

text: in

text: and

text: arrives

text: at

text: with

text: an

text: arrival

text: angle

text: of

text: In

text: this

text: case,

text: the

text: departure

text: angle

text: at

text: will

text: be

text: a

text: function

text: of

text: θ2

text: and

text: T

text: and

text: is

text: denoted

text: as

text: T

text: is

text: set

text: to

text: if

text: the

text: path

text: of

text: type

text: T

text: does

text: not

text: exist

text: or

text: if

text: From

text: the

text: deﬁnitions,

text: note

text: that

text: T

text: T

text: The

text: following

text: theorem

text: provides

text: a

text: way

text: to

text: further

text: simplify

text: equation

text: and

text: solve

text: the

text: Dubins

text: interval

text: problem:

text: Theorem

text: min

text: min{d∗,

text: where

text: d∗

text: In

text: English,

text: this

text: theorem

text: states

text: that

text: an

text: optimal

text: path

text: to

text: the

text: Dubins

text: interval

text: problem

text: must

text: be

text: one

text: of

text: the

text: following:

text: An

text: optimal

text: Dubins

text: path

text: consisting

text: of

text: at

text: most

text: three

text: segments

text: such

text: that

text: both

text: the

text: arrival

text: and

text: departure

text: angles

text: at

text: each

text: target

text: belong

text: to

text: one

text: of

text: the

text: boundary

text: values

text: of

text: the

text: respective

text: intervals,

text: or

text: An

text: optimal

text: Dubins

text: path

text: consisting

text: of

text: at

text: most

text: two

text: segments

text: such

text: that

text: the

text: angle

text: constraints

text: are

text: satis-

text: ﬁed.

text: After

text: proving

text: this

text: theorem

text: in

text: the

text: next

text: subsection,

text: we

text: will

text: provide

text: algorithms

text: to

text: solve

text: for

text: the

text: optimal

text: Dubins

text: paths

text: with

text: at

text: most

text: two

text: segments

text: (i.e.,

text: to

text: solve

text: for

text: any

text: path

text: P

text: As

text: d∗

text: in

text: the

text: above

text: theorem

text: can

text: already

text: be

text: computed

text: directly

text: using

text: Dubins’s

text: result

text: one

text: can

text: then

text: com-

text: pute

text: the

text: optimal

text: cost

text: for

text: the

text: Dubins

text: interval

text: problem

text: and

text: the

text: corresponding

text: departure

text: and

text: arrival

text: angles.

text: Proof

text: of

text: Theorem

text: This

text: theorem

text: will

text: be

text: proved

text: in

text: two

text: parts.

text: First,

text: we

text: will

text: ﬁrst

text: show

text: how

text: to

text: simplify

text: for

text: any

text: path

text: P

text: {RSR,RSL,LSR,LSL}.

text: Then

text: we

text: will

text: address

text: the

text: LRL

text: and

text: the

text: RLR

text: paths.

text: The

text: following

text: result

text: is

text: known

text: for

text: each

text: of

text: the

text: paths

text: P

text: {RSR,RSL,LSR,LSL}

text: from

text: to

text: Lemma

text: For

text: any

text: P

text: {RSR,RSL,LSR,LSL}

text: and

text: i

text: either

text: θi

text: or

text: θi

text: when

text: P

text: exists

text: and

text: of

text: its

text: curved

text: segments

text: vanish.

text: i

text: i

text: Now

text: let

text: us

text: apply

text: the

text: above

text: lemma

text: to

text: the

text: RSL

text: path.

text: The

text: RSL

text: path

text: ceases

text: to

text: exist

text: when

text: the

text: segment

text: S

text: vanishes,

text: i.e.,

text: the

text: RSL

text: path

text: reduces

text: to

text: an

text: RL

text: path.

text: In

text: addition,

text: when

text: one

text: of

text: the

text: curved

text: segments

text: vanishes,

text: the

text: RSL

text: path

text: reduces

text: to

text: either

text: the

text: RS

text: or

text: the

text: SL

text: path

text: (refer

text: to

text: Fig.

text: Therefore,

text: given

text: θ

text: the

text: optimum

text: for

text: ##LTLine##

text: ##LTLine##


text: text and more engagement with Leap Motion. Continuing to exercise 3D interactions from hand inputs rather than gamepad controllers could help immerse the player and manipulate the data more effectively. Currently, we are transitioning to the Oculus Rift DK2 to utilize the enhanced display and accurate positional tracking. Some potential future features we plan to implement in the user-interface include multi-selection and annotation. We also plan to continue researching other ways to enable user interaction and improve usability. This project reveals the added potential of how utilizing the VR platform can bring a more effective visual experience. We have effectively visualized Twitter on a 3D model of MIT’s campus to improve Big Data visual analytics. This research has shown how (1) virtual reality can also be used as a data visualization platform, (2) a more immersive environment enables user interaction, (3) patterns and visual analytics are more efﬁcient when working in a geospatial domain. REFERENCES [1] S. Lohr, “The age of big data,” New York Times, vol. 11, 2012. [2] M. Schroeck, R. Shockley, J. Smart, D. Romero-Morales, and P. Tufano, “Analytics: The real-world use of big data,” IBM Institute for Business Value—executive report, IBM Institute for Business Value, 2012. [3] A. McAfee and E. Brynjolfsson, “Big data: the management revolu- tion.,” Harvard business review, no. 90, pp. 60–6, 2012. [4] J. J. Thomas, Illuminating the path:[the research and development agenda for visual analytics]. IEEE Computer Society, 2005. [5] D. A. Keim, “Information visualization and visual data mining,” Visu- alization and Computer Graphics, IEEE Transactions on, vol. 8, no. 1, pp. 1–8, 2002. Fig. 8. Top: Linear progression comparing time to complete function call for positioning tweets with number of tweets present. Bottom: Logistic [6] Q. Ho and M. Jern, “Exploratory 3d geovisual analytics,” in Research, progression comparing ratio of number of collisions with number of tweets. Innovation and Vision for the Future, 2008. RIVF 2008. IEEE Interna- tional Conference on, pp. 276–283, IEEE, 2008. [7] S. Wang, Z. Mao, C. Zeng, H. Gong, S. Li, and B. Chen, “A new a frame rate of at least 60-75 fps for a comfortable user method of virtual reality based on unity3d,” in Geoinformatics, 2010 experience. With more vertices rendered in the scene, more 18th International Conference on, pp. 1–5, IEEE, 2010. draw calls are sent to the GPU. In addition, Oculus Rift [8] “Unity3d.” http://unity3d.com/. rendering and Leap Motion gesture recognition requires a lot [9] M. Hubbell and J. Kepner, “Large scale network situational awareness of processing. Upgrading from a traditional laptop to a more via 3d gaming technology,” in High Performance Extreme Computing (HPEC), 2012 IEEE Conference on, pp. 1–5, IEEE, 2012. powerful machine can produce a more ideal game experience. [10] B. Kot, B. Wuensche, J. Grundy, and J. Hosking, “Information vi- sualisation utilising 3d computer game engines case study: a source code comprehension tool,” in Proceedings of the 6th ACM SIGCHI V. CONCLUSION AND FUTURE WORK New Zealand chapter’s international conference on Computer-human interaction: making CHI natural, pp. 53–60, ACM, 2005. Although much progress has been made, further improve- [11] S. Djorgovski, P. Hut, R. Knop, G. Longo, S. McMillan, E. Vesperini, ments could enhance both application performance and user C. Donalek, M. Graham, A. Mahabal, F. Sauer, et al., “The mica exper- interactive gameplay. Rendering 3D models scales linearly iment: Astrophysics in virtual worlds,” arXiv preprint arXiv:1301.6808, with performance. Activating and deactivating colliders when 2013. needed can help reduce the computation load. Additional [12] C. Donalek, S. Djorgovski, A. Cioc, A. Wang, J. Zhang, E. Lawler, shaders could be applied to the 3D buildings of Cambridge S. Yeh, A. Mahabal, M. Graham, A. Drake, et al., “Immersive and collaborative data visualization using virtual reality platforms,” in Big to provide a better rendition and give the player more options Data (Big Data), 2014 IEEE International Conference on, pp. 609–614, of how the tweets are overlaid in the scene. Occlusion layers IEEE, 2014. for overlapping tweets and blocked buildings could be applied [13] “Mapd.” mapd.csail.mit.edu. to prevent unnecessary rendering. [14] J. J. White and R. E. Roth, “Twitterhitter: Geovisual analytics for harvesting insight from volunteered geographic information,” in Pro- Although we have a few useful analytics now, we intend ceedings of GIScience, vol. 2010, 2010. to add more features that allow for further engagement by the [15] P. Cho, H. Anderson, R. Hatch, and P. Ramaswami, “Real-time 3d ladar player. Originally, this work was done in Unity 4.6 and Oculus imaging,” in Applied Imagery and Pattern Recognition Workshop, 2006. Rift DK1. Implementing Unity’s UI system allows for 3D AIPR 2006. 35th IEEE, pp. 5–5, IEEE, 2006. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: text

text: and

text: more

text: engagement

text: with

text: Leap

text: Motion.

text: Continuing

text: to

text: exercise

text: interactions

text: from

text: hand

text: inputs

text: rather

text: than

text: gamepad

text: controllers

text: could

text: help

text: immerse

text: the

text: player

text: and

text: manipulate

text: the

text: data

text: more

text: effectively.

text: Currently,

text: we

text: are

text: transitioning

text: to

text: the

text: Oculus

text: Rift

text: to

text: utilize

text: the

text: enhanced

text: display

text: and

text: accurate

text: positional

text: tracking.

text: Some

text: potential

text: future

text: features

text: we

text: plan

text: to

text: implement

text: in

text: the

text: user-interface

text: include

text: multi-selection

text: and

text: annotation.

text: We

text: also

text: plan

text: to

text: continue

text: researching

text: other

text: ways

text: to

text: enable

text: user

text: interaction

text: and

text: improve

text: usability.

text: This

text: project

text: reveals

text: the

text: added

text: potential

text: of

text: how

text: utilizing

text: the

text: VR

text: platform

text: can

text: bring

text: a

text: more

text: effective

text: visual

text: experience.

text: We

text: have

text: effectively

text: visualized

text: Twitter

text: on

text: a

text: model

text: of

text: MIT’s

text: campus

text: to

text: improve

text: Big

text: Data

text: visual

text: analytics.

text: This

text: research

text: has

text: shown

text: how

text: virtual

text: reality

text: can

text: also

text: be

text: used

text: as

text: a

text: data

text: visualization

text: platform,

text: a

text: more

text: immersive

text: environment

text: enables

text: user

text: interaction,

text: patterns

text: and

text: visual

text: analytics

text: are

text: more

text: efﬁcient

text: when

text: working

text: in

text: a

text: geospatial

text: domain.

text: REFERENCES

text: S.

text: Lohr,

text: “The

text: age

text: of

text: big

text: data,”

text: New

text: York

text: Times,

text: vol.

text: M.

text: Schroeck,

text: R.

text: Shockley,

text: J.

text: Smart,

text: D.

text: Romero-Morales,

text: and

text: P.

text: Tufano,

text: “Analytics:

text: The

text: real-world

text: use

text: of

text: big

text: data,”

text: IBM

text: Institute

text: for

text: Business

text: Value—executive

text: report,

text: IBM

text: Institute

text: for

text: Business

text: Value,

text: A.

text: McAfee

text: and

text: E.

text: Brynjolfsson,

text: “Big

text: data:

text: the

text: management

text: revolu-

text: tion.,”

text: Harvard

text: business

text: review,

text: no.

text: pp.

text: J.

text: J.

text: Thomas,

text: Illuminating

text: the

text: path:[the

text: research

text: and

text: development

text: agenda

text: for

text: visual

text: analytics].

text: IEEE

text: Computer

text: Society,

text: D.

text: A.

text: Keim,

text: “Information

text: visualization

text: and

text: visual

text: data

text: mining,”

text: Visu-

text: alization

text: and

text: Computer

text: Graphics,

text: IEEE

text: Transactions

text: on,

text: vol.

text: no.

text: pp.

text: Fig.

text: Top:

text: Linear

text: progression

text: comparing

text: time

text: to

text: complete

text: function

text: call

text: for

text: positioning

text: tweets

text: with

text: number

text: of

text: tweets

text: present.

text: Bottom:

text: Logistic

text: Q.

text: Ho

text: and

text: M.

text: Jern,

text: “Exploratory

text: geovisual

text: analytics,”

text: in

text: Research,

text: progression

text: comparing

text: ratio

text: of

text: number

text: of

text: collisions

text: with

text: number

text: of

text: tweets.

text: Innovation

text: and

text: Vision

text: for

text: the

text: Future,

text: RIVF

text: IEEE

text: Interna-

text: tional

text: Conference

text: on,

text: pp.

text: IEEE,

text: S.

text: Wang,

text: Z.

text: Mao,

text: C.

text: Zeng,

text: H.

text: Gong,

text: S.

text: Li,

text: and

text: B.

text: Chen,

text: “A

text: new

text: a

text: frame

text: rate

text: of

text: at

text: least

text: fps

text: for

text: a

text: comfortable

text: user

text: method

text: of

text: virtual

text: reality

text: based

text: on

text: in

text: Geoinformatics,

text: experience.

text: With

text: more

text: vertices

text: rendered

text: in

text: the

text: scene,

text: more

text: International

text: Conference

text: on,

text: pp.

text: IEEE,

text: draw

text: calls

text: are

text: sent

text: to

text: the

text: GPU.

text: In

text: addition,

text: Oculus

text: Rift

text: rendering

text: and

text: Leap

text: Motion

text: gesture

text: recognition

text: requires

text: a

text: lot

text: M.

text: Hubbell

text: and

text: J.

text: Kepner,

text: “Large

text: scale

text: network

text: situational

text: awareness

text: of

text: processing.

text: Upgrading

text: from

text: a

text: traditional

text: laptop

text: to

text: a

text: more

text: via

text: gaming

text: technology,”

text: in

text: High

text: Performance

text: Extreme

text: Computing

text: (HPEC),

text: IEEE

text: Conference

text: on,

text: pp.

text: IEEE,

text: powerful

text: machine

text: can

text: produce

text: a

text: more

text: ideal

text: game

text: experience.

text: B.

text: Kot,

text: B.

text: Wuensche,

text: J.

text: Grundy,

text: and

text: J.

text: Hosking,

text: “Information

text: vi-

text: sualisation

text: utilising

text: computer

text: game

text: engines

text: case

text: study:

text: a

text: source

text: code

text: comprehension

text: tool,”

text: in

text: Proceedings

text: of

text: the

text: ACM

text: SIGCHI

text: V.

text: CONCLUSION

text: AND

text: FUTURE

text: WORK

text: New

text: Zealand

text: chapter’s

text: international

text: conference

text: on

text: Computer-human

text: interaction:

text: making

text: CHI

text: natural,

text: pp.

text: ACM,

text: Although

text: much

text: progress

text: has

text: been

text: made,

text: further

text: improve-

text: S.

text: Djorgovski,

text: P.

text: Hut,

text: R.

text: Knop,

text: G.

text: Longo,

text: S.

text: McMillan,

text: E.

text: Vesperini,

text: ments

text: could

text: enhance

text: both

text: application

text: performance

text: and

text: user

text: C.

text: Donalek,

text: M.

text: Graham,

text: A.

text: Mahabal,

text: F.

text: Sauer,

text: et

text: al.,

text: “The

text: mica

text: exper-

text: interactive

text: gameplay.

text: Rendering

text: models

text: scales

text: linearly

text: iment:

text: Astrophysics

text: in

text: virtual

text: worlds,”

text: arXiv

text: preprint

text: with

text: performance.

text: Activating

text: and

text: deactivating

text: colliders

text: when

text: needed

text: can

text: help

text: reduce

text: the

text: computation

text: load.

text: Additional

text: C.

text: Donalek,

text: S.

text: Djorgovski,

text: A.

text: Cioc,

text: A.

text: Wang,

text: J.

text: Zhang,

text: E.

text: Lawler,

text: shaders

text: could

text: be

text: applied

text: to

text: the

text: buildings

text: of

text: Cambridge

text: S.

text: Yeh,

text: A.

text: Mahabal,

text: M.

text: Graham,

text: A.

text: Drake,

text: et

text: al.,

text: “Immersive

text: and

text: collaborative

text: data

text: visualization

text: using

text: virtual

text: reality

text: platforms,”

text: in

text: Big

text: to

text: provide

text: a

text: better

text: rendition

text: and

text: give

text: the

text: player

text: more

text: options

text: Data

text: (Big

text: Data),

text: IEEE

text: International

text: Conference

text: on,

text: pp.

text: of

text: how

text: the

text: tweets

text: are

text: overlaid

text: in

text: the

text: scene.

text: Occlusion

text: layers

text: IEEE,

text: for

text: overlapping

text: tweets

text: and

text: blocked

text: buildings

text: could

text: be

text: applied

text: “Mapd.”

text: mapd.csail.mit.edu.

text: to

text: prevent

text: unnecessary

text: rendering.

text: J.

text: J.

text: White

text: and

text: R.

text: E.

text: Roth,

text: “Twitterhitter:

text: Geovisual

text: analytics

text: for

text: harvesting

text: insight

text: from

text: volunteered

text: geographic

text: information,”

text: in

text: Pro-

text: Although

text: we

text: have

text: a

text: few

text: useful

text: analytics

text: now,

text: we

text: intend

text: ceedings

text: of

text: GIScience,

text: vol.

text: to

text: add

text: more

text: features

text: that

text: allow

text: for

text: further

text: engagement

text: by

text: the

text: P.

text: Cho,

text: H.

text: Anderson,

text: R.

text: Hatch,

text: and

text: P.

text: Ramaswami,

text: “Real-time

text: ladar

text: player.

text: Originally,

text: this

text: work

text: was

text: done

text: in

text: Unity

text: and

text: Oculus

text: imaging,”

text: in

text: Applied

text: Imagery

text: and

text: Pattern

text: Recognition

text: Workshop,

text: Rift

text: Implementing

text: Unity’s

text: UI

text: system

text: allows

text: for

text: AIPR

text: IEEE,

text: pp.

text: IEEE,

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: 11 [9] L. P. Pitaevskii and S. Stringari, Bose-Einstein Conden- V. Konotop, and G. Huang, Opt. Lett. 38, 4033 (2013); sation (Clarendon Press: Oxford and New York, 2003). C. Hang, D. A. Zezyulin, G. Huang, V. V. Konotop, and [10] K. Go´ral, K. Rza¸z˙ewski, and T. Pfau, Phys. Rev. A 61, B. A. Malomed, ibid. 39, 5387 (2014). 051601(R) (2000); S. Yi and L. You, ibid. 041604(R); L. [24] S. Klaiman, U. Gu¨nther, and N. Moiseyev, Phys. Rev. Santos, G. V. Shlyapnikov, P. Zoller, and M. Lewenstein, Lett. 101, 080402 (2008). Phys. Rev. Lett. 85 1791 (2000); P. Pedri and L. Santos, [25] Z. H. Musslimani, K. G. Makris, R. El-Ganainy, and D. ibid. 95, 200404 (2005); N. Christodoulides, Phys. Rev. Lett. 100, 030402 (2008). [11] S. Sinha and L. Santos, Phys. Rev. Lett. 99, 140406 [26] Sumei Hu, Xuekai Ma, Daquan Lu, Zhenjun Yang, (2007). Yizhou Zheng, and Wei Hu, Phys. Rev. A 84, 043818 [12] A. G. Litvak and A. M. Sergeev, JETP Lett. 27, 517 (2011); Zhiwei Shi, Xiujuan Jiang, Xing Zhu, and Hua- (1978). gang Li, Phys. Rev. A 84, 053855 (2011); S. Nixon, L. [13] C. Conti, M. Peccianti, and G. Assanto, Phys. Rev. Lett. Ge, and J. Yang, Phys. Rev. A 85, 023822 (2012); V. 91, 073901 (2003); ibid. 92, 113902 (2004). Achilleos, P. G. Kevrekidis, D. J. Frantzeskakis, and R. [14] M. Kunze, T. Ku¨pper, V.K. Mezentsev, E. G. Shapiro, Carretero-Gonz´alez, Phys. Rev. A 86, 013808 (2012); X. and S. Turitsyn, Physica D 128, 273 (1999); Yu. S. Zhu, H. Wang, L. X. Zheng, H. Li, and Y. J. He, Opt. Kivshar, T. Alexander, and S. K. Turitsyn, 2001, Phys. Lett. 36, 2680 (2011); Keya Zhou, Zhongyi Guo, Jicheng Lett. A 278, 225; V. I. Yukalov, E. P. Yukalova, and Wang, and Shutian Liu, Opt. Lett. 35, 2928 (2010); H. V. S. Bagnato, Phys. Rev. A 66, 043602 (2002); R. D’ Wang and J. Wang, Opt. Express 19, 4030 (2011); Zhien Agosta, B. A. Malomed, and C. Presilla, Laser Phys. 12, Lu and Zhi-Ming Zhang, ibid. 19, 11457 (2011). 37 (2002); V. V. Konotop and P. G. Kevrekidis, Phys. [27] D. A. Zezyulin and V. V. Konotop, Phys. Rev. A 85, Rev. Lett. 91, 230402 (2003); P. G. Kevrekidis, V. V. 043840 (2012). Konotop, A. Rodrigues, and D. J. Frantzeskakis, J. Phys. [28] Z. H. Shi, H. Li, X. Zhu, and X. Jiang, EPL 98, 64006 B: At. Mol. Opt. Phys. 38, 1173 (2005). (2012); S. Hu, D. Lu, X. Ma, Q. Guo, and W. Hu, EPL [15] M. Edwards, K. Burnett, Phys. Rev. A 51, 1382 (1995); 98, 14006 (2012); X. Zhu, H. Li, H. Wang, and Y. He, P. A. Ruprecht, M. J. Holland, K. Burnett, and M. Ed- JOSA B 30, 1987 (2013); S. Hu, X. Ma, D. Lu, Y. Zheng, wards, Phys. Rev. A 51, 4704 (1995); F. Dalfovo and S. and W. Hu, Phys. Rev. A ibid., 043826 (2012) H. Li, Stringari, Phys. Rev. A 53, 2477 (1996); V. I. Yukalov, X. Jiang, X. Zhu, and Z. Shi, Phys. Rev. A 86, 023840 E. P. Yukalova, and V. S. Bagnato, Phys. Rev. A 56, (2012); C. P. Jisha, A. Alberucci, V. A. Brazhnyi, and 4845 (1997). G. Assanto, ibid. 89, 013812 (2014); L. Fang, J. Gao, Z. [16] C. Wang, P. G. Kevrekidis, D. J. Frantzeskakis, B. A. Shi, X. Zhu, and H. Li, Eur. Phys. J. D 68, 298 (2014); Malomed, Physica D 240 805 (2011); P. A. Tsiliﬁs, P. G. [29] V. M. P´erez-Garc´ıa, V. V. Konotop, and J. J. Garc´ıa- Kevrekidis, and V. M. Rothos, J. Phys. A: Math. Theor. Ripoll, Phys. Rev. E 62, 4300 (2000); J. J. Garc´ıa-Ripoll, 47, 035201 (2014). V. V. Konotop, B. Malomed, and V. M. P´erez-Garc´ıa [17] Y. V. Kartashov, V. A. Vysloukh, and L. Torner, Phys. Mathematics and Computers in Simulation 62, 21-30 Rev. Lett. 93, 153903 (2004). (2003). [18] Z. Xu, Y. V. Kartashov, and L. Torner, Phys. Rev. Lett. [30] T. Kato, Perturbation Theory for Linear Operators 95, 113901 (2005); N. K. Efremidis, Phys. Rev. A 77, (Springer-Verlag, Berlin, 1966). 063824 (2008). [31] M. Znojil, Phys. Lett. A 259, 220 (1999). [19] J. Cuevas, B. A. Malomed, P. G. Kevrekidis, and D. J. [32] Handbook of Mathematical Functions, edited by M. Frantzeskakis, Phys. Rev. A 79, 053608 (2009). Abramovitz and I. A. Stegun (National Bureau of Stan- [20] D. A. Zezyulin, G. L. Alﬁmov, V. V. Konotop, and V. dards, Washington, DC, 1972). M. P´erez-Garc´ıa, Phys. Rev. A 78, 013606 (2008). [33] T. Dohnal and P. Siegl, Bifurcation of nonlin- [21] C. M. Bender, and S. Boettcher, Phys. Rev. Lett. 80, ear eigenvalues in problems with antilinear symmetry, 5243 (1998). arXiv:1504.00054 [math-ph]. [22] C. E. Ru¨ter, K. G. Makris, R. El-Ganainy, D. N. [34] M. P. Coles, D. E. Pelinovsky, and P. G. Kevrekidis, Non- Christodoulides, M. Segev, and D. Kip, Nat. Phys. 6, linearity 23, 1753 (2010). 192 (2010). [35] C. Gallo and D. Pelinovsky, Stud. App. Math. 133, 398 [23] C. Hang, G. Huang, and V. V. Konotop, Phys. Rev. (2014). Lett. 110, 083604 (2013); C. Hang, D. A. Zezyulin, V.

text: L.

text: P.

text: Pitaevskii

text: and

text: S.

text: Stringari,

text: Bose-Einstein

text: Conden-

text: V.

text: Konotop,

text: and

text: G.

text: Huang,

text: Opt.

text: Lett.

text: sation

text: (Clarendon

text: Press:

text: Oxford

text: and

text: New

text: York,

text: C.

text: Hang,

text: D.

text: A.

text: Zezyulin,

text: G.

text: Huang,

text: V.

text: V.

text: Konotop,

text: and

text: K.

text: Go´ral,

text: K.

text: Rza¸z˙ewski,

text: and

text: T.

text: Pfau,

text: Phys.

text: Rev.

text: A

text: B.

text: A.

text: Malomed,

text: ibid.

text: S.

text: Yi

text: and

text: L.

text: You,

text: ibid.

text: L.

text: S.

text: Klaiman,

text: U.

text: Gu¨nther,

text: and

text: N.

text: Moiseyev,

text: Phys.

text: Rev.

text: Santos,

text: G.

text: V.

text: Shlyapnikov,

text: P.

text: Zoller,

text: and

text: M.

text: Lewenstein,

text: Lett.

text: Phys.

text: Rev.

text: Lett.

text: P.

text: Pedri

text: and

text: L.

text: Santos,

text: Z.

text: H.

text: Musslimani,

text: K.

text: G.

text: Makris,

text: R.

text: El-Ganainy,

text: and

text: D.

text: ibid.

text: N.

text: Christodoulides,

text: Phys.

text: Rev.

text: Lett.

text: S.

text: Sinha

text: and

text: L.

text: Santos,

text: Phys.

text: Rev.

text: Lett.

text: Sumei

text: Hu,

text: Xuekai

text: Ma,

text: Daquan

text: Lu,

text: Zhenjun

text: Yang,

text: Yizhou

text: Zheng,

text: and

text: Wei

text: Hu,

text: Phys.

text: Rev.

text: A

text: A.

text: G.

text: Litvak

text: and

text: A.

text: M.

text: Sergeev,

text: JETP

text: Lett.

text: Zhiwei

text: Shi,

text: Xiujuan

text: Jiang,

text: Xing

text: Zhu,

text: and

text: Hua-

text: gang

text: Li,

text: Phys.

text: Rev.

text: A

text: S.

text: Nixon,

text: L.

text: C.

text: Conti,

text: M.

text: Peccianti,

text: and

text: G.

text: Assanto,

text: Phys.

text: Rev.

text: Lett.

text: Ge,

text: and

text: J.

text: Yang,

text: Phys.

text: Rev.

text: A

text: V.

text: ibid.

text: Achilleos,

text: P.

text: G.

text: Kevrekidis,

text: D.

text: J.

text: Frantzeskakis,

text: and

text: R.

text: M.

text: Kunze,

text: T.

text: Ku¨pper,

text: V.K.

text: Mezentsev,

text: E.

text: G.

text: Shapiro,

text: Carretero-Gonz´alez,

text: Phys.

text: Rev.

text: A

text: X.

text: and

text: S.

text: Turitsyn,

text: Physica

text: D

text: Yu.

text: S.

text: Zhu,

text: H.

text: Wang,

text: L.

text: X.

text: Zheng,

text: H.

text: Li,

text: and

text: Y.

text: J.

text: He,

text: Opt.

text: Kivshar,

text: T.

text: Alexander,

text: and

text: S.

text: K.

text: Turitsyn,

text: Phys.

text: Lett.

text: Keya

text: Zhou,

text: Zhongyi

text: Guo,

text: Jicheng

text: Lett.

text: A

text: V.

text: I.

text: Yukalov,

text: E.

text: P.

text: Yukalova,

text: and

text: Wang,

text: and

text: Shutian

text: Liu,

text: Opt.

text: Lett.

text: H.

text: V.

text: S.

text: Bagnato,

text: Phys.

text: Rev.

text: A

text: R.

text: D’

text: Wang

text: and

text: J.

text: Wang,

text: Opt.

text: Express

text: Zhien

text: Agosta,

text: B.

text: A.

text: Malomed,

text: and

text: C.

text: Presilla,

text: Laser

text: Phys.

text: Lu

text: and

text: Zhi-Ming

text: Zhang,

text: ibid.

text: V.

text: V.

text: Konotop

text: and

text: P.

text: G.

text: Kevrekidis,

text: Phys.

text: D.

text: A.

text: Zezyulin

text: and

text: V.

text: V.

text: Konotop,

text: Phys.

text: Rev.

text: A

text: Rev.

text: Lett.

text: P.

text: G.

text: Kevrekidis,

text: V.

text: V.

text: Konotop,

text: A.

text: Rodrigues,

text: and

text: D.

text: J.

text: Frantzeskakis,

text: J.

text: Phys.

text: Z.

text: H.

text: Shi,

text: H.

text: Li,

text: X.

text: Zhu,

text: and

text: X.

text: Jiang,

text: EPL

text: B:

text: At.

text: Mol.

text: Opt.

text: Phys.

text: S.

text: Hu,

text: D.

text: Lu,

text: X.

text: Ma,

text: Q.

text: Guo,

text: and

text: W.

text: Hu,

text: EPL

text: M.

text: Edwards,

text: K.

text: Burnett,

text: Phys.

text: Rev.

text: A

text: X.

text: Zhu,

text: H.

text: Li,

text: H.

text: Wang,

text: and

text: Y.

text: He,

text: P.

text: A.

text: Ruprecht,

text: M.

text: J.

text: Holland,

text: K.

text: Burnett,

text: and

text: M.

text: Ed-

text: JOSA

text: B

text: S.

text: Hu,

text: X.

text: Ma,

text: D.

text: Lu,

text: Y.

text: Zheng,

text: wards,

text: Phys.

text: Rev.

text: A

text: F.

text: Dalfovo

text: and

text: S.

text: and

text: W.

text: Hu,

text: Phys.

text: Rev.

text: A

text: ibid.,

text: H.

text: Li,

text: Stringari,

text: Phys.

text: Rev.

text: A

text: V.

text: I.

text: Yukalov,

text: X.

text: Jiang,

text: X.

text: Zhu,

text: and

text: Z.

text: Shi,

text: Phys.

text: Rev.

text: A

text: E.

text: P.

text: Yukalova,

text: and

text: V.

text: S.

text: Bagnato,

text: Phys.

text: Rev.

text: A

text: C.

text: P.

text: Jisha,

text: A.

text: Alberucci,

text: V.

text: A.

text: Brazhnyi,

text: and

text: G.

text: Assanto,

text: ibid.

text: L.

text: Fang,

text: J.

text: Gao,

text: Z.

text: C.

text: Wang,

text: P.

text: G.

text: Kevrekidis,

text: D.

text: J.

text: Frantzeskakis,

text: B.

text: A.

text: Shi,

text: X.

text: Zhu,

text: and

text: H.

text: Li,

text: Eur.

text: Phys.

text: J.

text: D

text: Malomed,

text: Physica

text: D

text: P.

text: A.

text: Tsiliﬁs,

text: P.

text: G.

text: V.

text: M.

text: P´erez-Garc´ıa,

text: V.

text: V.

text: Konotop,

text: and

text: J.

text: J.

text: Garc´ıa-

text: Kevrekidis,

text: and

text: V.

text: M.

text: Rothos,

text: J.

text: Phys.

text: A:

text: Math.

text: Theor.

text: Ripoll,

text: Phys.

text: Rev.

text: E

text: J.

text: J.

text: Garc´ıa-Ripoll,

text: V.

text: V.

text: Konotop,

text: B.

text: Malomed,

text: and

text: V.

text: M.

text: P´erez-Garc´ıa

text: Y.

text: V.

text: Kartashov,

text: V.

text: A.

text: Vysloukh,

text: and

text: L.

text: Torner,

text: Phys.

text: Mathematics

text: and

text: Computers

text: in

text: Simulation

text: Rev.

text: Lett.

text: Z.

text: Xu,

text: Y.

text: V.

text: Kartashov,

text: and

text: L.

text: Torner,

text: Phys.

text: Rev.

text: Lett.

text: T.

text: Kato,

text: Perturbation

text: Theory

text: for

text: Linear

text: Operators

text: N.

text: K.

text: Efremidis,

text: Phys.

text: Rev.

text: A

text: (Springer-Verlag,

text: Berlin,

text: M.

text: Znojil,

text: Phys.

text: Lett.

text: A

text: J.

text: Cuevas,

text: B.

text: A.

text: Malomed,

text: P.

text: G.

text: Kevrekidis,

text: and

text: D.

text: J.

text: Handbook

text: of

text: Mathematical

text: Functions,

text: edited

text: by

text: M.

text: Frantzeskakis,

text: Phys.

text: Rev.

text: A

text: Abramovitz

text: and

text: I.

text: A.

text: Stegun

text: (National

text: Bureau

text: of

text: Stan-

text: D.

text: A.

text: Zezyulin,

text: G.

text: L.

text: Alﬁmov,

text: V.

text: V.

text: Konotop,

text: and

text: V.

text: dards,

text: Washington,

text: DC,

text: M.

text: P´erez-Garc´ıa,

text: Phys.

text: Rev.

text: A

text: T.

text: Dohnal

text: and

text: P.

text: Siegl,

text: Bifurcation

text: of

text: nonlin-

text: C.

text: M.

text: Bender,

text: and

text: S.

text: Boettcher,

text: Phys.

text: Rev.

text: Lett.

text: ear

text: eigenvalues

text: in

text: problems

text: with

text: antilinear

text: symmetry,

text: [math-ph].

text: C.

text: E.

text: Ru¨ter,

text: K.

text: G.

text: Makris,

text: R.

text: El-Ganainy,

text: D.

text: N.

text: M.

text: P.

text: Coles,

text: D.

text: E.

text: Pelinovsky,

text: and

text: P.

text: G.

text: Kevrekidis,

text: Non-

text: Christodoulides,

text: M.

text: Segev,

text: and

text: D.

text: Kip,

text: Nat.

text: Phys.

text: linearity

text: C.

text: Gallo

text: and

text: D.

text: Pelinovsky,

text: Stud.

text: App.

text: Math.

text: C.

text: Hang,

text: G.

text: Huang,

text: and

text: V.

text: V.

text: Konotop,

text: Phys.

text: Rev.

text: Lett.

text: C.

text: Hang,

text: D.

text: A.

text: Zezyulin,

text: V.


text: 4 for n = 0 no double eigenvalues Ω exists. Therefore n,k (cid:82) the fundamental solutions from family n = 0 are always − stable in the small-amplitude limit. (Mn,k)1,1 = b(n2) + (cid:82) { K K } w˜ w˜ ∗ w˜ + w˜ ∗ w˜ dx It is easy to check that the eigenvalue Ω splits in k k w˜ n n w˜ k n,k n n , (19) exactly the same way as the opposite double eigenvalue w˜2dx − (cid:82) k Ωn,2n−k = Ωn,k, i.e., if Ωn,k splits into two real eigen- − values then Ωn,2n−k also splits into two real eigenvalues (Mn,k)2,2 = b(n2) (cid:82) { K K } and vice versa. Therefore, in order to examine stability of w˜ − w˜ − ∗ w˜ + w˜ ∗ w˜ − dx 2n k 2n k w˜ n n w˜ 2n k small-amplitude nonlinear modes that belong to the nth n (cid:82) n , (20) w˜2 − dx family, it is suﬃcient to analyze o−nly n positive double 2n k (cid:82) eigenvalues Ωn,k with k = 0, . . . , n 1. − w˜ w˜ − K w˜∗ dx (M ) = (cid:82) n 2n k w˜n k , (21) In order to examine splitting of the double eigenval- n,k 2,1 w˜2 − dx ues Ω , we employ Eqs. (8) which yield the following (cid:82) 2n k n,k asymptotic expansion for the linear stability operator: K ∗ w˜ w˜ w˜ − dx L = L˜n + σε2L(n2) + o(ε2), where the correction L(n2) is (Mn,k)1,2 = n k ww˜˜n2dx2n k . (22) given as k (cid:32) (cid:33) Thus in order to check reality of the eigenvalues of the −b(n2) + (−K|w˜∗nK|2) + w˜nKw˜n∗ − Kw|˜nK| w˜n− ∗K . mofaittrsixquMadnr,ka,tiict cihsasruaﬃctceireinsttictoeqc−ounastiidoner, it.he.e, dthisecrqiumainntaintyt w˜ ∗ b(2) ( w˜ 2) w˜ D = [(M ) +(M ) ]2 4 det M . For D > n w˜n n n n w˜n n,k n,k 1,1 n,k 2,2 n,k n,k 0 the eigenvalues of M are real while a situation with n,k D < 0 corresponds to a pair of complex conjugated n,k Following the standard arguments of the perturbation eigenvalues. The situation Dn,k = 0 requires a more theory for linear operators [30], in order to address the delicate analysis as in this case behavior of the double × splitting of the double eigenvalue Ωn,k we consider a 2 2 eigenvalue Ωn,k is determined by the next terms of the matrix deﬁned as asymptotic expansions. Using analytical expressions for the eigenfuctions   w˜n(x), the entries of matrices Mn,k and hence the de- terminant D can be computed analytically with a n,k    (cid:104) ∗(cid:105) (cid:104) ∗(cid:105)  computer algebra program (at least, for several relevant  L(cid:104)(n2)p(nI,)k, p(n∗I,(cid:105))k L(n2(cid:104))p(nI,I2)n−k, p∗(cid:105)(nI,)k  slyhtaipcaels eoxfptrheesskioenrnsealrfeuntoctoiobnulKky(xt)o).bTe hpererseesnutletidnginatnhae-  p(nI,)k, p(nI,)k p(nI,)k, p(nI,)k  paper. However, for an interested reader to have an idea M = , n,k (cid:104) ∗ (cid:105) (cid:104) ∗ (cid:105) of how the expressions for the determinants D read, L(2)p(I) , p(II) − L(2)p(II) − , p(II) − n,k n n,k n,2n k n n,2n k n,2n k in Appendix we provide two expressions for D and (cid:104) ∗ (cid:105) (cid:104) ∗ (cid:105) 1,0 p(II) − , p(II) − p(II) − , p(II) − D obtained for the Gaussian kernel and α = 0. Com- n,2n k n,2n k n,2n k n,2n k 2,0 plexity of the expressions for D increases drastically n,k (cid:82) if larger numbers n or nonzero values of α are involved. Nevertheless, these expressions are available analytically (cid:104) (cid:105) † and can be used for ﬁnding the domains of positivity and where a, b = b (x)a(x)dx for any two column vec- † negativity of the determinants D which are considered tors a and b (here means the transposition and complex n,k as functions of λ and α. conjugation). If both the eigenvalues of matrix M are n,k V. RESULTS FOR THE REAL PARABOLIC real, then the double eigenvalue Ω splits into two real n,k POTENTIAL and simple eigenvalues. If such a situation takes place − for all k = 0, 1, . . . , n 1, then the small-amplitude non- Let us start presentation of our results with an impor- linear modes w (x) from the nth family are stable. On PT n tant particular case α = 0, when -symmetric contri- the other hand, if for some k the matrix M has a com- n,k bution is absent, and the model is conservative. First, it plex eigenvalue, then the double eigenvalue Ω splits n,k is relevant to notice that for α = 0 the eigenvalue prob- into a pair of complex-conjugated eigenvalues. This is lem (10) admits an exact solution with eigenvalue ω = 2 suﬃcient to conclude that the small-amplitude nonlinear and the respective eig(cid:18)envector given(cid:19)as modes from the nth family are unstable. Recall that real and imaginary parts of w˜ (x) have op- (cid:48) n xw + w posite parities. Using this fact, one can establish that all p = − n n(cid:48) . (23) xw + w the entries of the matrices M are real numbers which n n n,k read ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: for

text: n

text: no

text: double

text: eigenvalues

text: Ω

text: exists.

text: Therefore

text: n,k

label: equation

text: the

text: fundamental

text: solutions

text: from

text: family

text: n

text: are

text: always

text: stable

text: in

text: the

text: small-amplitude

text: limit.

text: K

text: K

text: w˜

text: w˜

text: w˜

text: w˜

text: w˜

text: dx

text: It

text: is

text: easy

text: to

text: check

text: that

text: the

text: eigenvalue

text: Ω

text: splits

text: in

text: k

text: k

text: w˜

text: n

text: n

text: w˜

text: k

text: n,k

text: n

text: n

text: exactly

text: the

text: same

text: way

text: as

text: the

text: opposite

text: double

text: eigenvalue

text: k

text: Ωn,k,

text: i.e.,

text: if

text: Ωn,k

text: splits

text: into

text: two

text: real

text: eigen-

text: values

text: then

text: also

text: splits

text: into

text: two

text: real

text: eigenvalues

text: K

text: K

text: and

text: vice

text: versa.

text: Therefore,

text: in

text: order

text: to

text: examine

text: stability

text: of

text: w˜

text: w˜

text: w˜

text: w˜

text: w˜

text: dx

text: k

text: k

text: w˜

text: n

text: n

text: w˜

text: k

text: small-amplitude

text: nonlinear

text: modes

text: that

text: belong

text: to

text: the

text: nth

text: n

text: n

text: dx

text: family,

text: it

text: is

text: suﬃcient

text: to

text: analyze

text: o−nly

text: n

text: positive

text: double

text: k

text: eigenvalues

text: Ωn,k

text: with

text: k

text: n

text: w˜

text: w˜

text: K

text: w˜∗

text: dx

text: (M

text: n

text: k

text: w˜n

text: k

text: In

text: order

text: to

text: examine

text: splitting

text: of

text: the

text: double

text: eigenval-

text: n,k

text: dx

text: ues

text: Ω

text: we

text: employ

text: Eqs.

text: which

text: yield

text: the

text: following

text: k

text: n,k

text: asymptotic

text: expansion

text: for

text: the

text: linear

text: stability

text: operator:

text: K

text: w˜

text: w˜

text: w˜

text: dx

text: L

text: L˜n

text: where

text: the

text: correction

text: is

text: n

text: k

text: k

text: given

text: as

text: k

text: Thus

text: in

text: order

text: to

text: check

text: reality

text: of

text: the

text: eigenvalues

text: of

text: the

text: w˜nKw˜n∗

text: Kw|˜nK|

text: w˜n−

text: ∗K

text: mofaittrsixquMadnr,ka,tiict

text: it.he.e,

text: dthisecrqiumainntaintyt

text: w˜

text: w˜

text: w˜

text: D

text: [(M

text: +(M

text: det

text: M

text: For

text: D

text: n

text: w˜n

text: n

text: n

text: n

text: w˜n

text: n,k

text: n,k

text: n,k

text: n,k

text: n,k

text: the

text: eigenvalues

text: of

text: M

text: are

text: real

text: while

text: a

text: situation

text: with

text: n,k

text: D

text: corresponds

text: to

text: a

text: pair

text: of

text: complex

text: conjugated

text: n,k

text: Following

text: the

text: standard

text: arguments

text: of

text: the

text: perturbation

text: eigenvalues.

text: The

text: situation

text: Dn,k

text: requires

text: a

text: more

text: theory

text: for

text: linear

text: operators

text: in

text: order

text: to

text: address

text: the

text: delicate

text: analysis

text: as

text: in

text: this

text: case

text: behavior

text: of

text: the

text: double

text: splitting

text: of

text: the

text: double

text: eigenvalue

text: Ωn,k

text: we

text: consider

text: a

text: eigenvalue

text: Ωn,k

text: is

text: determined

text: by

text: the

text: next

text: terms

text: of

text: the

text: matrix

text: deﬁned

text: as

text: asymptotic

text: expansions.

text: Using

text: analytical

text: expressions

text: for

text: the

text: eigenfuctions

text: w˜n(x),

text: the

text: entries

text: of

text: matrices

text: Mn,k

text: and

text: hence

text: the

text: de-

text: terminant

text: D

text: can

text: be

text: computed

text: analytically

text: with

text: a

text: n,k

text: computer

text: algebra

text: program

text: (at

text: least,

text: for

text: several

text: relevant

text: slyhtaipcaels

text: hpererseesnutletidnginatnhae-

text: p(nI,)k,

text: p(nI,)k

text: p(nI,)k,

text: p(nI,)k

text: paper.

text: However,

text: for

text: an

text: interested

text: reader

text: to

text: have

text: an

text: idea

text: M

text: n,k

text: of

text: how

text: the

text: expressions

text: for

text: the

text: determinants

text: D

text: read,

text: p(II)

text: p(II)

text: n,k

text: n

text: n,k

text: k

text: n

text: k

text: k

text: in

text: Appendix

text: we

text: provide

text: two

text: expressions

text: for

text: D

text: and

text: p(II)

text: p(II)

text: p(II)

text: p(II)

text: D

text: obtained

text: for

text: the

text: Gaussian

text: kernel

text: and

text: α

text: Com-

text: k

text: k

text: k

text: k

text: plexity

text: of

text: the

text: expressions

text: for

text: D

text: increases

text: drastically

text: n,k

text: if

text: larger

text: numbers

text: n

text: or

text: nonzero

text: values

text: of

text: α

text: are

text: involved.

text: Nevertheless,

text: these

text: expressions

text: are

text: available

text: analytically

text: and

text: can

text: be

text: used

text: for

text: ﬁnding

text: the

text: domains

text: of

text: positivity

text: and

text: where

text: a,

text: b

text: b

text: (x)a(x)dx

text: for

text: any

text: two

text: column

text: vec-

text: negativity

text: of

text: the

text: determinants

text: D

text: which

text: are

text: considered

text: tors

text: a

text: and

text: b

text: (here

text: means

text: the

text: transposition

text: and

text: complex

text: n,k

text: as

text: functions

text: of

text: λ

text: and

text: α.

text: conjugation).

text: If

text: both

text: the

text: eigenvalues

text: of

text: matrix

text: M

text: are

text: n,k

text: V.

text: RESULTS

text: FOR

text: THE

text: REAL

text: PARABOLIC

text: real,

text: then

text: the

text: double

text: eigenvalue

text: Ω

text: splits

text: into

text: two

text: real

text: n,k

text: POTENTIAL

text: and

text: simple

text: eigenvalues.

text: If

text: such

text: a

text: situation

text: takes

text: place

text: for

text: all

text: k

text: n

text: then

text: the

text: small-amplitude

text: non-

text: Let

text: us

text: start

text: presentation

text: of

text: our

text: results

text: with

text: an

text: impor-

text: linear

text: modes

text: w

text: (x)

text: from

text: the

text: nth

text: family

text: are

text: stable.

text: On

text: PT

text: n

text: tant

text: particular

text: case

text: α

text: when

text: -symmetric

text: contri-

text: the

text: other

text: hand,

text: if

text: for

text: some

text: k

text: the

text: matrix

text: M

text: has

text: a

text: com-

text: n,k

text: bution

text: is

text: absent,

text: and

text: the

text: model

text: is

text: conservative.

text: First,

text: it

text: plex

text: eigenvalue,

text: then

text: the

text: double

text: eigenvalue

text: Ω

text: splits

text: n,k

text: is

text: relevant

text: to

text: notice

text: that

text: for

text: α

text: the

text: eigenvalue

text: prob-

text: into

text: a

text: pair

text: of

text: complex-conjugated

text: eigenvalues.

text: This

text: is

text: lem

text: admits

text: an

text: exact

text: solution

text: with

text: eigenvalue

text: ω

text: suﬃcient

text: to

text: conclude

text: that

text: the

text: small-amplitude

text: nonlinear

text: and

text: the

text: respective

text: modes

text: from

text: the

text: nth

text: family

text: are

text: unstable.

text: Recall

text: that

text: real

text: and

text: imaginary

text: parts

text: of

text: w˜

text: (x)

text: have

text: op-

text: n

text: xw

text: w

text: posite

text: parities.

text: Using

text: this

text: fact,

text: one

text: can

text: establish

text: that

text: all

text: p

text: n

text: xw

text: w

text: the

text: entries

text: of

text: the

text: matrices

text: M

text: are

text: real

text: numbers

text: which

text: n

text: n

text: n,k

text: read

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##