Name
Abstract | ||
|---|---|---|
Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in which the weight of every edge is its length. It has long been conjectured that the stretch factor in T of any pair p,p′∈P, which is the ratio of the length of the shortest path from p to p′ in T over the Euclidean distance ‖pp′‖, can be at most π/2≈1.5708. In this paper, we show how to construct point sets in convex position with stretch factor >1.5810 and in general position with stretch factor >1.5846. Furthermore, we show that a sufficiently large set of points drawn independently from any distribution will in the limit approach the worst-case stretch factor for that distribution. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.comgeo.2010.09.009 | Computational Geometry |
Keywords | DocType | Volume |
Dilation,Spanning ratio,Shortest path,Point configuration | Journal | 44 |
Issue | ISSN | Citations |
2 | 0925-7721 | 3 |
PageRank | References | Authors |
0.47 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prosenjit K. Bose | 1 | 2336 | 293.75 |
| Luc Devroye | 2 | 819 | 214.10 |
| Maarten Löffler | 3 | 551 | 62.87 |
| Jack Snoeyink | 4 | 2842 | 231.68 |
| Vishal Verma | 5 | 59 | 5.73 |