Delaunay graphs are almost as good as complete graphs
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 20-26
- https://doi.org/10.1109/sfcs.1987.18
Abstract
Let S be any set of N points in the plane and let DT(S) be the graph of the Delaunay triangulation of S. For all points a and b of S, let d(a, b) be the Euclidean distance from a to b and let DT(a, b) be the length of the shortest path in DT(S) from a to b. We show that there is a constant c(≤ 1+√5/2 π ≈ 5.08) independent of S and N such that DT(a, b)/d(a, b) ≪ c.Keywords
This publication has 3 references indexed in Scilit:
- Shortest paths in euclidean graphsAlgorithmica, 1986
- There is a planar graph almost as good as the complete graphPublished by Association for Computing Machinery (ACM) ,1986
- Computational GeometryPublished by Springer Nature ,1985