Visualization of Spanners

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


1. Introduction

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.

2. Spanners based on cones

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''.

2.1. The geographic neighborhood graph

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.

2.2. The theta-graph

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.

Lemma

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.

Click to enter the applet!