| Petra
Specht Department of Computer Science University of Magdeburg, Germany E-Mail: petra@isg.cs.uni-magdeburg.de This work was done at the School of Computer Science, Carleton University. |
 |
| Michiel
Smid School of Computer Science Carleton University , Ottawa, Ontario, Canada E-Mail: michiel@scs.carleton.ca This author was suppported by NSERC. |
|
| Special thanks
to Jan Tusch and Michael Specht (students of Computer Science, University of Magdeburg) for the programming support. |
1. Introduction
2. Spanners based on
cones
The applet
A geometric spanner network for a set of points is a graph G in which each pair of vertices is connected by a "short'" path. What does this mean? The Euclidean length of any path in G between two vertices p and q is greater than or equal to |pq|, the Euclidean distance between p and q. We say that a path between p and q is "short'' if its length is no more than a constant factor times |pq|. Hence, the detour when following this path is not too "big''. To define this notion more precisely, let S be a finite set of points in the plane and let t>1 be a real number. Let G=(S,E) be a (directed or undirected) graph with vertex set S in which edges are drawn as straight-line segments joining two vertices. For any two vertices p and q of S, let d_G(p,q) denote the Euclidean length of a shortest path in G between p and q. We say that G is a t-spanner for S, if d_G(p,q) < t |pq| for any two vertices p and q of S. The smallest value of t for which G is a t-spanner for S is called the stretch factor of G. It is clear that a t-spanner for S always exists: Just connect any two points of S by an edge. In fact, this gives us a t-spanner for t=1. Clearly, the disadvantage is that the number of edges in this graph is quadratic in the number of vertices. In the next section, we will give two (related) constructions of t-spanners (for any constant t>1), that have only a linear number of edges.
The main idea in both constructions is to define the graph in such a way that for any two points p and q of S, there is an edge that takes us from p in the "direction'' of q. Let theta be a small angle. For each point p of S, we partition the plane into cones of angle theta, all having their apex at p. For each such cone, we would like to connect p to that point of S inside the cone that is "closest'' to p. There are two ways to define the notion of being "closest''.
This graph was introduced by Yao in 1982. For each point p of S and any cone C with apex p such that C contains at least one point of S different from p, let r_p be the point of S in C whose Euclidean distance to p is minimum. The geographic neighborhood graph contains all edges (p,r_p) obtained in this way.
This graph was introduced independently by Clarkson in 1987, and Keil in 1988. Consider any point p of S and any cone C that contains at least one point of S different from p. Let r_p be the point of S in C whose projection on the bisector of C is closest to p. The theta-graph contains all edges (p,r_p) obtained in this way. First observe that the number of edges of the theta-graph is less than or equal to n times 2 pi divided by theta, where n denotes the number of points of S. Hence, if we assume theta to be a constant, then the theta-graph has O(n) edges. We will argue why the stretch factor of the theta-graph is "small''. A similar analysis can be applied to the geographic neighborhood graph. Consider two points p and q of S. We will construct a "short'' path in the theta-graph between p and q. If p=q, then there is nothing to do. So assume that p and q are distinct points. Let C be the cone with apex p that contains q. The theta-graph contains an edge (p,r), where r is a point of S contained in C. We follow this edge, and recursively construct a path between r and q. The following lemma, due to Ruppert and Seidel, will imply that the path constructed in this way is a spanner path between p and q.
Consider two distinct points p and q of
S, and let theta be an angle such that 0 < theta < pi/3.
Let C be the cone with apex p that contains q. Let r be a point
in C and S whose projection on the bisector of C is at least as
close to p as the projection of q onto this bisector. Then |rq|
is less than or equal to |pq| - (1 - 2 sin (theta/2)) |pr|.
This lemma implies that |rq| < |pq|. Hence, the path
constructed above has the property that each edge takes us strictly
closer to the destination q. In particular, the construction terminates
and results in a path between p and q. A simple analysis, based
on the above lemma, shows that the length of this path is less
than or equal to t |pq|, where t = 1 / (1-2 sin (theta / 2)).
Hence, the theta-graph is a t-spanner for t = 1 / (1 - 2 sin (theta / 2)).
By choosing the angle theta sufficiently small, the value of t
gets arbitrarily close to one.