Petra
Specht Department of Computer Science University of Magdeburg, Germany EMail: petra@isg.cs.unimagdeburg.de This work was done at the School of Computer Science, Carleton University. 

Michiel
Smid School of Computer Science Carleton University , Ottawa, Ontario, Canada EMail: 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 straightline 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 tspanner 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 tspanner for S is called the stretch factor of G. It is clear that a tspanner for S always exists: Just connect any two points of S by an edge. In fact, this gives us a tspanner 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 tspanners (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 thetagraph contains all edges (p,r_p) obtained in this way. First observe that the number of edges of the thetagraph 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 thetagraph has O(n) edges. We will argue why the stretch factor of the thetagraph 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 thetagraph 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 thetagraph 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 / (12 sin (theta / 2)).
Hence, the thetagraph is a tspanner for t = 1 / (1  2 sin (theta / 2)).
By choosing the angle theta sufficiently small, the value of t
gets arbitrarily close to one.