Paper by Erik D. Demaine

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.

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 P1 and P2 in the plane, the ham-sandwich cut of P1 and P2 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(log3 n) worst-case time and insertions and deletions of vertices of the Pi 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.

The paper is 4 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.