Instance-optimal geometric algorithms

Peyman Afshani Madalgo, Jérémy Barbay, Timothy M. Chan

Research output: Contribution to journalArticle

Abstract

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 (US)
Article number3
JournalJournal of the ACM
Volume64
Issue number1
DOIs
StatePublished - Mar 2017

Keywords

  • 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

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Instance-optimal geometric algorithms'. Together they form a unique fingerprint.

  • Cite this