**Next:** Problem 72: Polyhedron with Regular Pentagon Faces

**Previous:** Problem 70: Yao-Yao Graph a Spanner?

- Statement
For points S in convex position (i.e., every point is on the hull of S), is the Delaunay triangulation of S a (\pi/2)-spanner? A geometric graph is a

*t-spanner*(or just a*spanner*) if, for every pair of nodes, the shortest distance between the nodes following the edges of the graph is at most t times the Euclidean distance between them. The constant t is the*stretch factor*or*dilation*.- Origin
Prosenjit Bose [DO08].

- Status/Conjectures
Now closed: false. [This entry awaiting updating.]

- Partial and Related Results
Chew conjectured that the Delaunay triangulation is a t-spanner [Che89] for some constant t. Dobkin et al. [DFS90] established this for t = \pi (1+\sqrt{5})/2 \approx 5.08. The value of t was improved to 2 \pi / (3 \cos (\pi/6)) \approx 2.42 by Keil and Gutwin [KG92], and further strengthened in [BM04]. Chew showed that t is \pi/2 \approx 1.57 for points on a circle, providing a lower bound. “It is widely believed that, for every set of points in \R^2, the Delaunay triangulation is a (\pi/2)-spanner” [NS07], p. 470.

This history suggests the special case posed above.

There is a new forthcoming result: [CKX09].

- Appearances
- Categories
spanners; Delaunay triangulations

- Entry Revision History
J. O’Rourke, 29 Dec. 2008; 4 July 2009; 1 Apr. 2010.

- [BM04]
P. Bose and P. Morin. Online routing in triangulations.

*SIAM J. Comput.*, 33:937–951, 2004.- [Che89]
L. P. Chew. There are planar graphs almost as good as the complete graph.

*J. Comput. Syst. Sci.*, 39:205–219, 1989.- [CKX09]
Shiliang Cui, Iyad Kanj, and Ge Xia. On the dilation of Delaunay triangulations of points in convex position. In

*Proc. Canad. Conf. Comp. Geom.*, 2009. To appear, Aug. 2009.- [DFS90]
D. P. Dobkin, S. J. Friedman, and K. J. Supowit. Delaunay graphs are almost as good as complete graphs.

*Discrete Comput. Geom.*, 5:399–407, 1990.- [DO08]
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2007. In

*Proc. 20th Canad. Conf. Comput. Geom.*, 2008.- [KG92]
J. M. Keil and C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph.

*Discrete Comput. Geom.*, 7:13–28, 1992.- [NS07]
Giri Narasimhan and Michiel Smid.

*Geometric Spanner Networks*. Cambridge University Press, 2007.