Information Technology Reference
In-Depth Information
Point Sets.
We say that a set
S
of points in the plane is in
general position
if no three
points are collinear and no two points have the same
x
-or
y
-coordinate. All point sets
mentioned in this paper are in general position. Let
S
be a convex point set. We denote
by
(
S
),
r
(
S
),
t
(
S
),
b
(
S
) the leftmost, the rightmost, the topmost, and the bottommost
point of
S
, respectively. A subset of points of
S
is called (
clockwise
)
consecutive
if its
points appear consecutively as we (clockwise) traverse the convex hull of
S
.
A convex point set
S
is called
left-sided (resp. right-sided)
if
t
(
S
) and
b
(
S
) (resp.
b
(
S
),
t
(
S
)) are clockwise consecutive on
S
,and
S
is called
one-sided
if
S
is left-
sided or right-sided.
S
is called
strip-convex
if (
i
) the points
b
(
S
) and
(
S
) are either
consecutive or coincide, and (
ii
) the points
t
(
S
) and
r
(
S
) are either consecutive or
coincide. For
p,q
S
, the points of
S
which lie between the vertical lines through
p
and
q
(including them) are said to be
vertically between
p
and
q
.
∈
Embeddings.
Let
P
be an
n
-vertex path (labeled) with vertex set
V
(
P
) and
S
be a
set of
n
points in general position. An
embedding
of
P
on
S
is an injective function
E
S
.Iftheedges of
P
are drawn as straight-line segments connecting corre-
sponding end-vertices, the embedding
:
V
(
P
)
ₒ
E
yields a drawing of
P
. We say that the embed-
ding
is
direction-consistent
if each
edge points to the direction corresponding to its label. Planar direction-consistent em-
beddings are abbreviated by PDCE. During the construction of an embedding, a point
p
is called
used
if a vertex has already been mapped to it. Otherwise,
p
is called
free
.
Throughout the paper we consider embeddingsof
n
-vertex paths on sets of
n
points,
unless explicitly stated differently.
E
is
planar
if this drawing is planar. We say that
E
Operations with Paths, Point Sets, and Embeddings.
Let
T
ↆ{
U,D,R,L
}
and
consider a
T
-path
P
=
d
1
d
2
...d
n−
1
.Let
S
beasetof
n
points and let
E
be a direction-
consistent embedding of
P
on
S
. Observe that
E
describes a direction-consistent em-
bedding of another path
P
I
on the same point set
S
. Path
P
I
is called the
reverse
path of
P
, and is constructed by reversing the directions of the edges of
P
and chang-
ing the labels to their opposite. Thus, formally
P
I
=
I
(
d
n−
1
)
...I
(
d
2
)
I
(
d
1
),where
I
(
L
)=
R
. This embedding of
P
I
on
S
is
(
U
)=
D
,
I
(
D
)=
U
,
I
(
R
)=
L
,and
I
E
I
. For example, if
P
=
UUDRL
,then
P
I
=
RLUDD
. Observe also
that (
P
I
)
I
=
P
.
denoted by
E
I
is aPDCE of
Observation 1.
Let
E
be aPDCE of a path
P
onapointset
S
.Then
P
I
on thesame pointset
S
.
yields a straight-line drawing
ʓ
of
P
.
Consider the rotation of
ʓ
counterclockwise by
ˀ/
2. This rotated drawing represents a
direction-consistent embedding, denoted by
Let
P
,
S
,and
E
be as above. The embedding
E
R
(
E
), of a new path, denoted by
R
(
P
),on
the rotated point set, denoted by
R
(
S
). This new path
R
(
P
) is formally defined as fol-
lows:
R
(
P
)=
R
(
d
1
)
R
(
d
2
)
...
R
(
d
n−
1
),where
R
(
U
)=
L
,
R
(
D
)=
R
,
R
(
R
)=
U
,
k
for
k
applications of
4
(
P
)=
P
and
and
R
(
L
)=
D
.Weuse the notation
R
R
.Thus,
R
4
(
S
)=
S
. Also, if
P
is an
2
(
P
)
R
{
U,D,L
}
-path and
S
is a right-sided point set then
R
2
(
S
) is a left-sided point set. Note that
P
I
2
(
P
).
is an
{
U,D,R
}
-path and
R
=
R
