Delaunay graphs are almost as good as complete graphs

David P. Dobkin, Steven J. Friedman, Kenneth J. Supowit

Research output: Contribution to journalArticlepeer-review

176 Scopus citations


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 (≤((1+√5)/2) π≈5.08) independent of S and N such that {Mathematical expression}

Original languageEnglish (US)
Pages (from-to)399-407
Number of pages9
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Delaunay graphs are almost as good as complete graphs'. Together they form a unique fingerprint.

Cite this