$\begingroup$
$\endgroup$
2
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.
-
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– Louis2013年12月26日 13:27:13 +00:00Commented Dec 26, 2013 at 13:27
-
$\begingroup$ @Louis: why should a vertical line give the best possible split? $\endgroup$JeffE– JeffE2013年12月28日 16:19:12 +00:00Commented Dec 28, 2013 at 16:19
1 Answer 1
$\begingroup$
$\endgroup$
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.
answered Dec 28, 2013 at 20:30
Karolis Juodelė
3,69716 silver badges18 bronze badges
Explore related questions
See similar questions with these tags.