We prove the existence of an algorithm $A$ for computing 2-d or 3-d convex
hulls that is optimal for {em every point set/} in the following sense: for
every sequence $sigma$ of $n$ points and for every algorithm $A'$ in a certain
class $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'$. In fact, we can 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 {em instance-optimal/} in the {em order-oblivious/} and {em
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 {em 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, such as maxima in 2-d and 3-d, orthogonal line segment intersection
in 2-d, finding bichromatic $L_infty$-close pairs in 2-d, off-line orthogonal
range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line
halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.
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.