{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,12]],"date-time":"2025-04-12T05:08:37Z","timestamp":1744434517076},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p> Given a set P of n point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using O((c+n) polylog (c+n)) time and storage by means of a wavefront expansion. For [Formula: see text] our algorithm is faster than an algorithm by Aichholzer et al., which takes O(n log n + c<jats:sup>2<\/jats:sup> log c) time. <\/jats:p>","DOI":"10.1142\/s0218195908002623","type":"journal-article","created":{"date-parts":[[2008,8,13]],"date-time":"2008-08-13T11:09:14Z","timestamp":1218625754000},"page":"275-294","source":"Crossref","is-referenced-by-count":9,"title":["CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER"],"prefix":"10.1142","volume":"18","author":[{"given":"ROBERT","family":"G\u00d6RKE","sequence":"first","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, P.O. Box 6980, D-76128 Karlsruhe, Germany"}]},{"given":"CHAN-SU","family":"SHIN","sequence":"additional","affiliation":[{"name":"School of Digital Information Engineering, Hankuk University of Foreign Studies, Yongin, Korea"}]},{"given":"ALEXANDER","family":"WOLFF","sequence":"additional","affiliation":[{"name":"Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, Postbus 513, 5600 MB Eindhoven, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00505-7"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556395"},{"key":"rf4","first-page":"752","volume":"1","author":"Aichholzer O.","journal-title":"J. Universal Comput. Sci."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2947-0"},{"key":"rf7","series-title":"Lecture Notes Comput. Sci","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1007\/11602613_100","volume":"3827","author":"Bae S. W.","year":"2005"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029813"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009479"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2.3.253"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102784"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195908002623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:23:02Z","timestamp":1565137382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195908002623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":12,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0218195908002623"],"URL":"https:\/\/doi.org\/10.1142\/s0218195908002623","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}