DELAUNAY GRAPHS ARE ALMOST AS GOOD AS COMPLETE GRAPHS.

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages20-26
Number of pages7
ISBN (Print)0818608072, 9780818608070
DOIs
StatePublished - 1987

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'DELAUNAY GRAPHS ARE ALMOST AS GOOD AS COMPLETE GRAPHS.'. Together they form a unique fingerprint.

Cite this