Nice point sets can have nasty delaunay triangulations

J. Erickson

doi:10.1145/378583.378636

Nice point sets can have nasty delaunay triangulations

Research output: Contribution to conference › Paper › peer-review

Abstract

We consider the complexity of Delaunay triangulations of sets of points in IR³ under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in IR³ with spread Δ has complexity Ω(min{Δ³,n Δ,n²}) and O(min{Δ⁴, n²}). For the case Δ = (√n), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

Original language	English (US)
Pages	96-105
Number of pages	10
DOIs	https://doi.org/10.1145/378583.378636
State	Published - 2001
Event	17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States Duration: Jun 3 2001 → Jun 5 2001

Other

Other	17th Annual Symposium on Computational Geometry (SCG'01)
Country	United States
City	Medford, MA
Period	6/3/01 → 6/5/01

Keywords

Delaunay triangulation
Lower bounds
Sample measure
Spread
Surface reconstruction
ε-sample

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/378583.378636

Fingerprint Dive into the research topics of 'Nice point sets can have nasty delaunay triangulations'. Together they form a unique fingerprint.

Cite this

@conference{6dfc15a4932742c68a0b9ddfef0e1b80,

title = "Nice point sets can have nasty delaunay triangulations",

abstract = "We consider the complexity of Delaunay triangulations of sets of points in IR3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in IR3 with spread Δ has complexity Ω(min{Δ3,n Δ,n2}) and O(min{Δ4, n2}). For the case Δ = (√n), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.",

keywords = "Delaunay triangulation, Lower bounds, Sample measure, Spread, Surface reconstruction, ε-sample",

author = "J. Erickson",

year = "2001",

doi = "10.1145/378583.378636",

language = "English (US)",

pages = "96--105",

}

TY - CONF

T1 - Nice point sets can have nasty delaunay triangulations

AU - Erickson, J.

PY - 2001

Y1 - 2001

N2 - We consider the complexity of Delaunay triangulations of sets of points in IR3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in IR3 with spread Δ has complexity Ω(min{Δ3,n Δ,n2}) and O(min{Δ4, n2}). For the case Δ = (√n), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

AB - We consider the complexity of Delaunay triangulations of sets of points in IR3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in IR3 with spread Δ has complexity Ω(min{Δ3,n Δ,n2}) and O(min{Δ4, n2}). For the case Δ = (√n), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

KW - Delaunay triangulation

KW - Lower bounds

KW - Sample measure

KW - Spread

KW - Surface reconstruction

KW - ε-sample

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

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

U2 - 10.1145/378583.378636

DO - 10.1145/378583.378636

M3 - Paper

AN - SCOPUS:0034832768

SP - 96

EP - 105

T2 - 17th Annual Symposium on Computational Geometry (SCG'01)

Y2 - 3 June 2001 through 5 June 2001

ER -