Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
