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 .
 
Search WWH ::




Custom Search