2
$\begingroup$

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.

Example

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?

$\endgroup$
1
  • $\begingroup$ Any constraints on the cardinalities of each set? Could one of them have just one point, for example? $\endgroup$ Aug 21, 2018 at 18:59

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Cool. But couldn't the line AB actually be a part of one of two convex hulls? $\endgroup$
    – Strahinja
    Aug 21, 2018 at 9:06
  • $\begingroup$ @StrahinjaRodic, exactly, it will be part of one of the two convex hulls; that's what I am aiming for. $\endgroup$
    – D.W.
    Aug 21, 2018 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.