{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T07:25:58Z","timestamp":1759389958673,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00624-2","type":"journal-article","created":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T14:42:58Z","timestamp":1567780978000},"page":"915-937","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9683-5982","authenticated-orcid":false,"given":"Chih-Hung","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"issue":"1\u20134","key":"624_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01553882","volume":"4","author":"B Aronov","year":"1989","unstructured":"Aronov, B.: On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4(1\u20134), 109\u2013140 (1989)","journal-title":"Algorithmica"},{"key":"624_CR2","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":"624_CR3","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"624_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"624_CR5","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","volume":"39","author":"LJ Guibas","year":"1989","unstructured":"Guibas, L.J., Hershberger, J.: Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci. 39(2), 126\u2013152 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20134","key":"624_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"LJ Guibas","year":"1987","unstructured":"Guibas, L.J., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1\u20134), 209\u2013233 (1987)","journal-title":"Algorithmica"},{"issue":"5","key":"624_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0020-0190(91)90064-O","volume":"38","author":"J Hershberger","year":"1991","unstructured":"Hershberger, J.: A new data structure for shortest path queries in a simple polygon. Inf. Process. Lett. 38(5), 231\u2013235 (1991)","journal-title":"Inf. Process. Lett."},{"key":"624_CR8","unstructured":"Liu, C.-H.: A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon. In: 34th International Symposium on Computational Geometry, SoCG 2018, June 11\u201314, 2018, Budapest, Hungary, pp. 58:1\u201358:14 (2018)"},{"key":"624_CR9","unstructured":"Mehlhorn, K., Sanders, P..: Sorted sequences. In: Algorithms and Data Structures: The Basic Toolbox. Springer, Berlin (2008)"},{"key":"624_CR10","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"JSB Mitchell","year":"2000","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, Amsterdam (2000)"},{"key":"624_CR11","unstructured":"Oh, E., Ahn, H.-K.: Voronoi diagrams for a moderate-sized point-set in a simple polygon. In: 33rd International Symposium on Computational Geometry, SoCG 2017, July 4\u20137, 2017, Brisbane, Australia, pp. 52:1\u201352:15 (2017)"},{"issue":"4","key":"624_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/PL00009199","volume":"20","author":"E Papadopoulou","year":"1998","unstructured":"Papadopoulou, E., Lee, D.T.: A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains. Algorithmica 20(4), 319\u2013352 (1998)","journal-title":"Algorithmica"},{"issue":"5","key":"624_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0020-0190(83)90099-6","volume":"16","author":"RE Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Updating a balanced search tree in O(1) rotations. Inf. Process. Lett. 16(5), 253\u2013257 (1983)","journal-title":"Inf. Process. Lett."},{"key":"624_CR14","unstructured":"Tarjan, R.E.: Efficient Top-Down Updating of Red\u2013Black Trees. Technical Report TR-006-85. Department of Computer Science, Princeton University (1985)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00624-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00624-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00624-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,3]],"date-time":"2020-09-03T23:30:30Z","timestamp":1599175830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00624-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["624"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00624-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,9,5]]},"assertion":[{"value":"22 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}