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.

Improve this question
$\endgroup$
2
  • 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
    Commented Dec 26, 2013 at 13:27
  • $\begingroup$ @Louis: why should a vertical line give the best possible split? $\endgroup$
    – JeffE
    Commented Dec 28, 2013 at 16:19

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

Your Answer

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

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