Information Technology Reference
In-Depth Information
Lemma 1.
Let
k
be thesizeoftheboundary of
F
.Forany
ʵ>
0
wecan efficiently
construct an inner
ʵ
-approximation
F
of
F
whose boundaryhassize
3
k
(see Figure 1).
We prove Lemma 1 using Lemma 2 in which, for every sufficiently small
ʵ>
0 we
construct a closed polygonal arc
P
ʵ
that is
ʵ
-close to the facial walk, does not have too
many bends, and so that the simple polygon bounded by
P
ʵ
lies in the interior of the
simple polygon bounded by
P
ʵ
for all 0
<ʵ
<ʵ
(in particular, any two polygonal
arcs are disjoint). There are various ways to achieve this. Pach and Wenger [20] use the
Minkowski sum of the facial walk (in their case the facial walk of a tree) and a square
diamond centered at 0.Weuse a slightly different construction, because it seems eas-
ier (both computationally and conceptually) and it gives a slightly better bound on the
number of bends (which is what we are most interested in); namely for the facial walk
of an
n
-vertex tree, Pach and Wenger construct a polygonal arc with 4
n
−
2 vertices,
while our polygonal arcs have 2
n
2 vertices. Our construction does have one disad-
vantage: the resulting drawings will get rather tight for sharp (acute or obtuse) angles
(the Minkowski-sum construction has the same problem for highly obtuse angles only).
−
Lemma 2.
Let
W
be a facial walk inaface
F
of a drawing of agraph
G
in theplane.
We can efficiently construct a disjointfamily of polygonal arcs
P
ʵ
so that
P
ʵ
is
ʵ
-close
to
W
andeach
P
ʵ
has at most
max
{
3
,
|
W
|}
vertices.
Proof.
Let
e,v,f
be a
corner
of
W
, that is, two consecutive edges
e
,
f
and their shared
vertex
v
.At
v
erect the angle bisector of
e
and
f
of length
ʵ
(inside
F
), and let
v
be the
endpoint of the bisector different from
v
.Forcomputational reasons, it may be better to
use the
1
-norm at this point (the Euclidean norm will lead to square root expressions
in the coordinates). If (
v
i
)
i
=1
,
then (
v
i
)
i
=1
defines a closed polygonal arc. If
ʵ
is sufficiently small, namely less than
half the distance between any vertex of
W
and a non-adjacent edgeon
W
,thearcis
free of self-crossings, and therefore bounds a simple polygon with
is the sequence of vertices along
W
, with
k
=
|
W
|
vertices. There
are two special cases in which this argument does not work: if the boundary walk is a
boundary walk on an isolated vertex or an isolated edge. In both of these cases, we can
approximate
W
using atriangular shape.
|
W
|
Lemma 2 allows us to replace a facial boundary with a
simple polygonwithholes
,
that is, a collection of closed polygonal arcs that bound a face which is very close
to the original boundary, has bounded complexity, and can be constructed efficiently.
This leads to a proof of Lemma 1. Namely, approximate each facial walk of the facial
boundary with an
ʵ
-close polygonal arc lying in
F
.Theunion of those arcs is a simple
polygon with holes as long as
ʵ
is less than half the distance between any two non-
adjacent vertices or edges. The upper bound of 3
k
will generally be a large overestimate,
but allows for the possibility that all the inner walks are walks on isolated vertices.
We n ow r e turn to the proof of Theorem 1. After constructing an inner
ʵ
-approximation
F
of
F
by using Lemma 1, the next step is to construct tree
T
.Triangulate
F
using at
most
m
F
+2(
b
2) triangles
3
−
and usearesult of Bern and Gilbert [3] to construct a
3
Every
n
-vertex polygon with
b
boundary components can be triangulated by inserting edges
in
O
(
n
log
n
) time. The number of resulting triangles is
n
+2(
b −
2) (see [19, Lemma 5.1]).
