Dynamic ham-sandwich cuts in the plane (Q1025301)

The two-dimensional version of the ham-sandwich theorem states that any two compact sets in the plane can be simultaneously bisected by a single line. Algorithms for determining such a bisecting line have been studied extensively; however, almost all such algorithms do not consider the possibility of dynamically altering the planar sets. In this paper, the authors present data structures and algorithms that allow for efficient bisector determination as well as dynamic insertion and deletion of points. The authors discuss the cases when each of the two sets is specified as a collection of points, or as a union of convex polygons; in the latter case, either the vertex count, perimeter, or area may be used as the measure by which to bisect. Also discussed is the related problem of partitioning a set into four equal parts using only two lines. Although the authors address an audience versed only in the generalities of computational geometry, the discussion makes extensive use of previous results. The overall exposition is terse, although abundant references are provided.