Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection

Timothy M. Chan, Eric Y. Chen

Research output: Contribution to journalArticlepeer-review

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 log3 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 languageEnglish (US)
Pages (from-to)636-646
Number of pages11
JournalComputational Geometry: Theory and Applications
Volume43
Issue number8
DOIs
StatePublished - Oct 2010
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection'. Together they form a unique fingerprint.

Cite this