{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:53:13Z","timestamp":1772502793773,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161\/2011"],"award-info":[{"award-number":["1161\/2011"]}],"id":[{"id":"10.13039\/501100001736","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":["822-10"],"award-info":[{"award-number":["822-10"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1841-14"],"award-info":[{"award-number":["1841-14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU\/3501\/1"],"award-info":[{"award-number":["MU\/3501\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"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\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["892\/13"],"award-info":[{"award-number":["892\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","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":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include <jats:inline-formula><jats:alternatives><jats:tex-math>$$L_p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n \\log ^3 n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{\\varepsilon })$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>\u03b5<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time for an update and <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{\\varepsilon })$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>\u03b5<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of <jats:italic>\u201cvertical\u201d shallow cuttings<\/jats:italic> in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest <jats:italic>k<\/jats:italic> levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan\u2019s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\mathbb {R}}}^3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Along the way, we also revisit Chan\u2019s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).<\/jats:p>","DOI":"10.1007\/s00454-020-00243-7","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T22:10:47Z","timestamp":1600812647000},"page":"838-904","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications"],"prefix":"10.1007","volume":"64","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Seiferth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"issue":"1","key":"243_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00454-009-9177-z","volume":"42","author":"P Afshani","year":"2009","unstructured":"Afshani, P., Chan, T.M.: On approximate range counting and depth. Discrete Comput. Geom. 42(1), 3\u201321 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"243_CR2","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matou\u0161ek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"243_CR3","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in $$3$$-dimensional arrangements and its applications. SIAM J. Comput. 29(3), 912\u2013953 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"243_CR4","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"PK Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica 13(4), 325\u2013345 (1995)","journal-title":"Algorithmica"},{"key":"243_CR5","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Hackensack (2013)"},{"key":"243_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006)"},{"issue":"4","key":"243_CR7","doi-asserted-by":"publisher","first-page":"301","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), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"243_CR8","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. Springer, Berlin (2008)"},{"key":"243_CR9","volume-title":"Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization","year":"2007","unstructured":"Boissonnat, J.-D., Teillaud, M. (eds.): Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization. Springer, Berlin (2007)"},{"issue":"4","key":"243_CR10","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., Jej\u010di\u010d, M.: Shortest paths in intersection graphs of unit disks. Comput. Geom. 48(4), 360\u2013367 (2015)","journal-title":"Comput. Geom."},{"issue":"2","key":"243_CR11","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"TM Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of $$(\\le k)$$-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"243_CR12","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"TM Chan","year":"2005","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. SIAM J. Comput. 34(4), 879\u2013893 (2005)","journal-title":"SIAM J. Comput."},{"key":"243_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM 57(3), #\u00a016 (2010)","DOI":"10.1145\/1706591.1706596"},{"key":"243_CR14","unstructured":"Chan, T.M.: Dynamic geometric data structures via shallow cuttings. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 129, #\u00a024. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"2","key":"243_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/090751670","volume":"40","author":"TM Chan","year":"2011","unstructured":"Chan, T.M., P\u01cetra\u015fcu, M., Roditty, L.: Dynamic connectivity: connecting to networks and geometry. SIAM J. Comput. 40(2), 333\u2013349 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"243_CR16","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)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"243_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"243_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method. Cambridge University Press, Cambridge (2000)"},{"key":"243_CR19","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly-exponential stratification scheme for real semi-algebraic varieties and its applications. In: Automata, Languages and Programming (Stresa 1989). Lecture Notes in Computer Science, vol. 372, pp. 179\u2013193. Springer, Berlin (1989)","DOI":"10.1007\/BFb0035760"},{"key":"243_CR20","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Drysdale, R.L.\u00a0III: Voronoi diagrams based on convex distance functions. In: 1st Symposium on Computational Geometry (Baltimore 1985), pp. 235\u2013244. ACM, New York (1985)","DOI":"10.1145\/323233.323264"},{"issue":"3","key":"243_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(79)90084-0","volume":"25","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: The tail of the hypergeometric distribution. Discrete Math. 25(3), 285\u2013287 (1979)","journal-title":"Discrete Math."},{"issue":"4","key":"243_CR22","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"KL Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17(4), 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"243_CR23","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"243_CR24","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1(1), 25\u201344 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"243_CR25","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)","journal-title":"Discrete Comput. Geom."},{"key":"243_CR26","unstructured":"Erickson, J.: Static-to-dynamic transformations (lecture notes). http:\/\/jeffe.cs.illinois.edu\/teaching\/datastructures\/notes\/01-statictodynamic.pdf"},{"issue":"1","key":"243_CR27","first-page":"31","volume":"3","author":"M F\u00fcrer","year":"2012","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Spanners for geometric intersection graphs with applications. J. Comput. Geom. 3(1), 31\u201364 (2012)","journal-title":"J. Comput. Geom."},{"key":"243_CR28","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)"},{"key":"243_CR29","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Kaplan, H., Sharir, M.: Approximating the $$k$$-level in three-dimensional plane arrangements. In: A Journey Through Discrete Mathematics, pp. 467\u2013503. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-44479-6_19"},{"issue":"3","key":"243_CR30","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/s00454-010-9248-1","volume":"45","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S., Sharir, M.: Relative $$(p,\\epsilon )$$-approximations in geometry. Discrete Comput. Geom. 45(3), 462\u2013496 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"243_CR31","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)","journal-title":"J. ACM"},{"key":"243_CR32","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Spanners and reachability oracles for directed transmission graphs. In: 31st International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 34, pp. 156\u2013170. Leibniz-Zent. Inform., Wadern (2015)"},{"key":"243_CR33","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Dynamic connectivity for unit disk graphs. In: 32nd European Workshop on Computational Geometry (Lugano 2016), pp. 183\u2013186. https:\/\/www.eurocg2016.usi.ch\/sites\/default\/files\/EuroCG16-BookOfAbstract.pdf"},{"issue":"4","key":"243_CR34","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)","journal-title":"SIAM J. Comput."},{"key":"243_CR35","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495\u20132504. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.165"},{"key":"243_CR36","unstructured":"Kauer, A., Mulzer, M.: Dynamic disk connectivity. In: 35th European Workshop on Computational Geometry (Utrecht 2019), #\u00a050 (2019). http:\/\/www.eurocg2019.uu.nl\/papers\/50.pdf"},{"issue":"5","key":"243_CR37","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1145\/1017460.1017461","volume":"51","author":"V Koltun","year":"2004","unstructured":"Koltun, V.: Almost tight upper bounds for vertical decompositions in four dimensions. J. ACM 51(5), 699\u2013730 (2004)","journal-title":"J. ACM"},{"issue":"4","key":"243_CR38","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"DT Lee","year":"1980","unstructured":"Lee, D.T.: Two-dimensional Voronoi diagrams in the $$L_{p}$$-metric. J. ACM 27(4), 604\u2013618 (1980)","journal-title":"J. ACM"},{"issue":"3","key":"243_CR39","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y Li","year":"2001","unstructured":"Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the sample complexity of learning. J. Comput. System Sci. 62(3), 516\u2013527 (2001)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"243_CR40","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"issue":"4","key":"243_CR41","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K Mulmuley","year":"1991","unstructured":"Mulmuley, K.: On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. 6(4), 307\u2013338 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"243_CR42","volume-title":"Computational Geometry. An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry. An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)"},{"key":"243_CR43","first-page":"59","volume":"124","author":"W Mulzer","year":"2018","unstructured":"Mulzer, W.: Five proofs of Chernoff\u2019s bound with applications. Bull. Eur. Assoc. Theor. Comput. Sci. 124, 59\u201376 (2018)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"2","key":"243_CR44","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)","journal-title":"J. Comput. System Sci."},{"key":"243_CR45","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and $$k$$-level construction. In: 15th Annual Symposium on Computational Geometry (Miami Beach 1999), pp. 390\u2013399. ACM, New York (1999)","DOI":"10.1145\/304893.304993"},{"issue":"4","key":"243_CR46","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/s00453-009-9322-3","volume":"59","author":"L Roditty","year":"2011","unstructured":"Roditty, L., Segal, M.: On bounded leg shortest paths problems. Algorithmica 59(4), 583\u2013600 (2011)","journal-title":"Algorithmica"},{"issue":"3","key":"243_CR47","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J.T., Sharir, M.: On the \u201cpiano movers\u201d problem. II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4(3), 298\u2013351 (1983)","journal-title":"Adv. Appl. Math."},{"key":"243_CR48","unstructured":"Seiferth, P.: Disk Intersection Graphs: Models, Data Structures, and Algorithms. PhD thesis, Freie Universit\u00e4t Berlin (2016)"},{"key":"243_CR49","volume-title":"Davenport\u2013Schinzel Sequences and their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"6","key":"243_CR50","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/0218080","volume":"18","author":"PM Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Geometry helps in matching. SIAM J. Comput. 18(6), 1201\u20131225 (1989)","journal-title":"SIAM J. Comput."},{"key":"243_CR51","unstructured":"Wang, H., Xue, J.: Near-optimal algorithms for shortest paths in weighted unit-disk graphs. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 129, #\u00a060. Leibniz-Zent. Inform., Wadern (2019)"},{"issue":"4","key":"243_CR52","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"ACC Yao","year":"1982","unstructured":"Yao, A.C.C.: On constructing minimum spanning trees in $$k$$-dimensional spaces and related problems. SIAM J. Comput. 11(4), 721\u2013736 (1982)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00243-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-020-00243-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00243-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,22]],"date-time":"2021-09-22T00:46:12Z","timestamp":1632271572000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-020-00243-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["243"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00243-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"4 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}