Separated Ham-Sandwich Cut Algorithm
This algorithm is by Megiddo.
Bisectors
A line l is said to bisect a set A of n
points if both closed halfplanes bounded by l contain at least n/2
points of A. Note that if n is odd, then l has to
be incident to some point of A.
The Problem
Given a set R of n red points and a set B of m
blue points, such that all points in R have negative x
coordinate, and all points in B have positive x
coordinate, find a ham-sandwich cut l for R and B
(i.e. l bisects both R and B).
If n and m are both odd, then l has to go
through a blue point and a red point. In the following, we can assume n
and m are both odd, otherwise we add one point to R and/or B.
A ham-sandwich cut of the augmented set is a ham-sandwich cut of the
original set.
The Dual
In the dual, the blue points map to blue lines, the red points map to
red lines. The median level of the red lines is the set of all
points in the dual that have exactly (n-1)/2 red lines above it
and (n-1)/2 red lines below it. The dual lines of those points
are bisectors of R. The median level of the blue lines is
defined similarly. A point at the intersection of those two median
levels is a ham-sandwich cut.
Since the red points have negative x coordinates, the red
lines have negative slopes. Likewise, the blue lines have positive
slopes. So the red median level is monotone decreasing, and the blue
median level is monotone increasing.
Sidedness tests
Given a vertical line, the intersections of that line with both median
levels can be found in linear time using a selection algorithm (as seen
in class).
Given a line h of positive slope, consider the intersections
of all red lines with h, and walk along the line from left to
right. Since red lines have negative slopes, when you start at the far
left, all red lines are above, and as you walk from left to right across
a red line, the line crosses h from above to below, so the number
of red lines above decreases by one. So the median level intersects h
exactly once at the intersection with the median x coordinate,
and so can be found in linear time using a selection algorithm.
Once the intersection between h and the red median level has
been found, draw a vertical line v through it, and find the
intersection between the blue median level and v. The point dual
to the ham-sandwich cut is on the same side of h as this
intersection. (exercise: prove this). This way, we can decide the
sidedness test for a line with positive slope in linear time. The same
can be done for lines with a negative slope.
The pruning step
- Find s the median slope of all remaining lines
(independently of their color)
- Arbitrarily pair line of slopes larger than s with lines
of slope smaller than s. Let I be the set of all
these intersections.
- Find a vertical line w bisecting all those intersections.
- Decide which side of that line w contains the intersection
of the median levels. (suppose the intersection is to the right)
- Find a line h that bisects the points of I to the
left of w.
- Perform a sidedness on that line h. This allows to prune
at least an eighth of the remaining lines (as explained in
class).