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.