Is there always a straight line bisecting a finite set of points on a plane?

[Dragonfall]

How do you show that there is always a straight line bisecting a finite set of points on a plane?

 

[VKint]

Okay, I'll bite:

Let the set of points be S, let |S| = n, and suppose S is contained in some box B = [-a, a] X [-a, a] (S is finite, after all). Consider the set L of all lines that pass through at least 2 points in S. Then L is finite, so the set T consisting of all points p such that (1) for all lines l in L, p is not on l is nonempty, and (2) p is below and to the left of B (that is, $$p \in (-\infty, -a] \times (-\infty, -a]$$ ) is nonempty. Choose some p in T, and center a polar coordinate system at p, with polar axis parallel to the x-axis. For all q in S, define $$\theta(q)$$ as the modulus of q, considered as a point in this polar coordinate system (note that by the way we defined p, we always have $$\displaystyle 0 \leq \theta(q) \leq \frac{\pi}{2}$$). Define a discrete mapping $$\displaystyle f : \left[0, \frac{\pi}{2} \right] \to \mathbb{N}$$ by $$f(t) = | \{ q \in S \; : \; \theta(q) \leq t \} |$$. By the way we defined p, for all $$m \leq n$$, there exists some $$t_m$$ such that $$f(t_m) = n$$. Furthermore, we can consider the smallest such $$t_m$$; write this as $$\tilde{t}_m$$. If n is odd, then the line through p of slope
$$\displaystyle \tan(\tilde{t}_{\frac{1}{2} (n+1)})$$
does the trick; if n is even, then the line through p of slope
$$\displaystyle \tan(t_{\frac{1}{2} n})$$,
where $$t_{\frac{1}{2} n} \neq \tilde{t}_{\frac{1}{2} n}$$, suffices.

 

[Dragonfall]

(1) for all lines l in L, p is not on l is nonempty

I'm not sure what this means.

This can't be the easiest way to prove this. I can't figure out how to prove this. It's like a gap in my math education.

 

[VKint]

I'm not sure what this means.

Yeah, that sentence should have read:

"Then L is finite, so the set T consisting of all points p such that (1) for all lines l in L, p is not on l, and (2) p is below and to the left of B (that is, $$p \in (-\infty, -a] \times (-\infty, -a]$$ ) is nonempty." In other words,
$$\{p \; : \; \ell \in L \Rightarrow p \notin \ell \; \textrm{and} \; p \in (-\infty, -a] \times (-\infty, -a] \} \neq \emptyset$$.

It's actually a very easy proof; my post above just got a bit bogged down in formalism. The idea is that you select a point p far to the left and below all your points (again, call the set of all your points S), such that no line runs through p and any two points in S, and imagine rotating a line slowly through p. You then keep track of how many times the line has "hit" a point in S. The crucial idea is that you can arrange things so that this count always increases by just one at a time (this is why we chose p so that it's not collinear with any two points in S). Furthermore, at some point, the line has "hit" all the points in S, so the final count is |S|. There is therefore a time at which the line has hit exactly half of the points in S.

 

[HallsofIvy]

First, what do you mean by "bisecting a finite set of points"? In particular, if the line passes through some of the points and has the same number of points on each side, is that "bisecting"?

 

[maze]

If you can separate any 2 convex sets, then you can iteratively build up 2 balanced disjoint convex hulls of your points. This is actually pretty general - the Mazur separation lemma let's you separate convex sets in any Banach space.

here is a diagram:
http://img266.imageshack.us/img266/5483/convexs1.gif

 

[Dragonfall]

First, what do you mean by "bisecting a finite set of points"? In particular, if the line passes through some of the points and has the same number of points on each side, is that "bisecting"?

Bisecting in this case means dividing the plane into 2 half planes each of which contains an equal number of points. If a point is on the line then it counts towards both sides.

I guess that separation lemma could work, but what if there's an odd number of points? Then the bisecting line must pass through an odd number of points. Not sure if that's always possible.

 

[Dragonfall]

Yeah, that sentence should have read:

"Then L is finite, so the set T consisting of all points p such that (1) for all lines l in L, p is not on l, and (2) p is below and to the left of B (that is, $$p \in (-\infty, -a] \times (-\infty, -a]$$ ) is nonempty." In other words,
$$\{p \; : \; \ell \in L \Rightarrow p \notin \ell \; \textrm{and} \; p \in (-\infty, -a] \times (-\infty, -a] \} \neq \emptyset$$.

It's actually a very easy proof; my post above just got a bit bogged down in formalism. The idea is that you select a point p far to the left and below all your points (again, call the set of all your points S), such that no line runs through p and any two points in S, and imagine rotating a line slowly through p. You then keep track of how many times the line has "hit" a point in S. The crucial idea is that you can arrange things so that this count always increases by just one at a time (this is why we chose p so that it's not collinear with any two points in S). Furthermore, at some point, the line has "hit" all the points in S, so the final count is |S|. There is therefore a time at which the line has hit exactly half of the points in S.

Ok I think I got the idea. This could work.

 

[maze]

I guess that separation lemma could work, but what if there's an odd number of points? Then the bisecting line must pass through an odd number of points. Not sure if that's always possible.

ah yeah youre going to have to do some modification if you want it exactly half and half. If the number of points is odd, with this method one group will have exactly 1 more point than the other group.