Minimum distance between two convex hulls maximized
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.