On the stretch factor of Delaunay triangulations of points in convex position |
| |
Authors: | Shiliang Cui Iyad A. Kanj Ge Xia |
| |
Affiliation: | a Wharton OPIM, University of Pennsylvania, 3730 Walnut Street, Philadelphia, PA 19104, United States b School of Computing, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604, United States c Department of Computer Science, Lafayette College, Easton, PA 18042, United States |
| |
Abstract: | 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|. Keil and Gutwin in 1989 [11] proved that the stretch factor of the Delaunay triangulation of a set of points S in the plane is at most 2π/(3cos(π/6))≈2.42. Improving on this upper bound remains an intriguing open problem in computational geometry.In this paper we consider the special case when the points in S are in convex position. We prove that in this case the stretch factor of the Delaunay triangulation of S is at most ρ=2.33. |
| |
Keywords: | Delaunay triangulation Convex position Stretch factor/dilation |
本文献已被 ScienceDirect 等数据库收录! |
|