- #1

- 1,030

- 4

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

- Thread starter Dragonfall
- Start date

- #1

- 1,030

- 4

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

- #2

- 139

- 12

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, [tex] p \in (-\infty, -a] \times (-\infty, -a] [/tex] ) 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 [tex] \theta(q) [/tex] 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 [tex] \displaystyle 0 \leq \theta(q) \leq \frac{\pi}{2} [/tex]). Define a discrete mapping [tex]\displaystyle f : \left[0, \frac{\pi}{2} \right] \to \mathbb{N} [/tex] by [tex] f(t) = | \{ q \in S \; : \; \theta(q) \leq t \} | [/tex]. By the way we defined p, for all [tex] m \leq n [/tex], there exists some [tex] t_m [/tex] such that [tex] f(t_m) = n [/tex]. Furthermore, we can consider the

[tex] \displaystyle \tan(\tilde{t}_{\frac{1}{2} (n+1)}) [/tex]

does the trick; if n is even, then the line through p of slope

[tex] \displaystyle \tan(t_{\frac{1}{2} n}) [/tex],

where [tex] t_{\frac{1}{2} n} \neq \tilde{t}_{\frac{1}{2} n} [/tex], suffices.

- #3

- 1,030

- 4

I'm not sure what this means.(1) for all lines l in L, p is not on l is nonempty

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.

- #4

- 139

- 12

Yeah, that sentence should have read:I'm not sure what this means.

"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, [tex] p \in (-\infty, -a] \times (-\infty, -a] [/tex] ) is nonempty." In other words,

[tex] \{p \; : \; \ell \in L \Rightarrow p \notin \ell \; \textrm{and} \; p \in (-\infty, -a] \times (-\infty, -a] \} \neq \emptyset [/tex].

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.

- #5

HallsofIvy

Science Advisor

Homework Helper

- 41,833

- 961

- #6

- 655

- 3

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 lets you separate convex sets in any Banach space.

here is a diagram:

http://img266.imageshack.us/img266/5483/convexs1.gif [Broken]

here is a diagram:

http://img266.imageshack.us/img266/5483/convexs1.gif [Broken]

Last edited by a moderator:

- #7

- 1,030

- 4

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.

- #8

- 1,030

- 4

Ok I think I got the idea. This could work.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, [tex] p \in (-\infty, -a] \times (-\infty, -a] [/tex] ) is nonempty." In other words,

[tex] \{p \; : \; \ell \in L \Rightarrow p \notin \ell \; \textrm{and} \; p \in (-\infty, -a] \times (-\infty, -a] \} \neq \emptyset [/tex].

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.

- #9

- 655

- 3

ah yeah youre gonna 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.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.

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 10

- Views
- 2K

- Last Post

- Replies
- 14

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 875

- Last Post

- Replies
- 3

- Views
- 6K

- Last Post

- Replies
- 3

- Views
- 1K