{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:40Z","timestamp":1740109600559,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T00:00:00Z","timestamp":1704240000000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["StG 757609"],"award-info":[{"award-number":["StG 757609"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1367\/2016"],"award-info":[{"award-number":["1367\/2016"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1595\/19"],"award-info":[{"award-number":["1595\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011643","name":"Blavatnik Family Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011643","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU 3501\/3-1","GRK 2434"],"award-info":[{"award-number":["MU 3501\/3-1","GRK 2434"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>Let $$S \\subseteq \\mathbb {R}^2$$<\/jats:tex-math>\n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a set of n<\/jats:italic>sites<\/jats:italic> in the plane, so that every site $$s \\in S$$<\/jats:tex-math>\n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has an associated radius<\/jats:italic>$$r_s > 0$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Let $$\\mathcal {D}(S)$$<\/jats:tex-math>\n \n D<\/mml:mi>\n (<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the disk intersection graph<\/jats:italic> defined by S<\/jats:italic>, i.e., the graph with vertex set S<\/jats:italic> and an edge between two distinct sites $$s, t \\in S$$<\/jats:tex-math>\n \n s<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if and only if the disks with centers s<\/jats:italic>, t<\/jats:italic> and radii $$r_s$$<\/jats:tex-math>\n \n r<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$r_t$$<\/jats:tex-math>\n \n r<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> intersect. Our goal is to design data structures that maintain the connectivity structure of $$\\mathcal {D}(S)$$<\/jats:tex-math>\n \n D<\/mml:mi>\n (<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> as sites are inserted and\/or deleted in S<\/jats:italic>. First, we consider unit disk graphs<\/jats:italic>, i.e., we fix $$r_s = 1$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for all sites $$s \\in S$$<\/jats:tex-math>\n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For this case, we describe a data structure that has $$O(\\log ^2 n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> amortized update time and $$O(\\log n\/\\log \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> query time. Second, we look at disk graphs with bounded radius ratio<\/jats:italic>$$\\Psi $$<\/jats:tex-math>\n \u03a8<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, i.e., for all $$s \\in S$$<\/jats:tex-math>\n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we have $$1 \\le r_s \\le \\Psi $$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n \n r<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \u03a8<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for a parameter $$\\Psi $$<\/jats:tex-math>\n \u03a8<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that is known in advance. Here, we not only investigate the fully dynamic case, but also the incremental and the decremental scenario, where only insertions or only deletions of sites are allowed. In the fully dynamic case, we achieve amortized expected update time $$O(\\Psi \\log ^{4} n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03a8<\/mml:mi>\n \n log<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and query time $$O(\\log n\/\\log \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This improves the currently best update time by a factor of $$\\Psi $$<\/jats:tex-math>\n \u03a8<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In the incremental case, we achieve logarithmic dependency on $$\\Psi $$<\/jats:tex-math>\n \u03a8<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, with a data structure that has $$O(\\alpha (n))$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b1<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> amortized query time and $$O(\\log \\Psi \\log ^{4} n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n \u03a8<\/mml:mi>\n \n log<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> amortized expected update time, where $$\\alpha (n)$$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the inverse Ackermann function. For the decremental setting, we first develop an efficient decremental disk revealing<\/jats:italic> data structure: given two sets R<\/jats:italic> and B<\/jats:italic> of disks in the plane, we can delete disks from B<\/jats:italic>, and upon each deletion, we receive a list of all disks in R<\/jats:italic> that no longer intersect the union of B<\/jats:italic>. Using this data structure, we get decremental data structures with a query time of $$O(\\log n\/\\log \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that supports deletions in $$O(n\\log \\Psi \\log ^{4} n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n \u03a8<\/mml:mi>\n \n log<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> overall expected time for disk graphs with bounded radius ratio $$\\Psi $$<\/jats:tex-math>\n \u03a8<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$O(n\\log ^{5} n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> overall expected time for disk graphs with arbitrary radii, assuming that the deletion sequence is oblivious of the internal random choices of the data structures.<\/jats:p>","DOI":"10.1007\/s00454-023-00621-x","type":"journal-article","created":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T20:02:32Z","timestamp":1704312152000},"page":"214-277","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Connectivity in Disk Graphs"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8112-0482","authenticated-orcid":false,"given":"Alexander","family":"Baumann","sequence":"first","affiliation":[]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9884-3297","authenticated-orcid":false,"given":"Katharina","family":"Klost","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4239-424X","authenticated-orcid":false,"given":"Kristin","family":"Knorr","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Seiferth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,3]]},"reference":[{"key":"621_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, P.K., Cohen, R., Halperin, D., Mulzer, W.: Maintaining the union of unit discs under insertions with near-optimal overhead. In: Proceedings of the 35th Annual Symposium on Computational Geometry (SoCG), pp. 26:1\u201326:15 (2019) https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.26","DOI":"10.4230\/LIPIcs.SoCG.2019.26"},{"issue":"3","key":"621_CR2","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"PK Agarwal","year":"1991","unstructured":"Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom. 6(3), 407\u2013422 (1991). https:\/\/doi.org\/10.1007\/BF02574698","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"621_CR3","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF02574015","volume":"11","author":"PK Agarwal","year":"1994","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: On range searching with semialgebraic sets. Discrete Comput. Geom. 11(4), 393\u2013418 (1994). https:\/\/doi.org\/10.1007\/BF02574015","journal-title":"Discrete Comput. Geom."},{"key":"621_CR4","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"SW Bent","year":"1985","unstructured":"Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J. Comput. 14, 545\u2013568 (1985)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"621_CR5","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms 1(4), 58 (1980)","journal-title":"J. Algorithms"},{"key":"621_CR6","doi-asserted-by":"publisher","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 617\u2013626 (2002) https:\/\/doi.org\/10.1109\/SFCS.2002.1181985","DOI":"10.1109\/SFCS.2002.1181985"},{"issue":"3","key":"621_CR7","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1007\/s00453-010-9430-0","volume":"61","author":"K Buchin","year":"2011","unstructured":"Buchin, K., L\u00f6ffler, M., Morin, P., Mulzer, W.: Preprocessing imprecise points for Delaunay triangulation: simplified and extended. Algorithmica 61(3), 674\u2013693 (2011). https:\/\/doi.org\/10.1007\/s00453-010-9430-0","journal-title":"Algorithmica"},{"issue":"4","key":"621_CR8","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.comgeo.2014.12.003","volume":"48","author":"S Cabello","year":"2015","unstructured":"Cabello, S., Jejcic, M.: Shortest paths in intersection graphs of unit disks. Comput. Geom. Theory Appl. 48(4), 360\u2013367 (2015). https:\/\/doi.org\/10.1016\/j.comgeo.2014.12.003","journal-title":"Comput. Geom. Theory Appl."},{"key":"621_CR9","doi-asserted-by":"publisher","unstructured":"Catusse, N., Chepoi, V., Vax\u00e8s, Y.: Planar hop spanners for unit disk graphs. In: Algorithms for Sensor Systems, Lecture Notes in Computer Science, pp. 16\u201330. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-16988-5_2","DOI":"10.1007\/978-3-642-16988-5_2"},{"issue":"1","key":"621_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/363647.363652","volume":"48","author":"TM Chan","year":"2001","unstructured":"Chan, T.M.: Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM 48(1), 1\u201312 (2001). https:\/\/doi.org\/10.1145\/363647.363652","journal-title":"J. ACM"},{"issue":"3","key":"621_CR11","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/1706591.1706596","volume":"57","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM 57(3), 16:1-16:15 (2010). https:\/\/doi.org\/10.1145\/1706591.1706596","journal-title":"J. ACM"},{"issue":"4","key":"621_CR12","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1007\/s00454-020-00229-5","volume":"64","author":"TM Chan","year":"2020","unstructured":"Chan, T.M.: Dynamic geometric data structures via shallow cuttings. Discrete Comput. Geom. 64(4), 1235\u20131252 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00229-5","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"621_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/090751670","volume":"40","author":"TM Chan","year":"2011","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M., Roditty, L.: Dynamic connectivity: connecting to networks and geometry. SIAM J. Comput. 40(2), 333\u2013349 (2011). https:\/\/doi.org\/10.1137\/090751670","journal-title":"SIAM J. Comput."},{"issue":"4","key":"621_CR14","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1007\/s00454-016-9784-4","volume":"56","author":"TM Chan","year":"2016","unstructured":"Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comput. Geom. 56(4), 866\u2013881 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9784-4","journal-title":"Discrete Comput. Geom."},{"key":"621_CR15","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"621_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","edition":"3"},{"issue":"2","key":"621_CR17","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986). https:\/\/doi.org\/10.1137\/0215023","journal-title":"SIAM J. Comput."},{"issue":"1","key":"621_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02574030","volume":"13","author":"D Eppstein","year":"1995","unstructured":"Eppstein, D.: Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom. 13(1), 111\u2013122 (1995). https:\/\/doi.org\/10.1007\/BF02574030","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"621_CR19","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms 13(1), 33\u201354 (1992). https:\/\/doi.org\/10.1016\/0196-6774(92)90004-V","journal-title":"J. Algorithms"},{"key":"621_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S Fortune","year":"1987","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153 (1987). https:\/\/doi.org\/10.1007\/BF01840357","journal-title":"Algorithmica"},{"key":"621_CR21","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms, vol. 173. American Mathematical Society, Providence (2011). https:\/\/doi.org\/10.1090\/surv\/173"},{"key":"621_CR22","unstructured":"Hofer, C.: Fast Dynamic Planar Convex Set Maintenance Using Finger Trees. Bachelor thesis, Freie Universit\u00e4t Berlin (2017)"},{"issue":"4","key":"621_CR23","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001). https:\/\/doi.org\/10.1145\/502090.502095","journal-title":"J. ACM"},{"key":"621_CR24","doi-asserted-by":"publisher","unstructured":"Huang, S.-E., Huang, D., Kopelowitz, T., Pettie, S.: Fully dynamic connectivity in $$O(\\log n(\\log \\log n)^2)$$ amortized expected time. In: Proceedings of 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 510\u2013520 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.32","DOI":"10.1137\/1.9781611974782.32"},{"key":"621_CR25","doi-asserted-by":"publisher","unstructured":"Kaplan, H., Klost, K., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Triangles and girth in disk graphs and transmission graphs. In: 27th Annual European Symposium on Algorithms, ESA 2019, pp. 64:1\u201364:14 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.64","DOI":"10.4230\/LIPIcs.ESA.2019.64"},{"issue":"4","key":"621_CR26","doi-asserted-by":"publisher","first-page":"1585","DOI":"10.1137\/16M1059692","volume":"47","author":"H Kaplan","year":"2018","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Spanners for directed transmission graphs. SIAM J. Comput. 47(4), 1585\u20131609 (2018). https:\/\/doi.org\/10.1137\/16M1059692","journal-title":"SIAM J. Comput."},{"issue":"3","key":"621_CR27","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1007\/s00454-020-00243-7","volume":"64","author":"H Kaplan","year":"2020","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. Discrete Comput. Geom. 64(3), 838\u2013904 (2020). https:\/\/doi.org\/10.1007\/s00454-020-00243-7","journal-title":"Discrete Comput. Geom."},{"key":"621_CR28","unstructured":"Kaplan, H., Tarjan, R.E., Tsioutsiouliklis, K.: Faster kinetic heaps and their use in broadcast scheduling. In: Proceedings of 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 836\u2013844 (2001)"},{"key":"621_CR29","doi-asserted-by":"publisher","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA \u201913, pp. 1131\u20131142 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.81","DOI":"10.1137\/1.9781611973105.81"},{"key":"621_CR30","doi-asserted-by":"publisher","first-page":"101979","DOI":"10.1016\/j.comgeo.2022.101979","volume":"111","author":"K Klost","year":"2023","unstructured":"Klost, K.: An algorithmic framework for the single source shortest path problem with applications to disk graphs. Comput. Geom. Theory Appl. 111, 101979 (2023). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101979","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"621_CR31","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1137\/20m1388371","volume":"51","author":"C-H Liu","year":"2022","unstructured":"Liu, C.-H.: Nearly optimal planar $$k$$ nearest neighbors queries under general distance functions. SIAM J. Comput. 51(3), 723\u2013765 (2022). https:\/\/doi.org\/10.1137\/20m1388371","journal-title":"SIAM J. Comput."},{"issue":"4","key":"621_CR32","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1137\/110825698","volume":"41","author":"M L\u00f6ffler","year":"2012","unstructured":"L\u00f6ffler, M., Mulzer, W.: Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent. SIAM J. Comput. 41(4), 941\u2013974 (2012). https:\/\/doi.org\/10.1137\/110825698","journal-title":"SIAM J. Comput."},{"key":"621_CR33","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-40104-6_43","volume-title":"Algorithms and Data Structures","author":"M L\u00f6ffler","year":"2013","unstructured":"L\u00f6ffler, M., Simons, J.A., Strash, D.: Dynamic planar point location with sub-logarithmic local updates. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) Algorithms and Data Structures, pp. 499\u2013511. Springer, Berlin (2013)"},{"key":"621_CR34","unstructured":"Mitchell, J.S.B., Mulzer, W.: Proximity algorithms. In: J.E. Goodman, J. O\u2019Rourke, C.D. T\u00f3th (eds) Handbook of Discrete and Computational Geometry, chapter\u00a032, 3rd edition, pp. 849\u2013874 (2017)"},{"issue":"2","key":"621_CR35","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"MH Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. System Sci. 23(2), 166\u2013204 (1981). https:\/\/doi.org\/10.1016\/0022-0000(81)90012-X","journal-title":"J. Comput. System Sci."},{"key":"621_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry\u2014An Introduction. Springer, Berlin (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6"},{"issue":"1","key":"621_CR37","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0020-0190(87)90095-0","volume":"25","author":"JH Reif","year":"1987","unstructured":"Reif, J.H.: A topological approach to dynamic graph connectivity. Inf. Process. Lett. 25(1), 65\u201370 (1987). https:\/\/doi.org\/10.1016\/0020-0190(87)90095-0","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"621_CR38","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/0214034","volume":"14","author":"M Sharir","year":"1985","unstructured":"Sharir, M.: Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14(2), 448\u2013468 (1985). https:\/\/doi.org\/10.1137\/0214034","journal-title":"SIAM J. Comput."},{"issue":"3","key":"621_CR39","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983). https:\/\/doi.org\/10.1016\/0022-0000(83)90006-5","journal-title":"J. Comput. Syst. Sci."},{"key":"621_CR40","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of 32nd Annual ACM Symposium Theory Computing (STOC), pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"key":"621_CR41","doi-asserted-by":"publisher","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: Proceedings of 24th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1757\u20131769 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.126","DOI":"10.1137\/1.9781611973105.126"},{"key":"621_CR42","doi-asserted-by":"publisher","unstructured":"Yao, A.C., Frances Yao, F.: A general approach to D-dimensional geometric queries. In: Proceedings of 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 163\u2013168 (1985). https:\/\/doi.org\/10.1145\/22145.22163","DOI":"10.1145\/22145.22163"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00621-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00621-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00621-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T20:02:37Z","timestamp":1704571357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00621-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["621"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00621-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"12 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}