### Abstract

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 subset P of U, D can find the DT of P in time O(|P| loglog |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 subset P of 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 k > 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.

Original language | English |
---|---|

Pages (from-to) | 6:1-6:27 |

Number of pages | 27 |

Journal | Journal of the ACM |

Volume | 58 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2011 |

## Fingerprint Dive into the research topics of 'Delaunay triangulations in O(sort(n)) time and more'. Together they form a unique fingerprint.

## Cite this

Buchin, K., & Mulzer, W. (2011). Delaunay triangulations in O(sort(n)) time and more.

*Journal of the ACM*,*58*(2), 6:1-6:27. https://doi.org/10.1145/1944345.1944347