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. 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. 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

Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$. Then you can compute the convex hulls of these two sets and you can find the distance between the convex hulls in $O(n)$ time, for a particular split (use a Graham scan; pre-sort the points once). Since there are ${n \choose 2} = O(n^2)$ ways to choose $A,B$, this immediately gives a $O(n^3)$ time algorithm.

In fact, you don't need to compute both convex hulls. It suffices to find the points that are closest (on each side) to the line $AB$. It might be possible to do this faster than $O(n)$ time, which would improve the overall running time. I think it suffices to compute a Voronoi diagram of all the points (a one-time $O(n \log n)$ time cost), then find all Voronoi cells that the line $AB$ goes through. I don't know whether the worst-case complexity will be less than $O(n)$ but I bet in practice this will often lead to significant speedups.