{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:08:27Z","timestamp":1787389707050,"version":"build-2736575974"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University"},{"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\/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\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161"],"award-info":[{"award-number":["1161"]}],"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"],"award-info":[{"award-number":["1367"]}],"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"],"award-info":[{"award-number":["1367"]}],"id":[{"id":"10.13039\/501100001736","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\/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\/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\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["260\/18"],"award-info":[{"award-number":["260\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["794\/13"],"award-info":[{"award-number":["794\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["592\/17"],"award-info":[{"award-number":["592\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\\tilde O(nb^2)$ time so that one can compute any additively weighted Voronoi diagram for these sites in $\\tilde O(b)$ time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in $\\tilde{O}(n^{5\/3})$ time. This improves the recent breakthrough result of Cabello [ SODA 2017, SIAM, Philadelphia, 2017, pp. 2143--2152], both by improving the running time (from $\\tilde{O}(n^{11\/6})$), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex $v$, both the farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum of distances from $v$ to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest.<\/jats:p>","DOI":"10.1137\/18m1193402","type":"journal-article","created":{"date-parts":[[2021,4,1]],"date-time":"2021-04-01T11:22:07Z","timestamp":1617276127000},"page":"509-554","source":"Crossref","is-referenced-by-count":11,"title":["Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\\tilde{O}(n^{5\/3})$ Time"],"prefix":"10.1137","volume":"50","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":true,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,1]]},"reference":[{"key":"atypb1","first-page":"476","author":"Abboud A.","year":"2016","journal-title":"NJ"},{"key":"atypb2","first-page":"1681","author":"Abboud A.","year":"2015","journal-title":"PA"},{"key":"atypb3","first-page":"1","author":"Abboud A.","year":"2013","journal-title":"Berlin"},{"key":"atypb4","first-page":"434","author":"Abboud A.","year":"2014","journal-title":"NJ"},{"key":"atypb5","first-page":"377","author":"Abboud A.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb6","first-page":"41","author":"Abboud A.","year":"2015","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"atypb9","first-page":"81","author":"Backurs A.","year":"2016","journal-title":"Germany"},{"key":"atypb10","unstructured":"A. Backurs and C. Tzamos,\n                      Improving Viterbi is hard: Better runtimes imply faster clique algorithms\n                      , Proc. Mach. Learn. Res. (PMLR), 70 (2017), pp. 311-321."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.033"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,\n                      Computational Geometry: Algorithms and Applications\n                      , 3rd ed., Springer, Berlin, 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb13","first-page":"1190","author":"Bringmann K.","year":"2018","journal-title":"Philadelphia"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/3218821"},{"issue":"2103","key":"atypb15","first-page":"1542","volume":"42","author":"Cabello S.","journal-title":"SIAM J. Comput."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.02.001"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"T. M. Chan,\n                      \n                        All-pairs shortest paths for unweighted undirected graphs in\n                        o(mn)\n                        time\n                      \n                      , in SODA, 2006, SIAM, Philadelphia, pp. 514-523.","DOI":"10.1145\/1109557.1109614"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9062-1"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/08071990X"},{"key":"atypb20","first-page":"138","author":"Charalampopoulos P.","year":"2019","journal-title":"New York"},{"key":"atypb21","first-page":"159","author":"Chepoi V.","year":"1994","journal-title":"Berlin"},{"key":"atypb22","first-page":"59","author":"Chepoi V.","year":"2008","journal-title":"New York"},{"key":"atypb23","first-page":"346","author":"Chepoi V.","year":"2002","journal-title":"Philadelphia"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"atypb25","first-page":"962","author":"Cohen-Addad V.","year":"2017","journal-title":"NJ"},{"key":"atypb26","first-page":"100","author":"\u00c9","year":"2010","journal-title":"Berlin"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1080\/00207169008803814"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00157-2"},{"key":"atypb29","first-page":"632","author":"Eppstein D.","year":"1995","journal-title":"Philadelphia"},{"key":"atypb30","first-page":"1319","author":"Erickson J.","year":"2018","journal-title":"New York"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(80)90039-6"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"R. Floyd,\n                      Algorithm 97: Shortest path\n                      , Commun. ACM, 5 (1962), p. 345.","DOI":"10.1145\/367766.368168"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"atypb36","first-page":"515","author":"Gawrychowski P.","year":"2018","journal-title":"Philadelphia"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.006"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9063-0"},{"key":"atypb39","first-page":"131","author":"Han Y.","year":"2012","journal-title":"Berlin"},{"key":"atypb40","first-page":"403","volume":"7","author":"Hartvigsen D.","year":"1994","journal-title":"J. Discrete Math."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793253577"},{"key":"atypb44","first-page":"16","author":"Husfeldt T.","year":"2016","journal-title":"Germany"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb46","first-page":"146","author":"Klein P. N.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb48","first-page":"505","author":"Klein P. N.","year":"2013","journal-title":"New York"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"R. Klein,\n                      Concrete and Abstract Voronoi Diagrams\n                      , Lecture Notes in Comput. Sci. 400, Springer, New York, 1989.","DOI":"10.1007\/3-540-52055-4"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.002"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90033-3"},{"key":"atypb52","first-page":"865","author":"Marx D.","year":"2015","journal-title":"Berlin"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1080\/00207169008803870"},{"key":"atypb54","first-page":"515","author":"Roditty L.","year":"2013","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey,\n                      Closest-point problems\n                      , in FOCS, IEEE Computer Society, Los Alamitos, CA, 1975, pp. 151-162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90200-F"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.08.008"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"V. Vassilevska Williams and R. Williams,\n                      Subcubic equivalences between path, matrix and triangle problems\n                      , in FOCS, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 645-654.","DOI":"10.1109\/FOCS.2010.67"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"atypb63","first-page":"664","author":"Williams R.","year":"2014","journal-title":"New York"},{"key":"atypb64","doi-asserted-by":"crossref","unstructured":"C. Wulff-Nilsen,\n                      Wiener Index and Diameter of a Planar Graph in Subquadratic Time\n                      , Technical report, 08-16, Department of Computer Science, University of Copenhagen, Copenhagen (2008).","DOI":"10.1007\/978-3-540-92182-0_65"},{"key":"atypb65","unstructured":"C. Wulff-Nilsen,\n                      Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time\n                      , Ph.D. thesis, Copenhagen, Copenhagen (2010)."},{"key":"atypb66","first-page":"921","author":"Zwick U.","year":"2004","journal-title":"Berlin"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1193402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:34Z","timestamp":1787339974000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1193402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/18M1193402"],"URL":"https:\/\/doi.org\/10.1137\/18m1193402","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}