Delaunay graphs are almost as good as complete graphs

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

doi:10.1007/BF02187801

Delaunay graphs are almost as good as complete graphs

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

Research output: Contribution to journal › Article › peer-review

182 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 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 language	English (US)
Pages (from-to)	399-407
Number of pages	9
Journal	Discrete & Computational Geometry
Volume	5
Issue number	1
DOIs	https://doi.org/10.1007/BF02187801
State	Published - Dec 1990

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1007/BF02187801

Cite this

@article{9104918808c54dd198ff35a6040befe0,

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 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}",

author = "Dobkin, {David P.} and Friedman, {Steven J.} and Supowit, {Kenneth J.}",

year = "1990",

month = dec,

doi = "10.1007/BF02187801",

language = "English (US)",

volume = "5",

pages = "399--407",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Delaunay graphs are almost as good as complete graphs

AU - Dobkin, David P.

AU - Friedman, Steven J.

AU - Supowit, Kenneth J.

PY - 1990/12

Y1 - 1990/12

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 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}

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 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}

UR - http://www.scopus.com/inward/record.url?scp=0000913745&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000913745&partnerID=8YFLogxK

U2 - 10.1007/BF02187801

DO - 10.1007/BF02187801

M3 - Article

AN - SCOPUS:0000913745

SN - 0179-5376

VL - 5

SP - 399

EP - 407

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

Delaunay graphs are almost as good as complete graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this