Paper by Erik D. Demaine
- Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, and Vincent Yeung, “Dynamic Ham-Sandwich Cuts in the Plane”, Computational Geometry: Theory and Applications, volume 42, number 5, July 2009, pages 419–428. Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.
We design efficient data structures for dynamically maintaining a ham-sandwich
cut of two point sets in the plane subject to insertions and deletions of
points in either set. A ham-sandwich cut is a line that simultaneously
bisects the cardinality of both point sets. For general point sets, our first
data structure supports each operation in
O(n1/3+ε) amortized time and
O(n4/3+ε) space. Our second data structure
performs faster when each point set decomposes into a small number k of
subsets in convex position: it supports insertions and deletions in
O(log n) time and ham-sandwich queries in
O(k log4 n) time. In addition, if
each point set has convex peeling depth k, then we can maintain
the decomposition automatically using
O(k log n) time per insertion and deletion.
Alternatively, we can view each convex point set as a convex polygon, and we
show how to find a ham-sandwich cut that bisects the total areas or total
perimeters of these polygons in
O(k log4 n) time plus the
O((k b) polylog (k b))
time required to approximate the root of a polynomial of degree
O(k) up to b bits of precision. We also show how to
maintain a partition of the plane by two lines into four regions each
containing a quarter of the total point count, area, or perimeter in
- This paper is also available from ScienceDirect.
- The paper is 15 pages.
- The paper is available in PostScript (871k), gzipped PostScript (316k), and PDF (242k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- DynamicHamSandwich_CCCG2005 (Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated October 19, 2020 by