Prove that there always exists a line bisecting each of two point sets

Question

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?

Answer 1

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$.