On the stretch factor of Delaunay triangulations of points in convex position (Q621926): Difference between revisions

Let \(S\) be a finite set of points in the Euclidean plane. Let \(G\) be a geometric graph in the plane whose point set is \(S\). The stretch factor of \(G\) is the maximum ratio, among all points \(p\) and \(q\) in \(S\), of the length of the shortest path from \(p\) to \(q\) in \(G\) over the Euclidean distance \(|pq|\). \textit{J. M. Keil} and \textit{C. A. Gutwin} [Lect. Notes Comput. Sci. 382, 47--56 (1989; Zbl 0766.52004)] proved that the stretch factor of the Delaunay triangulation of a set of points \(S\) in the plane is at most \(\frac{2\pi}{3\cos(\frac\pi6)}\approx 2.42\), which currently stands as the best upper bound on the stretch factor of Delaunay triangulations. In an open-problem session of the 19th Canadian Conference on Computational Geometry (CCCG 2007), \textit{P. Bose} suggested looking at the special case when the points in \(S\) are in convex position. According with this suggestion, the authors of the paper under review prove that in this case the stretch factor of the Delaunay triangulation of \(S\) is at most \(2.33\).