Delaunay graphs are almost as good as complete graphs |
| |
Authors: | David P. Dobkin Steven J. Friedman Kenneth J. Supowit |
| |
Affiliation: | 1. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA
|
| |
Abstract: | ![]() LetS be any set ofN points in the plane and let DT(S) be the graph of the Delaunay triangulation ofS. For all pointsa andb ofS, letd(a, b) be the Euclidean distance froma tob and let DT(a, b) be the length of the shortest path in DT(S) froma tob. We show that there is a constantc (≤((1+√5)/2) π≈5.08) independent ofS andN such that $$frac{{DT(a,b)}}{{d(a,b)}}< c.$$ |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|