0
$\begingroup$

Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned.

Is there an algorithm which, when given a ratio a/b, divides the plane with a straight line, so that the values of the points are distributed as close as possible to the given ratio?

Points may be on the dividing line, then the are counted to the 'left/upper' partition.

$\endgroup$
  • 1
    $\begingroup$ If all the points have distinct $x$ coordinates this is easy. Otherwise, think about how to arrange for this to be the case. $\endgroup$ – Louis Dec 26 '13 at 13:27
  • $\begingroup$ @Louis: why should a vertical line give the best possible split? $\endgroup$ – JeffE Dec 28 '13 at 16:19
1
$\begingroup$

There is a brute $O(n^3)$ algorithm.

There are $\binom n 2 = \frac {n(n-1)} 2$ lines over pairs of points. If a line goes over $k$ points, there are $2(k+1)$ ways to rotate the line by a negligible angle, so that no points go over it and each rotation partitions the $k$ points differently.

For each pair of vertices (v1, v2),
  rotate the space so that v1.y = v2.y = 0
  let UP be the sum of values of vertices with positive y
  let DOWN be the same for negative y
  let L be a list of vertices with y = 0, sorted by x

  For each of L.length+1 ways to cut L in two,
    let LEFT be the sum of values of vertices in L to the left of the cut
    let RIGHT be the same for vertices to the right

    check whether one of UP + LEFT, DOWN + RIGHT or UP + RIGHT, DOWN + LEFT
     is a better partition than your previous best.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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