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.

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

There are obvious cases where no solution is possible. E.g. when you have three heaps of points. One point at location A, Two points at location B, and five points at location C.

If you expect some decent distribution, you can probably get a good result with tlayton's algorithm. To select the initial line slant, you could determine the extent of the whole point set, and choose the angle of the largest diagonal.

Solution 5

The median equally divides a set of numbers in the manner similar to what you're trying to accomplish, and it can be computed in O(n) time using a selection algorithm (the writeup in Cormen et al is better, so you may want to look there instead). So, find the median of your x values M_x (or your y values M_y if you prefer) and set x = M_x (or y = M_y) and that line will be axially aligned and split your points equally.

If the nature of your problem requires that no more than one point lies on the line (if you have an odd number of points in your set, at least one of them will be on the line) and you discover that's what's happened (or you just want to guard against the possibility), rotate all of your points by some random angle, θ, and compute the median of the rotated points. You then rotate the median line you computed by -θ and it will evenly divide points.

The likelihood of randomly choosing θ such that the problem manifests itself again is very small with a finite number of points, but if it does, try again with a different θ.

View more solutions

Comments

[mousey]

if all points lie on a vertical line it doesnt work

[BlueRaja - Danny Pflughoeft]

What if all the points have the same x value? Also, if exactly half are on one side and half on the other, the line can't pass through any of them (maybe one, if n is odd).

[BlueRaja - Danny Pflughoeft]

Same problem as Chris' solution, multiple points could have same projection.

[tlayton]

That's only an issue if those points are the two bracketing the middle. In that case, choose a different line in part 1.

[BlueRaja - Danny Pflughoeft]

So you are suggesting "choose a random line, see if you can fit it to split the set in two, otherwise choose another random line?"

[BlueRaja - Danny Pflughoeft]

I don't find it obvious - in fact, I don't think it's true. I can't imagine a scenario where you couldn't divide C in half such that A and three points from C are in one half, B and two points from C are in the other.

[relet]

You cannot divide C in half. Either all five points are on the line, or they are not.

[tlayton]

The final resulting line will be perpendicular to the line you choose. So yes, but the new line will give you a different result. But if you encounter this problem, it means that that particular set of points can't be split like this with a line in that particular direction.

[BlueRaja - Danny Pflughoeft]

Oh I see what you are saying - I was under the impression all n points were distinct.

[relet]

Heh, indeed. That needs to be clarified. I was thinking of n points as distinct objects in a list, which may refer to the same coordinates. :)

[Admin]

There is a deterministic way (though O(nlogn) currently) to find without any guessing (see my answer). Guessing is more practical though, as the chances of getting a bad guess are negligible.

[Admin]

@Rudi-moore: Can you please explain what you are trying to do, rather than just give the steps? It is a bit hard to read. Also, few questions, what happens if a_g = b_h? Also, is it possible that the line QR divides points to the right of points in step 3? (i.e x-cordinate > x_a) in which case you might not get an n/2-n/2 split?

[Admin]

@Rudi-moore: Rotating the line around Q might not work. I believe (though not completely sure) we can give you a configuration of points such that no line through Q will make an even split. You seem to be completely ignoring the points to the right of the vertical line. Also, the case when a_h = b_h and c=0 is undiscussed.

[Admin]

We can assume x1 =/= x2 as then the line will be parallel to the y-axis.

[BlueRaja - Danny Pflughoeft]

@M: Yep; that's essentially the same thing (it wouldn't necessarily be true if the points weren't distinct)

[rudi-moore]

@M Sorry i'm not a native speaker, mabye that makes it a bit harder to understand. I edited the post and hope to make it clearer with an example. For your question: if a_g = b_h you can choose P_g or P_h. It doesn't matter. Both will generate the same line. It is not possible that QR divides points on the right side, if it would another R would have been choosen. I'm not completly ignoring points on the right side. Only in the first steps. c=0 is only problematically if more than n/2 points are in the middle and in that case n/2 points from the middle go to left side.

[Admin]

@Rudi-moore: Good job! This looks right to me. It was simpler than I imagined it would be. +1.

[Admin]

@mousey, @BlueRaja: I suggest you take a look at this answer. I believe this works! I think this derserves to be the accepted answer.

[ninjagecko]

This is the easiest to code. As long as you choose a random line, you have almost NO chance (LITERALLY, YOU HAVE 0% CHANCE, though numerical precision may be an issue) of running into the colinearity issue unless some points are overlapping (no overlapping points was also an assumption made in the chosen answer). Also this an O(n log(n)) solution unlike was implied by "Moron". Thus I would choose this solution over the chosen answer.

[ninjagecko]

However, an O(N) solution is possible, see my solution.