Abbott, Timothy G.Burr, Michael A.Chan, Timothy M.Demaine, Erik D.Demaine, Martin L.Hugg, JohnKane, DanielLangerman, StefanNelson, JelaniRafalin, EynatSeyboth, KathrynYeung, Vincent2015-02-022009Abbott, Timothy G., Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, et al. 2009. “Dynamic Ham-Sandwich Cuts in the Plane.” Computational Geometry 42 (5) (July): 419–428. doi:10.1016/j.comgeo.2008.09.008.0925-7721http://nrs.harvard.edu/urn-3:HUL.InstRepos:13890811We 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(logn) time and ham-sandwich queries in O(klog4n) time. In addition, if each point set has convex peeling depth k , then we can maintain the decomposition automatically using O(klogn) 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(klog4n) time plus the O((kb)polylog(kb)) 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 polylogarithmic time.en-USData structuresBisectorsPoint setsPolygonsJournal Article2015-01-13Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel M. Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung2015-02-0210.1016/j.comgeo.2008.09.008