Minimum distance between two convex hulls maximized

Question

I want to implement a program that splits a set S of n points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized.

It should be done in O(n^3).

I have several ideas but I'm not sure whether they are correct:
1. Idea: I sort points by X and then for each two points I find the distance but only if there's no any other point between them. Then I choose the closest point to the first one on the left and the closest point to the second one on the right (first point would be part of the first polygon and second one of the second polygon). Then I find distance between point and line, line and line, line and point and point and point(but I already know that). That's how i find the maximal distance and then with Graham scan I create a convex hull. I repeat everything for Y, because maximal distance could be on Y, not on X.
2. Idea: I sort points by X and then create a convex hull for first 3 and another convex hull for other points. Then find a minimum distance between these two hulls. I save the distance and if it's greater than distance i saved before i overwrite it and remember polygons. And last step is when only 3 points are left for the second convex hull. Then I do all these steps for Y.

What do you guys think about my ideas? Do you have any improvements or maybe another, better idea?

Answer 1

O(N^3) is possible using the separating axis theorem if you are clever. See this first: https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169

Now if the distance between two convex hulls is x, then there is an axis along which the points in those hulls are separated by x. Conversely, if there is a gap of x between the projections of the points along any axis, then the convex hulls of the points on either side of that gap will be separated by at least x.

So, if you find the axis that has the largest gap between points, then the groups of points on either side of that gap will have the largest possible distance between their convex hulls.

The good news is that there are only O(N^2) possible best axes. The distance between two convex hulls will either be the distance between two points (corners) in the hulls, or the distance between a point in one and a line in the other. In the first case the corresponding separating axis will be along line between the points in either hull. In the second case the separating axis will be perpendicular to the line in one hull. Either way the axis is either perpendicular or parallel to the line between two points, and there are only O(N^2) such directions.

So, you can just try all of the possible directions, sort the points along each axis and find the biggest gap between them. Total time is... O(N^3 * log N) Not quite good enough.

In order to get that down to O(N^2) you'd have to get the sorting down to O(N) per axis. It turns out that that's actually no problem. If you go though all the possible axis directions in slope order, then the total number of inversions you see (pairs of points that change order) along the way is O(N^2). If you use insertion sort to resort the points for each axis, then the total amount of moves it will make is proportional to the number of inversions it does. That will be O(N^2) all together. Adding that with the linear scan part for each direction gives O(N^3) total work.