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

Delaunay triangulations in O (sort( n )) time and more,10.1145/1944345.1944347,Journal of The ACM,Kevin Buchin,Wolfgang Mulzer

Delaunay triangulations in O (sort( n )) time and more  
BibTex | RIS | RefWorks Download
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 ⊆ U, D can find the DT of P in expected 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 ⊆ U, D can find the convex hull of P in expected time O(|P| (log log |U|)2); (v) given a convex polytope in 3-space with n vertices which are colored with χ ≥ 2 colors, we can split it into the convex hulls of the individual color classes in expected time O(n (log log n)2). The results (i)--(iii) generalize to higher dimensions, where the expected running time now also depends on the complexity of the resulting DT. 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.
Journal: Journal of The ACM - JACM , vol. 58, no. 2, pp. 1-27, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.