3
$\begingroup$

A line $\ell$ for a set $S$ of points is bisecting if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points.

Now given point sets $A$ and $B$ in the plane, prove that we can always find a line $\ell$ such that $\ell$ bisects both $A$ and $B$ simultaneously. We can assume that no three points in $A \cup B$ lie on a line and no two points share an x-coordinate.

Note that I am not asking for an algorithm separating $A$ and $B$.


So far I have proven the following claim:

Let $S$ be a point set in the plane containing an even number of points. Prove that, for any point $s \in S$, a bisecting line $\ell$ for $S \setminus \{s\}$ also bisects $S$.

From this claim we can also infer that all separting lines for a point set $P$ with an odd number of points must pass through at least one point $p \in P$. However I am stuck on how to continue. Intuition suggests that one of the lines between points $a \in A$ and $b \in B$ must be simultaneously bisecting (if either of $A$ or $B$ contain an even number of points we can just remove one at random by the above claim). However I cannot seem to prove this is always the case.

Can you give me a hint for the next step?

$\endgroup$
  • 1
    $\begingroup$ Note that this is a special case of the Ham sandwich theorem, which states that for $n$ measurable objects in the $n$-dimensional Euclidean space, one can always find a $n-1$-dimensional hyperplane such that the $n$ objects are divided in half (w.r.t. the given meaure). Here, $n = 2$ and the measure used is the counting measure. Barring this: Can we prove this theorem without using the ham sandwich theorem (i.e. using only discrete geometry)? $\endgroup$ – ThreeFx Jan 20 at 16:56
  • $\begingroup$ What do you mean "discrete geometry"? I am afraid it is either not well-defined or not suitable for the current situation of 2-dimension Euclidean space. $\endgroup$ – Apass.Jack Jan 20 at 18:25
  • $\begingroup$ @Apass.Jack You're right, that's a bad formulation on my part. I meant: can we prove this without delving into measures and measure-theory? $\endgroup$ – ThreeFx Jan 20 at 18:48
  • $\begingroup$ In fact, we can make an algorithm to compute that line while proving the claim. The proof here is clear enough to me. $\endgroup$ – Apass.Jack Jan 20 at 18:52
  • $\begingroup$ @Apass.Jack That proof only applies to pancakes and isn't applicable to point sets since they aren't continuously measurable. $\endgroup$ – ThreeFx Jan 20 at 19:03
2
$\begingroup$

We can prove this using the geometric dual of $P$ and $Q$.

Take the line arrangement of $P^*$ and $Q^*$ in the plane and let us look at the median levels $\Lambda_p$ and $\Lambda_q$. Their intersection is definitely a possible solution because $\Lambda_p$ is the point set describing the dual of all bisecting lines for $P$, and vice-versa for $Q$.

Note the following: Since $|P|$ and $|Q|$ are odd, both median line arrangements have the same slope (and since all slopes are unique by assumption, they must correspond to the same lines) in the beginning and the end of the arrangement. Let us denote $p^*$ and $q^*$ as the respective lines. Then at the beginning (i.e. the largest x-value where no intersections occured yet), one must be above the other and at the end (i.e. the smallest x-value such that no intersections happen from now on forward), they must have switched places.

Since the levels $\Lambda_p$ and $\Lambda_q$ are piecewise continuous (actually even continuously extensible), by the intermediate value theorem they must intersect in at least one point $c^*$, which is the dual of a possible simultaneously bisecting line $c$.

$\endgroup$
  • $\begingroup$ This answer is nice. However, the proof that uses a rotating-knife is simpler. We just let each point represent one unit of pancake. $\endgroup$ – Apass.Jack Jan 23 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.