×

Improved stretch factor of Delaunay triangulations of points in convex position. (English) Zbl 1507.90184

Summary: Let \(S\) be a set of \(n\) points in the plane, and let \(DT (S)\) be the planar graph of the Delaunay triangulation of \(S\). For a pair of points \(a, b \in S\), denote by \(|{ab}|\) the Euclidean distance between \(a\) and \(b\). Denote by \(DT (a, b)\) the shortest path in \(DT (S)\) between \(a\) and \(b\), and let \(|DT (a, b)|\) be the total length of \(DT (a, b)\). D. P. Dobkin et al. [Discrete Comput. Geom. 5, No. 4, 399–407 (1990; Zbl 0693.05045)] were the first to show that \(DT (S)\) can be used to approximate the complete graph of \(S\) in the sense that the stretch factor \(\frac{|DT(a, b)|}{|a b|}\) is upper bounded by \(((1 + \sqrt{5})/2) \pi \approx 5.08\). Recently, Xia improved this factor to 1.998. A. Biniaz et al. [J. Comput. Geom. 7, No. 1, 520–539 (2016; Zbl 1405.68399)] have also shown that if the points of \(S\) are in convex position (i.e., they form the vertices of a convex polygon), then a planar graph with these vertices can be constructed such that its stretch factor is 1.88. In this paper, we prove that if the points of \(S\) are in convex position, then the stretch factor of \(DT (S)\) is less than 1.84, improving upon the previously known factors of Delaunay triangulations or planar graphs in the convex case.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Amani, M.; Biniaz, A.; Bose, P.; De Carufel, J-L; Maheshwair, A.; Smid, M., A plane 1.88-spanner for points in convex position, J Comput Geom, 7, 520-539 (2016) · Zbl 1405.68399
[2] Bose, P.; Smid, M., On plane geometric spanners: a survey and open problems, Comput Geom, 46, 818-830 (2013) · Zbl 1270.05032 · doi:10.1016/j.comgeo.2013.04.002
[3] de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational geometry: algorithms and applications (2008), Berlin: Springer, Berlin · Zbl 0939.68134 · doi:10.1007/978-3-540-77974-2
[4] Cui, S.; Kanji, IA; Xia, G., On the stretch factor of Delaunay triangulations of points in convex position, Comput Geom, 44, 104-109 (2011) · Zbl 1217.65046 · doi:10.1016/j.comgeo.2010.09.007
[5] Dobkin, DP; Friedman, ST; Supowit, KJ, Delaunay graphs are almost as good as complete graphs, Discret Comput Geom, 5, 399-407 (1990) · Zbl 0693.05045 · doi:10.1007/BF02187801
[6] Eppstein, D.; Sack, J-R; Urrutia, J., Spanning trees and spanners, Handbook of computational geometry, 425-462 (2000), Amsterdam: North-Hollard Press, Amsterdam · Zbl 0930.65001 · doi:10.1016/B978-044482537-7/50010-3
[7] Hershberger, J.; Suri, S., Practical methods for approximating shortest paths on a convex polytope in \(R^3\), Comput Geom, 10, 31-46 (1998) · Zbl 0896.68140 · doi:10.1016/S0925-7721(97)00004-7
[8] Keil, JM; Gutwin, CA, The Delaunay triangulation closely approximates the complete graph, Discret Comput Geom, 7, 13-28 (1992) · Zbl 0766.52004 · doi:10.1007/BF02187821
[9] Narasimhan, G.; Smid, M., Geometric spanner networks (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1140.68068 · doi:10.1017/CBO9780511546884
[10] Tan X, Sakthip C, Jiang B (2019) Improved stretch factor of Delaunay triangulations of points in convex position. In: Proceedings ofCOCOA. Lecturer notes in computer science, vol 11949, pp 473-484 · Zbl 1435.68354
[11] Xia, G., The stretch factor of the Delaunay triangulation is less than 1.998, SIAM J Comput, 42, 1620-1659 (2013) · Zbl 1302.65059 · doi:10.1137/110832458
[12] Xia G, Zhang L (2011) Towards the tight bound of the stretch factor of Delaunay triangulations. In: Proceedings of CCCG (2011), pp 175-180
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.