Separated Ham-Sandwich Cut Algorithm

This algorithm is by Megiddo. 


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

  1. Find s the median slope of all remaining lines (independently of their color)
  2. Arbitrarily pair line of slopes larger than s with lines of slope smaller than s. Let I be the set of all these intersections.
  3. Find a vertical line w bisecting all those intersections.
  4. Decide which side of that line w contains the intersection of the median levels. (suppose the intersection is to the right)
  5. Find a line h that bisects the points of I to the left of w.
  6. Perform a sidedness on that line h. This allows to prune at least an eighth of the remaining lines (as explained in class).