Revisiting the Stretch Factor of Delaunay Triangulations of Points in Convex Position

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). 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 a constant, independent of S and n. The currently known best factor for a set of planar points is 1.998. In this paper, we prove that for a set S of points in convex position (i.e., they form the vertices of a convex polygon), the stretch factor of DT(S) is at most 1.77. This improves upon the previously known factor 1.84 in the convex case.