TY - GEN
T1 - DELAUNAY GRAPHS ARE ALMOST AS GOOD AS COMPLETE GRAPHS.
AU - Dobkin, David P.
AU - Friedman, Steven J.
AU - Supowit, Kenneth J.
PY - 1987
Y1 - 1987
N2 - 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 length of the shortest path in DT(S) from a to b. We show that there is a constant c ( less than equivalent to (1 plus ROOT 5) pi /2 approximately equals 5. 08) independent of S and N such that DT(a, b)/d(a, b) less than c.
AB - 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 length of the shortest path in DT(S) from a to b. We show that there is a constant c ( less than equivalent to (1 plus ROOT 5) pi /2 approximately equals 5. 08) independent of S and N such that DT(a, b)/d(a, b) less than c.
UR - http://www.scopus.com/inward/record.url?scp=0023535759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023535759&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1987.18
DO - 10.1109/sfcs.1987.18
M3 - Conference contribution
AN - SCOPUS:0023535759
SN - 0818608072
SN - 9780818608070
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 20
EP - 26
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -