Instance-optimal geometric algorithms

Abstract

We prove the existence of an algorithmAfor computing 2D or 3D convex hulls that is optimal forevery pointsetin the following sense: for every sequenceσofnpoints and for every algorithmA′in a certain classA,the running time ofAon inputσis at most a constant factor times the running time ofA′on the worstpossible permutation ofσforA′. In fact, we can establish a stronger property: for every sequenceσof pointsand every algorithmA′, the running time ofAonσis at most a constant factor times the average runningtime ofA′over all permutations ofσ. We call algorithms satisfying these propertiesinstance optimalintheorder-obliviousandrandom-ordersetting. Such instance-optimal algorithms simultaneously subsumeoutput-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that donot take advantage of the order of the input or that assume the input are given in a random order.The classAunder consideration consists of all algorithms in a decision tree model where the testsinvolve onlymultilinearfunctions with a constant number of arguments. To establish an instance-specificlower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] orChan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a newalgorithm.We further obtain instance-optimal results for a few other standard problems in computational geometry,such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromaticL∞-closepairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offlinehalf-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals aconnection to distribution-sensitive data structures and yields new results as a byproduct, for example, ononline orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.