Information Technology Reference
In-Depth Information
denote by
pq
the straight-line segment having
p
and
q
as end-points, and by
|
pq
|
the
length of
pq
.Ageometric path (
v
1
,...,v
n
) is
greedy
if
|
v
i
+1
v
n
|
<
|
v
i
v
n
|
,forevery
1.Ageometric graph
G
is
greedy
if, for every ordered pair of vertices
u
and
v
, there exists a greedy path from
u
to
v
in
G
.Aresult related to our paper is that,
for every point set
P
,theDelaunay triangulation of
P
is a greedy graph [13].
In this paper we study
self-approaching
and
increasing-chord graphs
, that are types
of proximity graphs defined by Alamdari
et al.
[2]. A geometric path
≤
i
≤
n
−
1
P
=(
v
1
,...,v
n
)
is
self-approaching
if, for every three points
a
,
b
,and
c
in this order on
P
from
v
1
to
v
n
(possibly
a
,
b
,and
c
are internal to segments of
.Ageometric
graph
G
is
self-approaching
if, for every ordered pair of vertices
u
and
v
,
G
contains
a self-approaching path from
u
to
v
;also,
G
is
increasing-chord
if, for every pair of
vertices
u
and
v
,
G
contains a path between
u
and
v
that is self-approaching both from
u
to
v
and from
v
to
u
;thus, an increasing-chord graph is also self-approaching.The
study of self-approaching and increasing-chord graphs is motivated by their relationship
with greedy graphs (a self-approachinggraph is also greedy), and by the fact that such
graphs have a small geometric dilation, namely at most 5.3332 [9] (self-approaching
graphs) and at most 2.094 [15] (increasing-chord graphs).
Alamdari
et al.
showed: (i) how to test in linear time whether a path in
P
), it holds that
|
bc
|
<
|
ac
|
2
is self-
approaching; (ii) a characterization of the class of self-approaching trees; and (iii) how
to construct, for every point set
P
with
n
points in
R
2
, an increasing-chord graph that
R
spans
P
and uses
O
(
n
) Steiner points.
In this paper we focusour attention on the problem of constructing increasing-chord
graphs spanninggiven point sets in
2
.Weprovetwomainresults.
R
-
We show that, for every point set
P
with
n
points, there exists an increasing-chord
planar graph with
O
(
n
) Steiner points spanning
P
. This answers a question of
Alamdari
et al.
[2] and improves upon their result (iii) above, since our increasing-
chord graphs are planar and contain increasing-chord paths between every pair of
points, including the Steiner points (which is not the case for the graphs in [2]). It is
interesting that ourresult is achieved by studying Gabriel triangulations, which are
proximity graphs strongly related to Delaunay triangulations (a Gabriel triangula-
tion of a point set
P
is a subgraph of the Delaunay triangulation of
P
). It has been
proved in [2] that Delaunay triangulations are not, in general, self-approaching.
-
We show that, for every convex point set
P
with
n
points, there exists an increasing-
chord graph that spans
P
and that has
O
(
n
log
n
) edges (and no Steiner points).
2
Definitions and Preliminaries
A
geometric graph
(
P,S
) consists of a point set
P
in the plane and of a set
S
of straight-
line segments (called
edges
) between points in
P
.Ageometric graph is
planar
if no two
of its edges cross. A planar geometric graph partitions the plane into connected regions
called
faces
. The bounded faces are
internal
and the unbounded face is the
outer face
.A
geometric planar graph is a
triangulation
if every internal face is delimited by a triangle
and the outer face is delimited by a convex polygon.
Let
p
,
q
,and
r
be points in the plane. We denote by
pqr
the angle defined by a
clockwise rotation around
q
bringing
pq
to coincide with
qr
.
∠