Creating a Ham Sandwich Cut Interactive Applet Necklace Thieves References Main Page


Step To Find the Ham Sandwich Cut


Step 1.
  1. Two point sets are created, P and Q


Step 2.
  1. For each point in set P and Q we take the Dual and create line sets H1 and H2 respectively.
Step 3.
  1. We divide the entire x-axis into C intervals so that each interval contains no more than a*N intersections between the lines.
    • Where C is the total number of intervals
    • a < 1, and is chosen before we begin the algorithm,
    • And N is the total number of intersection between all the lines
  2. This gives us C intervals with less than a*N intersections each.

The picture below shows a set of lines that have been divided up into intervals by the green lines.

Above the blue lines are the dual of the blue points and the red lines are the dual of the red points


Step 4.
  • We check all the intervals until we find one that has the  odd intersection property.  
  • We will call this interval "Io" ("I" for Intersection and "o" for odd!)

In the picture above, (which is a zoomed in view of an interval) the black dots represent the median level of the blue lines and the pink dots represent the median levels of the red lines.  Since the median levels are flipped, this means that this interval has the odd intersection property.  The green dots are the intersections of all the lines, if you count them there are 19!

Step 5.
  1. Now we construct a trapezoid inside our interval "Io".
  2. For this step we are only concerned with one of the sets of lines (the larger of the two sets).  In the picture below we choose the blue lines.
  3. We look at all the blue lines that intersect the trapezoid and all the blue lines that do not intersect it.  We throw away all the lines that do not intersect it, since these are not the median level.

    Above in the picture, our trapezoid is denoted by the orange lines.  Looking at it we can see that each of the corners of the trapezoid are exactly one line above or one line below the median level of the blue points.

Creating the Trapezoid

  • To create the vertices of the trapezoid we find the number M, that will be the number of levels above or below the median level.
  • To find this number we subtract a fraction of the total number of blue lines from the current median level P.
  • In there there algorithm they use the 1/8 of the total number of blue lines.

Finishing the Algorithm

  • Once we are finished creating the trapezoid, we throw away at least 1/2 of the blue lines.

  • We continue repeating steps 3-5 until we have removed enough blue lines so that it is easy to find a ham sandwich cut in linear time.