Delaunay Graphs are Almost as Good as Complete Graphs

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(leq {1+sqrt5}/2)x pi approx 5.08)independent of S and N such that DT(a,b)/d(a,b) less than c.