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

摘要

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.