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 -