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 July 23, 2024 by
Erik Demaine.