The Open Problems Project

Next: Problem 72: Polyhedron with Regular Pentagon Faces

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

Problem 71: Stretch-Factor for Points in Convex Position

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

[DO08].

Categories

spanners; Delaunay triangulations

Entry Revision History

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

Bibliography

[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. . In Proc. Canad. Conf. Comp. Geom., pages 161–164, August 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.