Paper by Erik D. Demaine

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

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