**Reference**:- Timothy Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung, “Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane”, in
*Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005)*, Windsor, Ontario, Canada, August 10–12, 2005, pages 61–64. **Abstract**:-
We provide an efficient data structure for dynamically maintaining a
ham-sandwich cut of two non-overlapping convex polygons in the plane.
Given two non-overlapping convex polygons
*P*_{1}and*P*_{2}in the plane, the ham-sandwich cut of*P*_{1}and*P*_{2}is a line that simultaneously bisects the area (or perimeter or vertex count) of both polygons. We provide a data structure that supports queries for the ham-sandwich cut in*O*(log^{3}*n*) worst-case time and insertions and deletions of vertices of the*P*_{i}in*O*(log*n*) worst-case time. We also show how this data structure can be used to maintain a partition of the plane by two lines into four regions each containing a quarter of the total polygon area (or perimeter or vertex count). In particular, if we use the vertex-count measure, the intersection of these two lines gives a point of Tukey depth*n*/4, which serves as an approximate Tukey median. **Length**:- The paper is 4 pages.
**Availability**:- The paper is available in PostScript (256k), gzipped PostScript (115k), and PDF (142k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- DynamicHamSandwich_CGTA (Dynamic Ham-Sandwich Cuts in the Plane)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.