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)
|