CROWNS - Editorial






Try all ordered pairs of points p,q as the first and last points in the crown (the endpoints of the “base” of the crown). Translate the points so p is at the origin and then rotate so q is on the positive x axis. Now, discard all points with non-positive y coordinate, x coordinates at most 0 or at least the x coordinate of q (after rotating, of course). Finally, among these points keep only the one with minimum y coordinate among all points that share the same x coordinate. Sort these remaining points by their x coordinate.

For each point r (including the endpoints p,q), let U[r] be the maximum area of a crown that involves point r where the point after r is above r and let D[r] be the maximum area of a crown that involves point r where the point after r is below r. The largest area of a crown involving base points p,q is then U[p]. The base case is D[q] = infeasible and U[q] = 0, the idea being that the point before q in a crown must decrease to q. From an arbitrary point r, we compute D[r] by trying all points s whose x coordinate is greater than r and such that there is no other point lying below the line formed by the line r-s. The value of D[r] is the maximum of U[s] + (s.x-r.x) * (r.y+s.y)/2 over all such points s. U[r] is computed similarly. We can calculate D[r] in linear time given that the coordinates are sorted according to x coordinate by keeping track of the least slope of a line between r and a point seen so far in our sweep. Then we can determine, in constant time, whether a given point s has a point under the line r-s or not. In fact, it’s not too hard to see that both U[r] and D[r] can be computed in a single sweep. The running time is O(n^4) since there are O(n^2) pairs of points to try, O(n) values D[r] and U[r] to compute, and computing each such value takes O(n) time.

One final note is that there is always a solution given that no three points are collinear. To see this, note that we can triangulate the set of points. Any triangle is a feasible crown by selecting the longest side to be a base.


Can be found here.


Can be found here.