Dynamic ham-sandwich cuts in the plane
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 firs...
| Main Authors: | , , , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/96191 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826191963962998784 |
|---|---|
| author | Abbott, Timothy G. Burr, Michael A. Chan, Timothy M. Demaine, Erik D. Demaine, Martin L. Hugg, John Kane, Daniel Langerman, Stefan Nelson, Jelani Rafalin, Eynat Seyboth, Kathryn Yeung, Vincent |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abbott, Timothy G. Burr, Michael A. Chan, Timothy M. Demaine, Erik D. Demaine, Martin L. Hugg, John Kane, Daniel Langerman, Stefan Nelson, Jelani Rafalin, Eynat Seyboth, Kathryn Yeung, Vincent |
| author_sort | Abbott, Timothy G. |
| collection | MIT |
| description | 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(n[1 over 3]+ε) amortized time and O(n[4 over 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)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(klog[superscript 4]n) 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. |
| first_indexed | 2024-09-23T09:04:04Z |
| format | Article |
| id | mit-1721.1/96191 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:04:04Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/961912022-09-26T10:12:09Z Dynamic ham-sandwich cuts in the plane Abbott, Timothy G. Burr, Michael A. Chan, Timothy M. Demaine, Erik D. Demaine, Martin L. Hugg, John Kane, Daniel Langerman, Stefan Nelson, Jelani Rafalin, Eynat Seyboth, Kathryn Yeung, Vincent Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Abbott, Timothy G. Demaine, Martin L. Yeung, Vincent Nelson, Jelani 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(n[1 over 3]+ε) amortized time and O(n[4 over 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)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(klog[superscript 4]n) 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. 2015-03-25T18:34:46Z 2015-03-25T18:34:46Z 2009-01 2008-02 Article http://purl.org/eprint/type/JournalArticle 09257721 http://hdl.handle.net/1721.1/96191 Abbott, Timothy G., Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, et al. “Dynamic Ham-Sandwich Cuts in the Plane.” Computational Geometry 42, no. 5 (July 2009): 419–428. © 2009 Elsevier B.V. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1016/j.comgeo.2008.09.008 Computational Geometry Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Elsevier Elsevier |
| spellingShingle | Abbott, Timothy G. Burr, Michael A. Chan, Timothy M. Demaine, Erik D. Demaine, Martin L. Hugg, John Kane, Daniel Langerman, Stefan Nelson, Jelani Rafalin, Eynat Seyboth, Kathryn Yeung, Vincent Dynamic ham-sandwich cuts in the plane |
| title | Dynamic ham-sandwich cuts in the plane |
| title_full | Dynamic ham-sandwich cuts in the plane |
| title_fullStr | Dynamic ham-sandwich cuts in the plane |
| title_full_unstemmed | Dynamic ham-sandwich cuts in the plane |
| title_short | Dynamic ham-sandwich cuts in the plane |
| title_sort | dynamic ham sandwich cuts in the plane |
| url | http://hdl.handle.net/1721.1/96191 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT abbotttimothyg dynamichamsandwichcutsintheplane AT burrmichaela dynamichamsandwichcutsintheplane AT chantimothym dynamichamsandwichcutsintheplane AT demaineerikd dynamichamsandwichcutsintheplane AT demainemartinl dynamichamsandwichcutsintheplane AT huggjohn dynamichamsandwichcutsintheplane AT kanedaniel dynamichamsandwichcutsintheplane AT langermanstefan dynamichamsandwichcutsintheplane AT nelsonjelani dynamichamsandwichcutsintheplane AT rafalineynat dynamichamsandwichcutsintheplane AT seybothkathryn dynamichamsandwichcutsintheplane AT yeungvincent dynamichamsandwichcutsintheplane |