Information Technology Reference
In-Depth Information
Algorithm 1.
B
ACKWARD
E
MBEDDING
Input
:
{U, D, L, R}
-path
P
=
d
1
,...,d
n−
1
, convex point set
S
of size
n
Output
:Function
E
:
V
(
P
)
ₒ S
for
i ₐ n −
1
downto
1
do
1
switch
d
i
do
2
case
U
:
E
(
v
i
+1
)
ₐ t
(
S
)
case
D
:
E
(
v
i
+1
)
ₐ b
(
S
)
case
L
:
E
(
v
i
+1
)
ₐ
(
S
)
3
case
R
:
E
(
v
i
+1
)
ₐ r
(
S
)
S ₐ S\{E
(
v
i
+1
)
}
4
E
(
v
1
)
ₐ v ∈ S
//
S
contains only one element
5
return
E
6
Proof.
Observe that the algorithm traverses the path backwards and decides the place-
ment of vertex
v
i
+1
based on the label of the edge (
v
i
,v
i
+1
), i.e.,
d
i
.If
d
i
=
U
(resp.
D, L, R
), vertex
v
i
+1
is placed on the topmost (resp. bottommost, leftmost, rightmost)
of the currently free points. Hence, when vertex
v
i
is placed at the next step on any
other free point, edge (
v
i
,v
i
+1
) is guaranteed to be direction-consistent.
For the planarity, observe that the procedure picking the rightmost, the topmost, and
the bottommost points of a left-sided point set, creates a consecutive subset of
S
.Thus,
for any
i,
1
1,path
P
i,n−
1
(and therefore also
P
1
,i−
1
) is mapped to a
consecutive subset of
S
. Hence, by Lemma 1, the created embedding is also planar.
≤
i
≤
n
−
The following lemmas can be proven based on Lemma 2 and the operations of rota-
tion of a point set and reverse of a path. See [1] for the missing proofs.
Lemma 3.
An
{
U,D,R
}
-path
P
=
d
1
,...,d
n−
1
admits aPDCE on any right-sided
pointset
S
such that
E
(
v
1
)
is
b
(
S
)
,t
(
S
)
,or
(
S
)
∈{
t
(
S
)
,b
(
S
)
}
,dependenton
whether
d
1
is
U, D
,or
R
, respectively.
Lemma 4.
Let
S
be a strip-convex pointsetandlet
P
=
d
1
,...,d
n−
1
be an
{
U,R
}
-
path.Algorithm
B
ACKWARD
E
MBEDDING
computes aPDCE
E
of
P
on
S
such that(i)
E
(
v
1
)
is
b
(
S
)
or
l
(
S
)
, and (ii)
E
(
v
n
)
is
t
(
S
)
or
r
(
S
)
,dependentonwhether
d
n−
1
is
U
or
R
, respectively.
4
Three-Directional Paths
The following lemma is the key ingredient for the proof of a main result of this paper.
We postpone its proof until we have seen how the lemma is used.
Lemma 5.
Let
S
be a convex pointsetwith the property that
t
(
S
)
is to therightof
b
(
S
)
.Any
{
U,D,R
}
-pathadmits aPDCE on
S
.
Theorem 1.
Any three-directionalpathadmits aPDCE onaconvex pointset.
Proof.
Case 1:
P
is an
-path. Since
S
is in general position,
t
(
S
) is either
to the right or to the left of
b
(
S
). In the former case a PDCE of
P
on
S
exists by
{
U,D,R
}
