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 expected time using only O(1) extra space; this improves the previous O(nlog3n) 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 expected running time for output size K, improving the previous O(nlog2n+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.