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

An Applet to Demonstrate the Ham Sandwich Cut Algorithm!


  • Important!
    • For this applet to work the point sets P and Q must be the same size!
    • Also things get cluttered up because of the primary and the dual, so it works better for small numbers.
  • To Begin
    1. Press "Point set P" and click as many points you want (the point set P are the red lines and points)
      • As you press click a new point, the line of the dual will appear
    2. Press "Point set Q" and click the canvas to create some Q points (they must equal the number of the P points, or the applet will do nothing)
      • The dual of the Q points are created automatically
    3. Click on "Intersection" and watch as the applet, finds all the intersections between the red and blue lines
      • These intersections are denoted by the green dots.
    4. Now click on "Ham Cut"  repeatedly 
      • A green line appears that is the x value at that point.  The pink dot is the median level of the red lines and the black line is the median level of the blue lines.
      • Once these two levels are equal, a black line is drawn that is the ham sandwich cut.


    • The applet has a few bugs in it, it will not always find the exact ham sandwich cut but it will usually come close, the main reason is that there is a flip between float numbers and integers where some of the precision is lost.  So the line drawn is not exact.
    • Also, for odd numbers of point sets, there is no way to split the points exactly in half.  But if you delete a point in each point set, the ham sandwich cut should be right.