Instance Optimal Geometric Algorithms

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

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 $\sigma$ of $n$ points an…