Different solution. It turns out that there's a lot of symmetry, and the answer is a lot simpler than I originally thought. The maximum number of things you can ever do is the minimum of the unique X's and unique Y's, which is O(NlogN) if you just want the result.

Every other shape is equivalent to a rectangle that contains the points, because it doesn't matter how many points you pull from the center of a rectangle, the order will never matter (if handled as below). **Any shape** that you pluck a point from now has one less unique X and one less unique Y, just like a rectangle.

So the optimal solution has nothing to do with connectedness. Pick **any** point that is on the edge of the smallest dimension (i.e. if len(unique-Xs)>len(unique-Ys), pick anything that has either maximum or minimum X). It doesn't matter how many connections it has, just which dimension is biggest, which can easily be done while looking at the sorted-unique lists created above. If you keep a unique-x and unique-y counter and decrement them when you delete all the unique nodes in that element of the list, then each deletion is O(1) and recalculating the lengths is O(1). So repeating this N times is at worst O(N), and the final complexity is O(NlogN) (due solely to the sorting).

You can pick **any** point along the shortest edge because:

- if there's only one on that edge, you better pick it now or something else will eliminate it
- if there's more than one on that edge, who cares, you will eliminate all of them with your pick anyways

Basically, you're maximizing "max(uniqX,uniqY)" at each point.

Update: IVlad caught an edge case:

If the dimensions are equal, take the edge with the least points. Even if they aren't equal, take the top or bottom of the unique-stack you're eliminating from that has the least points.

Case in point:

Turn 1:

- Points:
`(1, 2); (3, 5); (10, 5); (10, 2); (10, 3)`

- There are 3 unique X's:
`1, 3, 10`

- There are 3 unique Y's:
`2, 3, 5`

- The "bounding box" is
`(1,5),(10,5),(10,2),(1,2)`

Reaction 1:

- The "outer edge" (outermost uniqueX or uniqueY lists of points) that has the least points is the left. Basically, look at the sets of points in x=1,x=10 and y=2,y=5. The set for x=1 is the smallest: one point. Pick the only point for x=1 ->
`(1,2)`

.
- That also eliminates
`(10,2)`

.

Turn 2:

- Points:
`(3, 5); (10, 5); (10, 3)`

- There are 2 unique X's:
`3, 10`

- There are 2 unique Y's:
`3, 5`

- The "bounding box" is
`(3,5),(10,5),(10,3),(3,3)`

Reaction 2:

- The "edge" of the bounding box that has the least is either the bottom or the left. We reached the trivial case - 4 points means all edges are the outer edges. Eliminate one. Say
`(10,3)`

.
- That also eliminates
`(10,5)`

.

Turn 3:

Reaction 3: