2015/05/01 by Peyman Afshani, Afshani, Peyman, Jérémy Barbay +3
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1505.00184
28 pages in fullpage
arxiv created 2015/05/01 · arxiv updated 2015/05/04
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 σ of n points and for every algorithm A' in a certain class A, the running time of A on input σ is at most a constant factor times the maximum running time of A' on the worst possible permutation of σ for A'. We establish a stronger property: for every sequence σ of points and every algorithm A', the running time of A on σ is at most a constant factor times the average running time of A' over all permutations of σ. 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 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.