{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:02Z","timestamp":1750220402840,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-15-13816, CCF-15-46392, and IIS-14-08846"],"award-info":[{"award-number":["CCF-15-13816, CCF-15-46392, and IIS-14-08846"]}]},{"name":"ARO","award":["W911NF-15-1-0408"],"award-info":[{"award-number":["W911NF-15-1-0408"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1736\/19"],"award-info":[{"award-number":["1736\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF\/US-Israel-BSF","award":["2019754"],"award-info":[{"award-number":["2019754"]}]},{"name":"Israel Ministry of Science and Technology","award":["103129"],"award-info":[{"award-number":["103129"]}]},{"name":"ERC STG","award":["757609"],"award-info":[{"award-number":["757609"]}]},{"name":"GIF","award":["1367\/2016"],"award-info":[{"award-number":["1367\/2016"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper:<\/jats:p>\n          <jats:p>\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(i)<\/jats:label>\n                <jats:p>\n                  We present a linear-size data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in\n                  <jats:italic>O<\/jats:italic>\n                  ((\n                  <jats:italic>k<\/jats:italic>\n                  +1)log\n                  <jats:sup>2<\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  ) time, where\n                  <jats:italic>n<\/jats:italic>\n                  is the current number of unit discs and\n                  <jats:italic>k<\/jats:italic>\n                  is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(ii)<\/jats:label>\n                <jats:p>\n                  We propose a linear-size data structure for maintaining the lower envelope of a set of\n                  <jats:italic>x<\/jats:italic>\n                  -monotone pseudo-lines. It can handle insertion\/deletion of a pseudo-line in\n                  <jats:italic>O<\/jats:italic>\n                  (log\n                  <jats:sup>2<\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  ) time; for a query point x\n                  <jats:sub>0<\/jats:sub>\n                  \u2208 \u211d, it can report, in\n                  <jats:italic>O<\/jats:italic>\n                  (log\n                  <jats:italic>n<\/jats:italic>\n                  ) time, the point on the lower envelope with\n                  <jats:italic>x<\/jats:italic>\n                  -coordinate\n                  <jats:italic>x<\/jats:italic>\n                  <jats:sub>0<\/jats:sub>\n                  ; and for a query point\n                  <jats:italic>q<\/jats:italic>\n                  \u2208 \u211d\n                  <jats:sup>2<\/jats:sup>\n                  , it can return all\n                  <jats:italic>k<\/jats:italic>\n                  pseudo-lines lying below\n                  <jats:italic>q<\/jats:italic>\n                  in time\n                  <jats:italic>O<\/jats:italic>\n                  (log\n                  <jats:italic>n<\/jats:italic>\n                  +\n                  <jats:italic>k<\/jats:italic>\n                  log\n                  <jats:sup>2<\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  ).\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(iii)<\/jats:label>\n                <jats:p>\n                  We present a linear-size data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc\n                  <jats:italic>D<\/jats:italic>\n                  , all input arcs intersecting\n                  <jats:italic>D<\/jats:italic>\n                  can be reported in\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>1\/2+\u025b<\/jats:sup>\n                  +\n                  <jats:italic>k<\/jats:italic>\n                  ) time, where\n                  <jats:italic>k<\/jats:italic>\n                  is the output size and \u025b &gt; 0  is an arbitrarily small constant. A unit-circle arc can be inserted or deleted in\n                  <jats:italic>O<\/jats:italic>\n                  (log\n                  <jats:sup>2<\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  ) time.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>","DOI":"10.1145\/3527614","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T11:58:56Z","timestamp":1659614336000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5275-9754","authenticated-orcid":false,"given":"Ravid","family":"Cohen","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3345-3765","authenticated-orcid":false,"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_5_2_2","first-page":"1057","volume-title":"Handbook of Discrete and Computational Geometry (3rd ed.)","author":"Agarwal Pankaj K.","year":"2017","unstructured":"Pankaj K. Agarwal. 2017. Range searching. In Handbook of Discrete and Computational Geometry (3rd ed.), Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba T\u00f3th (Eds.). CRC Press, Chapter 40, 1057\u20131092."},{"key":"e_1_3_5_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44479-6_1"},{"key":"e_1_3_5_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574015"},{"key":"e_1_3_5_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01293483"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222050"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1040"},{"key":"e_1_3_5_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90035-1"},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_3_5_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3414845"},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_5_12_2","first-page":"57","volume-title":"Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"Brodal Gerth St\u00f8lting","year":"2000","unstructured":"Gerth St\u00f8lting Brodal and Riko Jacob. 2000. Dynamic planar convex hull with optimal query time. In Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT). 57\u201370."},{"key":"e_1_3_5_13_2","first-page":"617","volume-title":"Proc. 43rd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS)","author":"Brodal Gerth St\u00f8lting","year":"2002","unstructured":"Gerth St\u00f8lting Brodal and Riko Jacob. 2002. Dynamic planar convex hull. In Proc. 43rd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS). 617\u2013626."},{"key":"e_1_3_5_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363652"},{"key":"e_1_3_5_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706596"},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-020-00229-5"},{"key":"e_1_3_5_17_2","unstructured":"Ravid Cohen Yossi Yovel and Dan Halperin. 2019. Sensory Regimes of Effective Distributed Searching without Leaders. (2019). http:\/\/arxiv.org\/abs\/1904.02895."},{"key":"e_1_3_5_18_2","first-page":"83","volume-title":"Handbook of Discrete and Computational Geometry (3rd ed.)","author":"Felsner Stefan","year":"2017","unstructured":"Stefan Felsner and Jacob E. Goodman. 2017. Pseudoline arrangements. In Handbook of Discrete and Computational Geometry (3rd ed.), Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba D. T\u00f3th (Eds.). CRC Press, Chapter 5, 83\u2013109."},{"key":"e_1_3_5_19_2","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/010"},{"key":"e_1_3_5_20_2","first-page":"183","volume-title":"Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT)","author":"Gupta Prosenjit","year":"1994","unstructured":"Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. 1994. On intersection searching problems involving curved objects. In Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT). 183\u2013194."},{"key":"e_1_3_5_21_2","first-page":"1343","volume-title":"Handbook of Discrete and Computational Geometry (3rd ed.)","author":"Halperin Dan","year":"2017","unstructured":"Dan Halperin and Micha Sharir. 2017. Arrangements. In Handbook of Discrete and Computational Geometry (3rd ed.), Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba D. T\u00f3th (Eds.). CRC Press, Chapter 28, 1343\u20131376."},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90013-O"},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-020-00243-7"},{"key":"e_1_3_5_24_2","first-page":"836","volume-title":"Proc. 12th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA)","author":"Kaplan Haim","year":"2001","unstructured":"Haim Kaplan, Robert Endre Tarjan, and Kostas Tsioutsiouliklis. 2001. Faster kinetic heaps and their use in broadcast scheduling. In Proc. 12th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA). 836\u2013844."},{"key":"e_1_3_5_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/2805882.2806037"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.173"},{"key":"e_1_3_5_27_2","series-title":"Lecture Notes in Computer Science","volume-title":"The Design of Dynamic Data Structures","author":"Overmars Mark H.","year":"1983","unstructured":"Mark H. Overmars. 1983. The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156. Springer-Verlag."},{"key":"e_1_3_5_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90012-X"},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/359131.359132"},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_3_5_31_2","volume-title":"Very Fast Algorithms for the Area of the Union of Many Circles","author":"Spirakis Paul G.","year":"1983","unstructured":"Paul G. Spirakis. 1983. Very Fast Algorithms for the Area of the Union of Many Circles. Technical Report 98. Courant Institute, New York University."},{"key":"e_1_3_5_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/3485"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527614","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527614","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:53Z","timestamp":1750191533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3527614"],"URL":"https:\/\/doi.org\/10.1145\/3527614","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2021-02-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}