Delaunay triangulations in O(sort(n)) time and more

K. Buchin, W. Mulzer

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)

Samenvatting

We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where sort(n) is the time to sort n numbers. We assume that the word RAM supports the shuffle-operation in constant time; (ii) if we know the ordering of a planar point set in x- and in y-direction, its DT can be found by a randomized algebraic computation tree of expected linear depth; (iii) given a universe U of points in the plane, we construct a data structure D for Delaunay queries: for any P in U, D can find the DT of P in time O(|P|log log|U|); (iv) given a universe U of points in 3-space in general convex position, there is a data structure D for convex hull queries: for any P in U, D can find the convex hull of P in time O(|P|(log log|U|)2); (v) given a convex polytope in 3-space with n vertices which are colored with chi > 2 colors, we can split it into the convex hulls of the individual color classes in time O(n(log log n)2). The results (i)-(iii) generalize to higher dimensions. We need a wide range of techniques. Most prominently, we describe a reduction from DTs to nearest-neighbor graphs that relies on a new variant of randomized incremental constructions using dependent sampling.
Originele taal-2Engels
TitelProceedings 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS'09, Atlanta GA, USA, October 25-27, 2009)
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's139-148
ISBN van geprinte versie978-1-4244-5116-6
DOI's
StatusGepubliceerd - 2009

Vingerafdruk Duik in de onderzoeksthema's van 'Delaunay triangulations in O(sort(n)) time and more'. Samen vormen ze een unieke vingerafdruk.

Citeer dit