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)
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
Last updated November 14, 2019 by