Next: Problem 72: Polyhedron with Regular Pentagon Faces
Previous: Problem 70: Yao-Yao Graph a Spanner?
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.
Prosenjit Bose [DO08].
Now closed: false. [This entry awaiting updating.]
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].
spanners; Delaunay triangulations
J. O’Rourke, 29 Dec. 2008; 4 July 2009; 1 Apr. 2010.
P. Bose and P. Morin. Online routing in triangulations. SIAM J. Comput., 33:937–951, 2004.
L. P. Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39:205–219, 1989.
Shiliang Cui, Iyad Kanj, and Ge Xia. . In Proc. Canad. Conf. Comp. Geom., pages 161–164, August 2009.
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.
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2007. In Proc. 20th Canad. Conf. Comput. Geom., 2008.
J. M. Keil and C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom., 7:13–28, 1992.
Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007.