@inproceedings{dc5e9ae353de4c4db145b16a6b8fac0f,
title = "DELAUNAY GRAPHS ARE ALMOST AS GOOD AS COMPLETE GRAPHS.",
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 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.",
author = "Dobkin, \{David P.\} and Friedman, \{Steven J.\} and Supowit, \{Kenneth J.\}",
year = "1987",
doi = "10.1109/sfcs.1987.18",
language = "American English",
isbn = "0818608072",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
publisher = "IEEE",
pages = "20--26",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
}