Instance-optimal geometric algorithms

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 set S of n points and for every algorithm A′ in a certain class A, the running time of A on the worst permutation of S for A is at most a constant factor times the running time of A′ on the worst permutation of S for A′. In fact, we can establish a stronger property: for every S and A′, the running time of A on S is at most a constant factor times the average running time of A′ over all permutations of S. 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 an interesting 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, offline orthogonal range searching in 2-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d. The theory we develop also neatly reveals connections to entropy-dependent data structures, and yields as a byproduct new expected-case results, e.g., for on-line orthogonal range counting in 2-d.

Original languageEnglish (US)
Title of host publicationProceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Pages129-138
Number of pages10
DOIs
StatePublished - 2009
Externally publishedYes
Event50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States
Duration: Oct 25 2009Oct 27 2009

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Country/TerritoryUnited States
CityAtlanta, GA
Period10/25/0910/27/09

Keywords

  • Adaptive algorithms
  • Computational geometry
  • Convex hull
  • Decision trees
  • Entropy-sensitive data structures
  • Instance optimality
  • Lower bounds
  • Maxima
  • Orthogonal segment intersection
  • Output-sensitive algorithms
  • Point location

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

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

Cite this