CS264: Beyond Worst-Case Analysis Lecture #2: Instance-Optimal Geometric Algorithms∗

This lectures touches on results of Afshani, Barbay, and Chan [1], who give a number of interesting instance-optimality results for fundamental problems in computational geometry, namely the problems of computing the maximal points or the convex hull of a point set in two or three dimensions. These are perhaps the most compelling examples to date of instance-optimal algorithms when the cost measure cost(A, z) is the running time of an algorithm. We discuss only their simplest result, for the following 2D Maxima problem; this suffices to showcase most of the paper’s main ideas. 2 The Problem and the Goal The input is n points in the plane. Assume for simplicity that all coordinate values are distinct (this is not important). Say that x is dominated by y if y is bigger in both coordinates (i.e., lies to the northeast of x). A maximal point is one not dominated by any other.1 The goal is to compute the set of all maxima of the point set. See Figure 1. We use the comparison model, familiar from the study of sorting algorithms. That is, we assume that an algorithm can access the input only through comparisons of coordinate values, and define cost(A, z) as the number of comparisons that the algorithm A needs to compute the correct answer for the input z.2