Instance-optimal geometric algorithms

We prove the existence of an algorithm A for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A′ in a certain class A, the running time of A on the worst permutation of S for A is at most a constant factor times the running time of A′ on the worst permutation of S for A′. In fact, we can establish a stronger property: for every S and A′, the running time of A on S is at most a constant factor times the average running time of A′ over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, offline orthogonal range searching in 2-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d. The theory we develop also neatly reveals connections to entropy-dependent data structures, and yields as a byproduct new expected-case results, e.g., for on-line orthogonal range counting in 2-d.