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 maximum running time of A on input 〈s1,..., sn 〉 is at most a constant factor times the max-imum running time of A ′ on 〈s1,..., sn〉, where the maximum is taken over all permutations 〈s1,..., sn〉 of S. In fact, we can establish a stronger property: for every S and A′, the maximum running time of A 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