Beyond Worst-Case Analysis (Lecture 2: Instance-Optimal Geometric Algorithms)
Tim Roughgarden Lectures · 71:16
The lecture shows that the classic 1985 Kirkpatrick–Seidel divide-and-conquer algorithm for the 2D maxima (Pareto frontier) problem is instance-optimal up to a constant factor among “natural” comparison-based algorith...