|
TR-113-87
Delaunay Graphs are Almost as Good as Complete Graphs |
|
| Authors: | Dobkin, David P., Friedman, Steven J., Supowit, Kenneth J. |
| Date: | June 1987 |
| Pages: | 18 |
| Download Formats: | [PDF] |
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. |
|