Finding 2d ham sandwich cuts in linear time
Benjamin Armbruster · 2008
A ham sandwich cut in d dimensions is a (d 1)-dimensional hyperplane that divides each of d objects in half. While the existence of such a hyperplane was shown in 1938, little is known about how to find one. We are the first to show how this can be done in 2 dimensions when both objects are (possibly overlapping) convex polygons. Our algorithm runs in O(N) time where N is the sum of the number of sides of the two polygons. We also give a linear time algorithm for the case when the first object is a convex polygon and the second object is a finite set of points.