Enclosure Area

This problem asks us to find a convex hull of points and then select from a set of points the single point not on the previous hull which would increase the area of the updated hull the most.

It makes sense that we have to calculate the convex hull up front.

We can then simply try adding all possible points and recomputing the hull. Right?

100k points? nlogn to recompute the hull? 100k times? Yeah, not going to cut it.

Judging by the 100k number, we are going to need to do each evaluation in sub-linear time (because if it were linear for each point, then we're at O(n^2)....).

For now, lets assume all the trial points are external to the convex hull.

Lets think about what happens when we recompute a convex hull with a new point P. Most of the hull will be the same, and at some point U, a new edge will deviate from the old hull to P, and then from P we'll head back towards the hull and rejoin at point V.

Intuition: if we progress around points P in a counter-clockwise direction, then the points U and V will also move in the same direction. This means to evaluate all points P, we only need to evaluate U and V to see if they are still the right deviation points, or whether we need to increment them to the next points on the hull. The key win here, though, is that since both are monotonic, we do just a single walk around the hull to evaluate ALL P points, meaning the evaluation of each P is sublinear....exactly what we needed.

So how do we calculate U and V?

Suppose we choose some start point P, say min X. The point U will be the points U and V will be the points on the hull which make the maximum possible angles (or alternatively, the furthest such that we are making the proper direction turn once we rejoin the hull). Once those are identified, when we select a new P, we increment U if we have to, and increment V if we can.

That leads to the following algorithm:

1. Compute initial convex hull and area
2. Select some point A on the hull, say, minimum x
3. Sort all points P (remember, still assumed to be external) based on angle to A
4. start with the minimum X of those P
5. initialize U and V to A.
   1. while the angle APV is increasing, move V to the next point on the hull, V'
      • Compute the incremental area by Adding VPV'
   2. while the angle APU is decreasing, move U to the previous most point on the hull, U'
      • Compute the incremental area by adding UPU'
6. Increment point P to P'
   1. Compute new area of current hull by subtracting UPV and adding UP'V
      • Key, or there would be no way to compute the incremental area when adjusting U and V!
   2. increment V as above, computing incremental area, stopping when the angle goes from increasing to decreasing
   3. increment U as above, computing the incremental area, stopping when the angle starts decreasing
7. When all P have been evaluated, return area of best P

So we still have to deal with points inside the hull. Getting rid of them in the normal way (iterating over all edges of the hull and checking whether the point lies to the same direction of all of them..CROSS PRODUCTS!) won't work because that makes n^2. The classic solution here is to have a sorted list of the segments of the convex hull by angle to some fixed point (say, A above). When evaluating a point for inclusion, we only have to calculate it's angle to A to determine which segment it would project on to (when viewed from A). We can then evaluate which is closer, that particular segment, or A. This gives logn time for arbitrary points, or given we're already walking in A angle order, amortizes to constant time.

Pitfall: the point P' could be all the way on the other side of the hull, so the angle VP'V' may need to decrease before it increases. One way to deal with this: Check that V is not already at it's optimal point by checking that angle decreases in either direction, and then incrementing V until it decreases AFTER having increased at least once.

Pitfall: ensure the areas you calculate have the proper sign! You can do this either with all positive area, or with some negative area. You just have to be consistent.