## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |

Pages | 129-138 |

Number of pages | 10 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States Duration: Oct 25 2009 → Oct 27 2009 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |
---|---|

Country/Territory | United States |

City | Atlanta, GA |

Period | 10/25/09 → 10/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)