{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T06:31:48Z","timestamp":1786689108166,"version":"build-2736575974"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T00:00:00Z","timestamp":1781481600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T00:00:00Z","timestamp":1781481600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-20-07556"],"award-info":[{"award-number":["CCF-20-07556"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2022131"],"award-info":[{"award-number":["2022131"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1156\/23"],"award-info":[{"award-number":["1156\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Blavatnik research Foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1007\/s00453-026-01395-3","type":"journal-article","created":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T04:49:14Z","timestamp":1781498954000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9586-8002","authenticated-orcid":false,"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0672-729X","authenticated-orcid":false,"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2541-3763","authenticated-orcid":false,"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,15]]},"reference":[{"key":"1395_CR1","first-page":"1","volume-title":"Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek","author":"PK Agarwal","year":"2017","unstructured":"Agarwal, P.K.: Simplex range searching and its variants: A review. In: Loebl, M., Ne\u0161et\u0159il, J., Thomas, R. (eds.) Journey through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 1\u201330. Springer Verlag, Berlin-Heidelberg (2017)"},{"issue":"1\u201325","key":"1395_CR2","first-page":"59","volume":"25","author":"PK Agarwal","year":"2025","unstructured":"Agarwal, P.K., Aronov, B., Ezra, E., Katz, M.J., Sharir, M.: Intersection queries for flat semi-algebraic objects in three dimensions and related problems. ACM Trans. Algorithms 21 25(1\u201325), 59 (2025)","journal-title":"ACM Trans. Algorithms 21"},{"issue":"3","key":"1395_CR3","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"PK Agarwal","year":"1999","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 (1999)","journal-title":"SIAM J. Comput."},{"key":"1395_CR4","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s00454-014-9626-1","volume":"52","author":"PK Agarwal","year":"2014","unstructured":"Agarwal, P.K., Har-Peled, S., Kaplan, H., Sharir, M.: Union of random Minkowski sums and network vulnerability analysis. Discret. Comput. Geom. 52, 551\u2013582 (2014)","journal-title":"Discret. Comput. Geom."},{"key":"1395_CR5","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Katz, M.J., Sharir, M.: On reverse shortest paths in geometric proximity graphs, Comput. Geom. Theory Appls. 117, Art.\u00a0102053. (2024), Also In Proc. 33rd Internat. Sympos. on Algorithms and Computation, 42:1-42:19 (2022)","DOI":"10.1016\/j.comgeo.2023.102053"},{"key":"1395_CR6","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, 325\u2013345 (1995)","journal-title":"Algorithmica"},{"issue":"3","key":"1395_CR7","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1137\/S0097539704446591","volume":"36","author":"PK Agarwal","year":"2006","unstructured":"Agarwal, P.K., Overmars, M.H., Sharir, M.: Computing maximally separated sets in the plane. SIAM J. Comput. 36(3), 815\u2013834 (2006)","journal-title":"SIAM J. Comput."},{"key":"1395_CR8","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.jcta.2004.12.008","volume":"111","author":"N Alon","year":"2005","unstructured":"Alon, N., Pach, J., Pinchasi, R., Radoi\u010di\u010d, R., Sharir, M.: Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A 111, 310\u2013326 (2005)","journal-title":"J. Combin. Theory Ser. A"},{"key":"1395_CR9","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, Singapore (2013)"},{"key":"1395_CR10","volume":"11","author":"R Ben Avraham","year":"2015","unstructured":"Ben Avraham, R., Filtser, O., Kaplan, H., Katz, M.J., Sharir, M.: The discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection. ACM Trans. Algorithms 11, 29 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"1395_CR11","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":"1395_CR12","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.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer Verlag, Berlin (2008)","edition":"3"},{"issue":"5","key":"1395_CR13","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1142\/S0218195903001268","volume":"13","author":"S Bespamyatnikh","year":"2003","unstructured":"Bespamyatnikh, S.: Computing closest points for segments. Int. J. Comput. Geom. Appl. 13(5), 419\u2013438 (2003)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1395_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0925-7721(99)00055-3","volume":"16","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Snoeyink, J.: Queries with segments in Voronoi diagrams. Comput. Geom. Theory Appls. 16, 23\u201333 (2000)","journal-title":"Comput. Geom. Theory Appls."},{"key":"1395_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0304-3975(80)90018-3","volume":"11","author":"N Blum","year":"1980","unstructured":"Blum, N., Mehlhorn, K.: On the average number of rebalancing operations in weight-balanced trees. Theor. Comput. Sci. 11, 303\u2013320 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"1395_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appls. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom. Theory Appls."},{"key":"1395_CR17","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. Theory Appls. 48, 360\u2013367 (2015)","journal-title":"Comput. Geom. Theory Appls."},{"key":"1395_CR18","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00454-012-9410-z","volume":"47","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: Optimal partition trees. Discrete Comput. Geom. 47, 661\u2013690 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"1395_CR19","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Dynamic generalized closest pair: Revisiting Eppstein\u2019s technique. In: Proc. 3rd Sympos. Simplicity in Algorithms (SOSA), vol. 2020, pp. 33\u201337","DOI":"10.1137\/1.9781611976014.6"},{"key":"1395_CR20","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Finding triangles and other small subgraphs in geometric intersection graphs. In: Proc. 34th ACM-SIAM Symposium on Discrete Algorithms, pp. 1777\u20131805. (2023)","DOI":"10.1137\/1.9781611977554.ch68"},{"key":"1395_CR21","unstructured":"Chan, T.M., Huang, Z.: Faster algorithms for reverse shortest path in unit-disk graphs and related geometric optimization problems: Improving the shrink-and-bifurcate technique, Proc. 41st Sympos. Comp. Geom. (SoCG), 2025, 32:1\u201332:14. arXiv:2504.06434"},{"key":"1395_CR22","unstructured":"Chan, T.M., Skrepetos, D.: All-pairs shortest paths in unit-disk graphs in slightly subquadratic time, Proc. 27th Internat. Sympos. on Algorithms and Computation, pp. 24:1\u201324:13 (2016)"},{"issue":"1","key":"1395_CR23","first-page":"27","volume":"10","author":"TM Chan","year":"2019","unstructured":"Chan, T.M., Skrepetos, D.: All-pairs shortest paths in geometric intersection graphs. J. Comput. Geom. 10(1), 27\u201341 (2019)","journal-title":"J. Comput. Geom."},{"issue":"2","key":"1395_CR24","first-page":"3","volume":"10","author":"TM Chan","year":"2019","unstructured":"Chan, T.M., Skrepetos, D.: Approximate shortest paths and distance oracles in weighted unit-disk graphs. J. Comput. Geom. 10(2), 3\u201320 (2019)","journal-title":"J. Comput. Geom."},{"key":"1395_CR25","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B.: Lower bounds on the complexity of polytope range searching. J. American Math. Society 2, 637\u2013666 (1989)","journal-title":"J. American Math. Society"},{"key":"1395_CR26","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M.: Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica 11, 116\u2013132 (1994)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"1395_CR27","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"1395_CR28","doi-asserted-by":"publisher","first-page":"5043","DOI":"10.1090\/S0002-9947-2014-06179-5","volume":"366","author":"D Conlon","year":"2014","unstructured":"Conlon, D., Fox, J., Pach, J., Sudakov, B., Suk, A.: Ramsey-type results for semi-algebraic hypergraphs. Trans. Amer. Math. Soc. 366, 5043\u20135065 (2014)","journal-title":"Trans. Amer. Math. Soc."},{"key":"1395_CR29","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02574030","volume":"13","author":"D Eppstein","year":"1995","unstructured":"Eppstein, D.: Fast hierarchical clustering and other applications of dynamic closest pairs. Discrete Comput. Geom. 13, 111\u2013122 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"1395_CR30","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF02712875","volume":"16","author":"J Erickson","year":"1996","unstructured":"Erickson, J.: New lower bounds for Hopcroft\u2019s problem. Discrete Comput. Geom. 16, 389\u2013418 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"1395_CR31","doi-asserted-by":"crossref","unstructured":"Fishkin, A.V.: Disk graphs: A short survey, Proc. 1st Internat. Workshop on Approximation and Online Algorithms, volume 2909 of Lecture Notes in Computer Science, pp. 260\u2013264, (2003)","DOI":"10.1007\/978-3-540-24592-6_23"},{"issue":"4","key":"1395_CR32","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1142\/S0218195917500078","volume":"27","author":"GD da Fonseca","year":"2017","unstructured":"da Fonseca, G.D., de S\u00e1, V.G.P., de Figueiredo, C.M.H.: Shifting coresets: Obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs. Int. J. Comput. Geom. Appl. 27(4), 255\u2013276 (2017)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1395_CR33","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J., Suk, A.: Density and regularity theorems for semi-algebraic hypergraphs. In: Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 1517\u20131530. (2015)","DOI":"10.1137\/1.9781611973730.100"},{"key":"1395_CR34","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Khan, A., Mari, M., M\u00f6mke, T., Pittu, M.R., Wiese, A.: A 3-approximation algorithm for maximum independent set of rectangles. In: Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, vol. 2022, pp. 894\u2013905","DOI":"10.1137\/1.9781611977073.38"},{"issue":"1","key":"1395_CR35","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/S0097539703436357","volume":"35","author":"J Gao","year":"2005","unstructured":"Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput. 35(1), 151\u2013169 (2005)","journal-title":"SIAM J. Comput."},{"key":"1395_CR36","unstructured":"Kaplan, H., Katz, M.J., Saban, R., Sharir, M.: The unweighted and weighted reverse shortest path problem for disk graphs, ACM Trans. Algorithms, accepted. Also in Proc. 31st European Sympos. Algorithms (2023), 67:1\u201367:14. arXiv:2307.14663"},{"key":"1395_CR37","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, 838\u2013904 (2020)","journal-title":"Discrete Comput. Geom."},{"key":"1395_CR38","unstructured":"Kaplan, H., Tarjan, R.E., Tsioutsiouliklis, K.: Faster kinetic heaps and their use in broadcast scheduling. In: Proc. 12th ACM-SIAM Sympos. on Discrete Algorithms, pp. 836\u2013844. (2001)"},{"key":"1395_CR39","doi-asserted-by":"publisher","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 Appls. 111, 101979 (2023)","journal-title":"Comput. Geom. Theory Appls."},{"key":"1395_CR40","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combinat. Theory Ser. B 62, 289\u2013315 (1994)","journal-title":"J. Combinat. Theory Ser. B"},{"issue":"3","key":"1395_CR41","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)","journal-title":"SIAM J. Comput."},{"key":"1395_CR42","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching, Springer (1984)","DOI":"10.1007\/978-3-642-69672-5"},{"key":"1395_CR43","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Multi-dimensional Searching and Computational Geometry. Data Structures and Algorithms 3, (1984) Springer","DOI":"10.1007\/978-3-642-69900-9_2"},{"key":"1395_CR44","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica 5, 215\u2013241 (1990)","journal-title":"Algorithmica"},{"key":"1395_CR45","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proc. 42nd IEEE Sympos. Foundations of Computer Science (FOCS), pp. 426\u2013431. (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"1395_CR46","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B.: Approximating maximum independent set for rectangles in the plane. In: Proc. 62nd IEEE Sympos. on Foundations of Computer Science, pp. 339\u2013350. (2021)","DOI":"10.1109\/FOCS52979.2021.00042"},{"key":"1395_CR47","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Milkov\u00e1, E., Ne\u0161et\u0159ilov\u00e1, H., Bor\u016fvka, O., on minimum spanning tree problem: translation of both the,: papers, comments, history. Discrete Math. 233(2001), 3\u201336 (1926)","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"1395_CR48","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J Nievergelt","year":"1973","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. SIAM J. Comput. 2, 33\u201343 (1973)","journal-title":"SIAM J. Comput."},{"key":"1395_CR49","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures. Lect. Notes Comput. Sci. 156, (1983) Springer"},{"key":"1395_CR50","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. Syst. Sci. 23, 166\u2013204 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"1395_CR51","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1985)"},{"issue":"4","key":"1395_CR52","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"},{"key":"1395_CR53","doi-asserted-by":"crossref","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Decidability of string graphs. In: Proc. Sympos. on Theory of Computing (STOC), pp. 241\u2013246. (2001)","DOI":"10.1145\/380752.380807"},{"key":"1395_CR54","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge-New York-Melbourne (1995)"},{"key":"1395_CR55","unstructured":"Wang, H.: Algorithms for computing closest points for segments, Proc. 41st Internat. Sympos. on Theoretical Aspects of Computer Science (STACS), 58:1\u201358:17 (2024)"},{"issue":"4","key":"1395_CR56","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s00454-020-00219-7","volume":"64","author":"H Wang","year":"2020","unstructured":"Wang, H., Xue, J.: Near-optimal algorithms for shortest paths in weighted unit-disk graphs. Discrete Comput. Geom. 64(4), 1141\u20131166 (2020)","journal-title":"Discrete Comput. Geom."},{"key":"1395_CR57","doi-asserted-by":"crossref","unstructured":"Wang, H., Zhao, Y.: Reverse shortest path problem for unit-disk graphs. In: Proc. 17th Internat. Sympos. on Algorithms and Data Structures, pp. 655\u2013668. (2021)","DOI":"10.1007\/978-3-030-83508-8_47"},{"key":"1395_CR58","doi-asserted-by":"crossref","unstructured":"Wang, H., Zhao, Y.: Reverse shortest path problem in weighted unit-disk graphs. In: Proc. 16th Internat. Conf. on Algorithms and Computation, vol. 2022, pp. 135\u2013146. ()","DOI":"10.1007\/978-3-030-96731-4_12"},{"key":"1395_CR59","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"DE Willard","year":"1985","unstructured":"Willard, D.E., Lueker, G.S.: Adding range restriction capability to dynamic data structures. J. ACM 32, 597\u2013617 (1985)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01395-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01395-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01395-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T06:10:46Z","timestamp":1786687846000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01395-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,15]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["1395"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01395-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,15]]},"assertion":[{"value":"13 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing Interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"55"}}