## Abstract

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(n logn) expected time using only O(1) extra space; this improves the previous O(n log^{3} n) bound by Brönnimann, Chan, and Chen (2004) [10]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(n logn + K) expected running time for output size K, improving the previous O(n log ^{2} n + K) bound by Vahrenhold (2007) [42]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) [33] for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Mølhave, and Zeh (2008) [3]. Our results are all obtained by standard random sampling techniques, with some interesting twists.

Original language | English (US) |
---|---|

Pages (from-to) | 636-646 |

Number of pages | 11 |

Journal | Computational Geometry: Theory and Applications |

Volume | 43 |

Issue number | 8 |

DOIs | |

State | Published - Oct 2010 |

Externally published | Yes |

## Keywords

- Cache-oblivious algorithms
- Convex hulls
- In-place algorithms
- Segment intersection
- Voronoi diagrams

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics