Dividing a plane of points into two equal halves [closed]

Question

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.

1. Create an arbitrary line in that plane. Project each point onto that line a.k.a for each point, get the closest point on that line to that point.

2. Order those points along the line in either direction, and choose a point on that line such that there is an equal number of points on the line in either direction.

3. Get the line perpendicular to the first line which passes through that point. This line will have half the original points on either side.

There are some cases to avoid when doing this. Most importantly, if all the point are themselves on a single line, don't choose a perpendicular line which passes through it. In fact, choose that line itself so you don't have to worry about projecting the points. In terms of the actual mathematics behind this, vector projections will be very useful.

This is a modification of Dividing a plane of points into two equal halves which allows for the case with overlapping points (in which case, it will say whether or not the answer exists).

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

This is O(N) unlike other proposed solutions.

Assuming a solution exists, the above method will probably terminate, though I don't have a proof.

Try the above algorithm a few times unless you detect overlapping points. If you detect a high number of overlapping points, you may be in for a rough ride, but there is a terribly inefficient brute-force solution that involves checking all possible angles:

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

A critical angle is defined as the angle which could possibly change the result (imagine the solution to a previous answer, rotate the entire set of points until one or more points swaps position with one or more other points, crossing the dividing line. There are only finitely many of these, and I think they are bounded by the number of points, so you're probably looking at something in the range O(N^2)-O(N^2 log(N)) if you have overlapping points, for a brute-force approach.

I'd guess that a good way is to sort/sequence/order the points (e.g. from left to right), and then choose a line which passes through (or between) the middle point[s] in the sequence.