Instance-optimal geometric algorithms

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review



  • Peyman Afshani Madalgo
  • Jérémy Barbay, Departamento de Ciencias de la Computacion (DCC), Universidad Austral de Chile
  • ,
  • Timothy M. Chan, University of Waterloo, Ontario

We prove the existence of an algorithm Afor computing 2D or 3D 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 running time of A′ on the worst possible permutation of σ for A′. In fact, we can 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 are 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 2D 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 3D 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 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L8-close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.

Original languageEnglish
Article number3
JournalJournal of the ACM
Publication statusPublished - 1 Mar 2017

    Research areas

  • Adaptive algorithms, Computational geometry, Convex hull, Decision trees, Distribution-sensitive data structures, Instance optimality, Line segment intersection, Lower bounds, Maxima, Orthogonal range searching, Output sensitivity, Partition trees, Point location

See relations at Aarhus University Citationformats

ID: 118499830