2010/06/02 by Prosenjit Bose, Luc Devroye, Bose, Prosenjit +7
Computer Science · Engineering · Environmental Science · Social Sciences · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Geographic Information Systems Studies #Remote Sensing and LiDAR Applications #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1006.0291
openalex publication_date 2010/06/02 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Consider the Delaunay triangulation T of a set P of points in the plane as a\nEuclidean graph, in which the weight of every edge is its length. It has long\nbeen conjectured that the dilation in T of any pair p, p \∈ P, which is the\nratio of the length of the shortest path from p to p' in T over the Euclidean\ndistance ||pp'||, can be at most \π/2 \≈ 1.5708. In this paper, we show\nhow to construct point sets in convex position with dilation > 1.5810 and in\ngeneral position with dilation > 1.5846. Furthermore, we show that a\nsufficiently large set of points drawn independently from any distribution will\nin the limit approach the worst-case dilation for that distribution.\n