[Solved]: Partition points in a plane with a straigth line

Problem Detail: 

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.

Asked By : rog4

Answered By : Karolis Juodelė

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. 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19299

3.2K people like this

 Download Related Notes/Documents