Dividing a plane of points into two equal halves

Question

Given a 2 dimensional plane in which there are n points. I need to generate the equation of a line that divides the plane such that there are n/2 points on one side and n/2 points on the other.

Answer 1

I have assumed the points are distinct, otherwise there might not even be such a line.

If points are distinct, then such a line always exists and is possible to find using a deterministic O(nlogn) time algorithm.

Say the points are P1, P2, ..., P2n. Assume they are not all on the same line. If they were, then we can easily form the splitting line.

First translate the points so that all the co-ordinates (x and y) are positive.

Now suppose we magically had a point Q on the y-axis such that no line formed by those points (i.e. any infinite line Pi-Pj) passes through Q.

Now since Q does not lie within the convex hull of the points, we can easily see that we can order the points by a rotating line passing through Q. For some angle of rotation, half the points will lie on one side and the other half will lie on the other of this rotating line, or, in other words, if we consider the points being sorted by the slope of the line Pi-Q, we could pick a slope between the (median)th and (median+1)th points. This selection can be done in O(n) time by any linear time selection algorithm without any need for actually sorting the points.

Now to pick the point Q.

Say Q was (0,b).

Suppose Q was collinear with P1 (x1,y1) and P2 (x2,y2).

Then we have that

(y1-b)/x1 = (y2-b)/x2 (note we translated the points so that xi > 0).

Solving for b gives

b = (x1y2 - y1x2)/(x1-x2)

(Note, if x1 = x2, then P1 and P2 cannot be collinear with a point on the Y axis).

Consider |b|.

|b| = |x1y2 - y1x2| / |x1 -x2|

Now let the xmax be the x-coordinate of the rightmost point and ymax the co-ordinate of the topmost.

Also let D be the smallest non-zero x-coordinate difference between two points (this exists, as not all xis are same, as not all points are collinear).

Then we have that |b| <= xmax*ymax/D.

Thus, pick our point Q (0,b) to be such that |b| > b_0 = xmax*ymax/D

D can be found in O(nlogn) time.

The magnitude of b_0 can get quite large and we might have to deal with precision issues.

Of course, a better option is to pick Q randomly! With probability 1, you will find the point you need, thus making the expected running time O(n).

If we could find a way to pick Q in O(n) time (by finding some other criterion), then we can make this algorithm run in O(n) time.