Improved 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 ∈ 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). Dobkin et al. 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 (|DT(a,b)|)/(|ab|) is upper bounded by ((l + √5)/2)π ≈ 5.08. Recently, Xia improved this factor to 1.998. Amani et al. have also shown that if the points of S are in convex position, then a planar graph with these vertices can be constructed such that its stretch factor is 1.88. A set of points is said to be in convex position, if all points form the vertices of a convex polygon. 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.83, improving upon the previously known factors, for either the Delaunay triangulation or planar graph of a point set. Our result is obtained by investigating some geometric properties of DT(S) and showing that there exists a convex chain between a and b in DT(S) such that it is either contained in a semicircle of diameter ab, or enclosed by segment ab and a simple (convex) chain that consists of a circular arc and two or three line segments.