I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other side.

The points are unevenly placed and the line must not pass through any of the points.

Can any one give any approach to solve the problem? Analysis of the algorithm is appreciated.

Hints: Count the points, use medians.

The number of points is assumed to be even.


One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that direction. However, if you choose a "generic" direction then this won't happen (assuming that the points are distinct). Since there are linear time median algorithms, this is an $O(n)$ algorithm. Using the randomized quickselect algorithm, you get a practical linear time algorithm.

  • $\begingroup$ I feel this does a better job of explaining the same idea. "direction" instead of "line" had me all confused. $\endgroup$ – Dukeling May 18 '13 at 18:40

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.