{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:09Z","timestamp":1787322849798,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100009031","name":"Collaborative Research Based on Industrial Demand","doi-asserted-by":"publisher","award":["17K12635"],"award-info":[{"award-number":["17K12635"]}],"id":[{"id":"10.13039\/501100009031","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1201"],"award-info":[{"award-number":["JPMJER1201"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422311"],"award-info":[{"award-number":["CCF-1422311"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["612.001.651"],"award-info":[{"award-number":["612.001.651"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks, we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.<\/jats:p>","DOI":"10.1137\/20m1384804","type":"journal-article","created":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T04:31:50Z","timestamp":1697085110000},"page":"2276-2311","source":"Crossref","is-referenced-by-count":2,"title":["Kinetic Geodesic Voronoi Diagrams in a Simple Polygon"],"prefix":"10.1137","volume":"37","author":[{"given":"Matias","family":"Korman","sequence":"first","affiliation":[{"name":"Siemens Electronic Design Automation, Wilsonville, OR 97070 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9294-9947","authenticated-orcid":true,"given":"Andr\u00e9","family":"van Renssen","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Sydney, Sydney, NSW 2006, Australia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcel","family":"Roeloffzen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, 5612 AZ, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, 3584 CS, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,10,12]]},"reference":[{"key":"ref1","unstructured":"P. K. Agarwal , \nL. Arge , and \nF. Staals  , Improved dynamic geodesic nearest neighbor searching in a simple polgyon, in Proc. 34th Annual Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 99, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2018, 4, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.4."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9729-3"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195914600097"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553882"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189321"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0089-9"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.10.009"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0988"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"G. S. Brodal  and \nR. Jacob  , Dynamic planar convex hull, in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 617\u2013626, https:\/\/doi.org\/10.1109\/SFCS.2002.1181985.","DOI":"10.1109\/SFCS.2002.1181985"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0961-x"},{"key":"ref12","unstructured":"E. D. Demaine , \nJ. S. B. Mitchell , and \nJ. O\u2019Rourke  , The Open Problems Project, https:\/\/topp.openproblem.net\/."},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"ref14","series-title":"Discrete Math. Appl.","volume-title":"Handbook of Discrete and Computational Geometry","author":"Goodman J. E.","year":"2004"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55121-2_11"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"ref19","unstructured":"M. I. Karavelas  and \nL. J. Guibas  , Static and kinetic geometric spanners with applications, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201901, SIAM, Philadelphia, 2001, pp. 168\u2013176."},{"key":"ref20","unstructured":"M. Korman , \nA. van Renssen , \nM. Roeloffzen , and \nF. Staals  , Kinetic geodesic Voronoi diagrams in a simple polygon, in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), LIPIcs. Leibniz Int. Proc. Inform. 168, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2020, 75, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.75."},{"key":"ref21","unstructured":"C.H. Liu  , A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon, in 34th International Symposium on Computational Geometry (SoCG 2018), LIPIcs. Leibniz Int. Proc. Inform. 99, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2018, 58, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.58."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2017.07.001"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530888"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell  , Shortest paths among obstacles in the plane, in Proceedings of the 9th Annual ACM Symposium on Computational Geometry, 1993, pp. 308\u2013317.","DOI":"10.1145\/160985.161156"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"E. Oh  , Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2019, pp. 391\u2013409, https:\/\/doi.org\/10.1137\/1.9781611975482.25.","DOI":"10.1137\/1.9781611975482.25"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00063-4"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2019.05.001"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.02.008"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009199"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187751"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/2746228"},{"key":"ref32","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"Sharir M.","year":"1995"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(86)90127-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1384804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:29:10Z","timestamp":1787318950000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1384804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/20M1384804"],"URL":"https:\/\/doi.org\/10.1137\/20m1384804","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]}}}