Improved stretch factor of Delaunay triangulations of points in convex position

Abstract

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). 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 $\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. Amani et al. 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.

1 Introduction

Let S be a set of n points in the plane, and let G(S) be such a graph that each vertex corresponds to a point in S and the weight of an edge is the Euclidean distance between its two endpoints. For a pair of points p, q in the plane, denote by pq the line segment connecting p and q, and |pq| the Euclidean distance between p and q. Denote by G(a, b) the shortest path in G(S) between two points $a, b \in S$, and |G(a, b)| the total length of path G(a, b). The graph G(S) is said to approximate the complete graph of S if $\frac{|G(a, b)|}{|a b|}$, called the stretch factor of G(S), is upper bounded by a constant, independent of S and n. It is then desirable to identify classes of graphs that approximate complete graphs well and have only O(n) edges, as these graphs have potential applications in geometric network design problems (Eppstein 2000; Narasimhan and Smid 2007).

Denote by DT(S) the planar graph of the Delaunay triangulation of S (de Berg et al. 2008). Dobkin et al. (1990) were the first to give a stretch factor $((1 + \sqrt{5})/2) \pi \approx 5.08)$ of Delaunay triangulations to complete graphs. Later, Keil and Gutwin (1992) improved it to $2 \pi / (3 \cos (\pi /6)) \approx 2.42$, and Cui et al. (2011) showed that the stretch factor of DT(S) for a set of points in convex position is 2.33. A set of points is said to be in convex position, if all points form the vertices of a convex polygon. Currently, the best result is due to Xia (2013), who proved that the stretch factor of DT(S) is 1.998. Determining the best possible stretch factor of Delaunay triangulations has been a long-standing open problem in computational geometry (Bose and Smid 2013). On the other hand, Xia and Zhang (2011) gave a lower bound 1.5932 on the stretch factor of DT(S).

Amani et al. (2016) have also constructed a planar graph, whose vertices are in convex position, such that its stretch factor is 1.88. Notice that the planar graph studied by Amani et al. is not the Delaunay triangulation of the given point set. The lower bound on the stretch factor of planar graphs in the convex case is 1.41611 (Bose and Smid 2013).

In this paper, we prove that the stretch factor of DT(S) for a set of points in convex position is 1.84. This improves upon the previously known factor 1.998 for Delaunay triangulations of points in convex position (clearly, the result of Xia 2013 works for a set of points in convex position). It also gives an improvement upon the stretch factor 1.88 for planar graphs with vertices in convex position, as Delaunay triangluations are planar. 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 a few line segments. The total length of the simple chain is less than 1.84|ab|.

2 Preliminaries

Assume that no four points of S are on the boundary of a circle in the plane, and no three points of S are on a line. The Voronoi diagram for S, denoted by Vor(S), is a partition of the plane into regions, each containing exactly one point in S, such that for each point $p \in S$, every point within its corresponding region, denoted by Vor(p), is closer to p than to any other point of S (de Berg et al. 2008). The boundaries of these Voronoi regions form a planar graph. The Delaunay triangulation of S, denoted by DT(S), is the straight-line dual of the Voronoi diagram for S; that is, we connect a pair of points in S if and only if they share a Voronoi boundary.

For a pair of points $a, b \in S$, denote by DT(a, b) the shortest path in DT(S) between a and b, in the Euclidean metric, and |DT(a, b)| the total length of path DT(a, b). The stretch factor of DT(S) is then the maximum value $\frac{|DT(a, b)|}{|a b|}$ among all point pairs (a, b).

Let us review an important idea of Dobkin et al.’s work (Dobkin et al. 1990). Denote by $a = a_{0}$, $a_{1}$, $\ldots$, $a_{m} = b$ the sequence of points of S, whose Voronoi regions intersect segment ab. See Fig. 1. The path obtained in this way is called the direct path from a to b (Dobkin et al. 1990).

For ease of presentation, denote by dp(a, b) the direct path from a to b in DT(S). Path dp(a, b) is said to be one-sided if all points of the path are to the same side of the line through a and b, including the special case that dp(a, b) consists of a single edge ab. See Fig. 1. If dp(a, b) is one-sided, then it has length at most $\pi |a b|/2$.

Lemma 1

(Dobkin et al. 1990) If path dp(a, b) is one-sided, then it has length at most $\pi |a b| / 2$.

Fig. 1

A one-sided, direct path from a to b

Let $p_i$ be the intersection point of ab with the Voronoi edge between $Vor(a_{i-1})$ and $Vor(a_{i})$, for $1 \le i \le m$. It follows from the definition of the Voronoi diagram that $p_i$ is the center of a circle that passes through $a_{i-1}$ and $a_i$ but contains no points of S in its interior. See Fig. 1. All points of path dp(a, b) are thus contained in the circle of diameter ab.

A simple property of the one-sided path dp(a, b) is that all points $p_i$ ($1 \le i \le m$) are monotone on segment ab (Dobkin et al. 1990). See also Fig. 1. A more general result than Lemma 1 is the following.

Lemma 2

(Dobkin et al. 1990) Let $C_{1}$, $C_{2}$, $\ldots$, $C_{k}$ be the circles all centered on a same line such that $U = \bigcup _{1 \le i \le k} C_{i}$ is connected. The boundary of U has length at most $\pi |a b|$ and is contained in the circle of diameter ab, where a and b are two extreme endpoints of U on the line.¹

3 The main result

Assume that the set S of given points is in convex position. For a point p in the plane, denote the coordinates of p by p.x and p.y, respectively. Assume that both a and b are on the x-axis, with $a.x < b.x$. Let C be the circle of diameter ab, and let o be the center of C. The bisector of two points p and q, denoted by $B_{p, q}$, is the perpendicular line through the middle point of segment pq.

Let CH(S) be the convex hull of points of S, i.e., the boundary of the smallest convex polygon containing all points of S (de Berg et al. 2008). Denote by SA[a, b] (resp. SB[a, b]) the polygonal chain of CH(S), which is above (resp. below) the line through a and b. For a point $p \in SA[a, b]$, denote by SA[a, p] and SA[p, b] the chains of SA[a, b] from a to p and from p to b, respectively. Analogously, SB[a, q] (resp. SB[q, b]), $q \in SB[a, b]$, represents the polygonal chain of SB[a, b] from a to q (resp. from q to b). Also, denote by SA(a, b) and SB(a, b) the open chains of SA[a, b] and SB[a, b], respectively.

Fig. 2

All triangles of DT(S) are assumed to properly intersect ab

We say segment ab properly intersects a Delaunay triangle if it goes across the interior of the triangle (i.e., ab does not intersect only at a vertex of the triangle). If a Delaunay triangle does not properly intersect ab, then at least one of its vertices (and two edges incident to that vertex) can be deleted from DT(S), without affecting the value of $\frac{|DT(a, b)|}{|a b|}$ (see Fig. 2). Then, the following observation can be made.

Observation 1

For any two points $a, b \in S$, one can assume that ab properly intersects all triangles of DT(S), in evaluating the value of $\frac{|DT(a, b)|}{|a b|}$.

Assume below that ab properly intersects all triangles of DT(S), see the right of Fig. 2. We will show that $\min \{ \frac{|SA[a, b]|}{|a b|}, \frac{|SB[a, b]|}{|a b|} \} \le 1.84$. The choice of SA[a, b] or SB[a, b] depends on whether path dp(a, b) intersects segment ab an odd number of times or not. The following results are obtained in this paper.

Lemma 3

Suppose that the first and last segments of path dp(a, b) are below and above the line through a and b, respectively. Then, there exists an angle $\alpha$ such that (i) $|DT(a, b)|/|a b| \le \sin (\alpha ) + \pi \cos (\alpha )/2$, $\pi /4 \le \alpha < \pi /2$, (ii) $|DT(a, b)|/|a b| \le \sin (\alpha ) + \cos (\alpha ) (\cos (\alpha ) + \alpha )$, $0< \alpha < \pi /4$, (iii) $|DT(a, b)|/|a b| \le \sin (\alpha ) + \cos (\alpha ) (\sin (\alpha ) + \pi /2 - \alpha )$, $\pi /6 \le \alpha < \pi /4$, or (iv) $|DT(a, b)|/|a b| \le \sin (\alpha ) + \cos (\alpha ) (2 \sin (\alpha ) + \pi /2 - 2\alpha )$, $0< \alpha < \pi /6$.

Lemma 4

Suppose that the first and last segments of path dp(a, b) are to the same side of the line through a and b. Then, there exists an angle $\beta$ such that $|DT(a, b)|/|a b| \le \beta + \cos (\beta ) (3\sin (\beta ) + \pi /2 - 3\beta )$, $0< \beta < \pi /6$.

The main result of this paper can then be summarized in the following theorem.

Theorem 1

Suppose that the set S of given points is in convex position, and a and b are two points of S. In the Delaunay triangulation of S, there is a path from a to b such that its length is less than 1.84|ab|.

Proof

Suppose that path dp(a, b) is not one-sided; otherwise, $|DT(a, b)| \le \pi |a b|/2$. Let $f_1(\alpha ) = \sin (\alpha ) + \pi \cos (\alpha )/2$, $\alpha \in [\pi /4, \pi /2)$, $f_2(\alpha ) = \sin (\alpha ) + \cos (\alpha ) (\cos (\alpha ) + \alpha )$, $\alpha \in (0, \pi /4)$, $f_3(\alpha ) = \sin (\alpha ) + \cos (\alpha ) (\sin (\alpha ) + \pi /2 - \alpha )$, $\alpha \in [\pi /6, \pi /4)$, $f_4(\alpha ) = \sin (\alpha ) + \cos (\alpha ) (2\sin (\alpha ) + \pi /2 - 2\alpha )$, $\alpha \in (0, \pi /6)$, and $f_5(\beta ) = \beta + \cos (\beta ) (3\sin (\beta ) + \pi /2 - 3\beta )$, $\beta \in (0, \pi /6)$. It follows from Lemmas 3 and 4 that $|DT(a, b)|/|a b| \le \max \{\pi /2, f_1(\alpha ), f_2(\alpha ), f_3(\alpha ), f_4(\alpha ), f_5(\beta ) \}$, for all possible values $\alpha$ and $\beta$. Figure 3 shows five functions, which are produced using gnuplot. (By definition, $f_4$ is very close to $f_5$.) For each $1 \le i \le 5$, we can obtain $f_i < 1.84$ by considering the variable’s value(s) satisfying $f'_i = 0$ and two extreme values of variable $\alpha$ or $\beta$. Actually, $f_3(\pi /6)$ gives the maximum value among all considered functions (see also Fig. 3). $\square$

Fig. 3

Illustrating the proof of Theorem 1

4 Proof of Lemma 3

Assume that neither SA[a, b] nor SB[a, b] is completely contained in the circle C of diameter ab; otherwise, $|DT(a, b)| \le \pi |a b| / 2$. Denote by ac and bd the first and last segments of path dp(a, b), as viewed from a, respectively. Then, both ac and bd are contained in C (Dobkin et al. 1990). See Fig. 4. Extend segments ac and bd until they touch the boundary of C, say, at points $c'$ and $d'$ respectively. Since $\angle b c' a = \angle a d' b = \pi /2$, either $\angle c' a d'$ or $\angle d' b c'$ is at least $\pi /2$. In the following, assume that $\angle d' b c' \ge \pi /2$, or equivalently, $\angle d b c' \ge \pi /2$.

Let i be the intersection point of C with $B_{b, d}$, which is vertically below ac. Since $B_{b,d}$ is perpendicular to bd, and since $\angle b c' a = \pi /2$ and $\angle d b c' \ge \pi /2$, $B_{b, d}$ properly intersects $a c'$. Hence, $i \ne c'$, and point i is outside of CH(S).

Denote by H the semicircle of diameter bi, which is vertically below bi (Fig. 4). We show below that SB[a, b] is contained in the region bounded by ab, ai and H, and then give a method to bound the total length of SB[a, b].

4.1 SB[a, b] is contained in the region bounded by ab, ai and H

Fig. 4

SB[a, b] is contained in the region bounded by ab, ai and H

Let e be the first vertex of SB[a, b], which is outside of C, as viewed from a. From the definition of i, point e is vertically below bi. Then, Vor(e) is adjacent to some regions Vor(q), $q \in SA[a, b] \cap S$ (Observation 1). Let f be the first vertex of SA[a, b] such that Vor(e) and Vor(f) are adjacent. Denote by ${{\mathcal {R}}}$ the chain formed by the common edges of Vor(p) and Vor(q), $p \in SB[e, b) \cap S$ and $q \in SA[f, b) \cap S$ (see Fig. 4).

We claim that ${{\mathcal {R}}}$ is vertically above (or on) $B_{b,d}$. If f happens to be d, then ${{\mathcal {R}}}$ is vertically above $B_{b, d}$ (Fig. 5). Consider below the situation in which f differs from d. If f is adjacent to d, then from Observation 1, there is a point $g \in SB[e, b) \cap S$ such that Vor(f), Vor(d) and Vor(g) share a Voronoi vertex, say, w. Clearly, w is the rightmost (resp. leftmost) vertex of Vor(f) (resp. Vor(d)). Since the common edge between Vor(f) and Vor(g) is on $B_{f, g}$, from the definition and convexity of Voronoi regions, $B_{f, g}$ properly intersects Vor(d). See the bottom of Fig. 4. Thus, $B_{f, g}$ intersects $B_{b, d}$ at a point that is to the right of w. Since Vor(f) is vertically above $B_{f, g}$, it is above $B_{b, d}$, too. Then, ${{\mathcal {R}}}$ is vertically above $B_{b, d}$. In the case that f is not adjacent to d, a similar argument on each pair of consecutive vertices of SA[f, b) can show that ${{\mathcal {R}}}$ is vertically above $B_{b, d}$. Our claim is thus proved.

From the convexity of S, all regions of Vor(S) are unbounded. From our claim, all the regions Vor(p), $p \in SB[e, b] \cap S$, then intersect $B_{b, d}$. Since bi is vertically below $B_{b, d}$, it intersects regions Vor(p), $p \in SB[e, b] \cap S$, too.

Let $u, v \in S$ be the points immediately before and after e in SB[a, b], respectively. (Note that u and v may be identical to c and b, respectively.) Since $v \in SB[e, b]$, segment bi then intersects the edge between Vor(e) and Vor(v) at a point, say, $o'$. See Fig. 4. Let D be the circle of radius $|o' e|$, centered at point $o'$.

We now show that i is on or outside of D. Since $o'$ is an interior point of the edge between Vor(e) and Vor(v), except for e and v, all other vertices of S are outside of D (de Berg et al. 2008). Thus, the radius of D is smaller than that of C. Since $o'$ and e are inside and outside of C respectively, C and D intersect. Denote by l and r the left and right intersection points between C and D, respectively. See Fig. 4. The circular sector of C bounded by ol, or and the arc $\widehat{l r}$ of C, which is to right of the line through a and l, then contains point $o'$. So, $o'$ is to the right of the line through a and l.

Consider the tangent from a downward to D. Denote by t the found tangent point, see Fig. 4. Since l is the left common point of C and D, point t is to the left of the line through a and l, and lies in the interior of C. Then, point t is on or vertically below bi; otherwise, $\angle a t o' > \angle a i o' = \pi /2$, a contradiction. Hence, at intersects bi, and i is on or outside of D. The intersection point of $B_{i, e}$ with bi is thus to the left of or identical to $o'$.

Lemma 2 can then be applied to the collection of the circles, which are centered on bi and pass through the point pair (i, e) and all pairs of consecutive vertices of SB[e, b]. Therefore, all points of SB[e, b] are contained in H. Since any point of SB[a, b] is to the right of (or on) the line through a and i, chain SB[a, b] is then contained in the region bounded by ab, ai and H. See Fig. 4.

4.2 Bounding the total length of SB[ab]

Let $\alpha = \angle a b i$, $0< \alpha < \pi /2$. Denote by k the intersection point of H with the horizontal line through i. Then, $\angle b k i = \pi /2$ and $\angle b i k = \alpha$. We distinguish the following situations.

Case 1. $\pi /4 \le \alpha < \pi /2$. In this case, $|a i| = \sin (\alpha ) |a b|$ and $|b i| = \cos (\alpha ) |a b|$. See Fig. 5. A simple argument (as in Hershberger and Suri 1998) then shows that the length of SB[a, b] is less than $(\sin (\alpha ) + \pi \cos (\alpha )/2) | a b |$. Thus, we have (i) $|DT(a, b)| \le |SB[a, b]| \le (\sin (\alpha ) + \pi \cos (\alpha )/2) | a b |$.

Fig. 5

Illustrating the case $\alpha \ge \pi /4$

Case 2. $0< \alpha < \pi /4$. We further distinguish two different situations.

Case 2.1. The whole chain SB[a, b] is vertically above the line through i and k. In this case, SB[a, b] is contained in the convex region bounded by ba, ai, ik and the arc $\widehat{k b}$ of H. Since $|i k| = \cos ^2 (\alpha ) |a b|$ and $|\widehat{k b}| = \alpha \cos (\alpha ) |a b|$, we have (ii) $|DT(a, b)| \le |SB[a, b]| \le (\sin (\alpha ) + \cos (\alpha ) (\cos (\alpha ) + \alpha )) | a b |$.

Case 2.2. A portion of SB[a, b] is vertically below the line through i and k. To bound the total length of SB[a, b], we draw a tangent from point i to the portion of SB[a, b] contained in H. The tangent intersects H at a point, say, n ($\ne i$). Since n is vertically below ik, segment bn intersects C at a point, say, m ($\ne b$). See the left of Fig. 6.

Let $\gamma = \angle i b m$. Our second claim is that $\gamma > \alpha$. Since n and m are on H and C respectively, $\angle b n i = \angle b m a = \pi /2$. Two segments am and in are thus parallel. From the definition of point $c'$, segment in intersects $a c'$, and it thus intersects C at a point s ($\ne i$). See the left of Fig. 6. Hence, two circular arcs $\widehat{a i}$ and $\widehat{m s}$ of C are of the same length. Therefore, $\angle s b m = \alpha$, and $\gamma > \alpha$.

Let p be the point on H such that $\angle i b p = \alpha$, see Fig. 6. Since $\gamma > \alpha$, segment ip does not intersect SB[a, b]. If $\pi /6 \le \alpha < \pi /4$, then ip can be used to cut off its corresponding arc of H. Since $| i p| = \cos (\alpha ) \sin (\alpha ) |a b|$, we have (iii) $|DT(a, b)| \le |SB[a b]| \le (\sin (\alpha ) + \cos (\alpha ) (\sin (\alpha ) + \pi /2 - \alpha )) | a b |$.

Finally, consider the situation in which $\alpha < \pi /6$. Denote by $n'$ the intersection point of H with the tangent from p rightward to SB[a, b]. If $n'$ is vertically above ik, then $\angle p b n'> \pi /2 - 2 \alpha> \pi /6 > \alpha$. Thus, we can draw another chord $p n'$ of at least length $\cos (\alpha ) \sin (\alpha ) |a b|$ to cut off its corresponding arc of H. Suppose now that point $n'$ is vertically below ik, see the right of Fig. 6. Since $n'$ is vertically below ik, segment $b n'$ intersects C at a point $m'$ ($\ne b$), and segment $i n'$ intersects C at a point $s'$ ($\ne i$). See the right of Fig. 6. As discussed above, we also have $\angle p b n' > \alpha$. Again, the chord $p n'$ of at least length $\cos (\alpha ) \sin (\alpha ) |a b|$ can be introduced to cut off its corresponding arc of H. In summary, we have (iv) $|DT(a, b)| \le |SB[a b]| \le (\sin (\alpha ) + \cos (\alpha ) (2\sin (\alpha ) + \pi /2 - 2\alpha )) |a b|$.

Fig. 6

In the case $\alpha < \pi /6$, two shortcuts can be introduced in H

The above analysis handles all possible situations. Our proof is thus complete.

5 Proof of Lemma 4

From the lemma assumption, path dp(a, b) intersects segment ab an even number of times. Assume without loss of generality that the first and last segments of path dp(a, b) are vertically above ab. Assume also that SA[a, b] is not wholly contained in C; otherwise, $|DT(a, b)| / |a b| \le \pi /2$.

Let c be the first point of path dp(a, b) such that c and its next point on dp(a, b) are above and below ab, respectively. Also, let d be the last point of dp(a, b) such that d and its previous point on dp(a, b) are above and below ab, respectively. See Fig. 7. Then, c and d are contained in C (Dobkin et al. 1990). Note that SA(c, d) consists of at least two vertices; otherwise, since both Vor(c) and Vor(d) intersect ab, the only vertex of SA(c, d), c and d form a Delaunay triangle, contradicting the assumption made in Observation 1.

Without loss of generality, assume that uv is an edge of SA[c, d] such that u and v are outside of and inside C respectively, the slope of $B_{u, v}$ is positive and SA[v, b] is contained in C. See Fig. 7. (The other possible situation in which $u' v'$ is an edge of SA[c, d] such that $u'$ and $v'$ are inside and outside of C respectively, the slope of $B_{u', v'}$ is negative and $SA[a, u']$ is contained in C can be dealt with analogously.)

Let CH be the convex hull of the Voronoi vertices whose y-coordinates are positive. (Recall that a and b are on the x-axis.) Consider the tangent from a to CH, which is vertically above CH. See Fig. 7. Denote by i the intersection point of the tangent with C.

Fig. 7

Illustration of the proof of Lemma 4

We first claim that segment uv intersects ai, or it is vertically above the line through a and i. Assume that our claim is not true. So, uv and ai do not intersect, and both u and v are vertically below the line through a and i. Since the slope of $B_{u, v}$ is positive and v is contained in C, the line through u and v intersects bi and ab as well, contradicting the convexity of S. The claim is proved. From the convexity of S and the definition of uv, our claim also implies that $u.y > i.y$.

From the above claim and the definition of point v, segment ai properly intersects SA[a, b]. Hence, i is outside of CH(S), see Fig. 7. If ai intersects uv, then it intersects the edge between Vor(u) and Vor(v). Otherwise, uv is vertically above the line through a and i. As v lies in C, from the convexity of S, segment uv is to the left of the line through b and i. Since the Voronoi vertex on $B_{u, v}$ is contained in CH and ai is vertically above CH, segment ai thus intersects the edge between Vor(u) and Vor(v), too. From the definition of uv, we can conclude that ai intersects regions Vor(p), for all points $p \in SA[a, v] \cap S$.

Denote by H the semicircle of diameter ai, which is vertically above ai. As shown in Sect. 4, SA[a, u] (or SA[a, v] if v is vertically above ai) is completely contained in H. See Fig. 7. From the assumption that SA[v, b] is contained in C, chain SA[a, b] is contained in the region bounded by H, ab and the arc $\widehat{b i}$ of C.

Let $\beta = \angle b a i$. Denote by j and k the intersection points of C and H with the horizontal line through point i, respectively. See Fig. 7. Draw a tangent from i to the portion of SA[a, b], which is vertically above ai. Denote by n the intersection point of the tangent with H, see Fig. 7. Let m be the intersection point of C with an. As in the proof of Lemma 3, we can show that $\angle i a m > \beta$. Since $u.y > i.y$, we have $m.y > i.y$ ($= j.y$). Hence, $\angle b a i + \angle i a m + \angle a b j < \pi /2$. Since $\angle a b j = \beta$ and $\angle i a m > \beta$, we obtain $\beta < \pi /6$.

As in the proof of Lemma 3, a chain of two segments of length $\cos (\beta ) \sin (\beta ) |a b|$, starting from point i, can then be introduced in H. Moreover, since $\angle b a k = \pi /2$, segment ak is tangent to C and does not intersect SA[a, b]. Since $\beta < \pi /6$, the third cut ak of length $\cos (\beta ) \sin (\beta ) |a b|$ can be further introduced in H. By noticing that $|\widehat{b i}| = \beta |a b|$, we obtain $|DT(a, b)| \le (\beta +\cos (\beta )(3\sin (\beta )+\pi /2-3\beta ))|a b|$.

6 Concluding remarks

We have shown that the stretch factor of the Delaunay triangulation of a set of points in convex position is less than 1.84. The same stretch factor might hold for the set of points in general position, too. A new difficulty is that the considered path between a and b is generally not convex, which needs be examined more. Also, it is a challenging open problem to reduce the stretch factor of DT(S) further, even for a set of points in convex position, so as to close the gap to its lower bound (roughly about 1.60).