next up previous
Next: Problem 72: Polyhedron with Up: The Open Problems Project Previous: Problem 70: Yao-Yao Graph


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 (π/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 = π(1 + $ \sqrt{{5}}$)/2 $ \approx$ 5.08. The value of t was improved to 2π/(3 cos(π/6)) $ \approx$ 2.42 by Keil and Gutwin [KG92], and further strengthened in [BM04]. Chew showed that t is π/2 $ \approx$ 1.57 for points on a circle, providing a lower bound. ``It is widely believed that, for every set of points in $ \mathbb {R}$2, the Delaunay triangulation is a (π/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.
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.


next up previous
Next: Problem 72: Polyhedron with Up: The Open Problems Project Previous: Problem 70: Yao-Yao Graph
The Open Problems Project - December 04, 2015