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

Creating a Ham Sandwich Cut (According to Matousek, lo and Steiger)


History of the Ham Sandwich Cut

  • In the beginning, there was a linear time algorithm created by Megiddo, where the two point sets were separated by a line.  This algorithm was very efficient, and it could run in linear time. O(n)
  • Next came Edelsbrunner and Waupotitch and they modified Megiddo's algorithm so that it worked when the two point sets were not seperated by a line (this is called the general case).  But their algorithm was slower and only ran in O(nlgn)
  • Finally Matousek, Lo, and Steiger came along and developed an algorithm for the general case, and using some tricks and interesting points along the way, developed an algorithm that ran in  linear time O(n), (very efficient!)
  • Below are pictures of the general case (right) and the case where the two sets are seperated by a line (left)