  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
sequence $\sigma$ of $n$ points and for every algorithm $A'$ in a certain class
$\mathcal{A}$, the running time of $A$ on input $\sigma$ is at most a constant
factor times the maximum running time of $A'$ on the worst possible permutation
of $\sigma$ for $A'$. We establish a stronger property: for every sequence
$\sigma$ of points and every algorithm $A'$, the running time of $A$ on
$\sigma$ is at most a constant factor times the average running time of $A'$
over all permutations of $\sigma$. 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 $\mathcal{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 a new 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. Our framework also reveals connection to distribution-sensitive data
structures and yields new results as a byproduct, for example, on on-line
orthogonal range searching in 2-d and on-line halfspace range reporting in 2-d
and 3-d.
