Delaunay Graphs are Almost as Good as Complete Graphs
Report ID: TR-113-87Author: Friedman, Steven J. / Dobkin, David P. / Supowit, Kenneth J.
Date: 1987-06-00
Pages: 18
Download Formats: |PDF|
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.