{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:34:19Z","timestamp":1759336459163,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540503354"},{"type":"electronic","value":"9783540459750"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50335-8_31","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:21:13Z","timestamp":1330201273000},"page":"148-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Abstract voronoi diagrams and their applications"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Klein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"B. Aronov, \u201cOn the geodesic Voronoi diagram of point sites in a simple polygon\u201d, Proc. 3rd ACM Symposium on Computational Geometry, Waterloo, 1987, pages 39\u201349.","DOI":"10.1145\/41958.41963"},{"key":"12_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","volume":"9","author":"K. Q. Brown","year":"1979","unstructured":"K. Q. Brown, \u201cVoronoi diagrams from convex hulls\u201d, Inf. Proc. Lett. 9, pages 223\u2013228, 1979.","journal-title":"Inf. Proc. Lett."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"L. P. Drysdale, III, \u201cVoronoi diagrams based on convex distance functions\u201d, Proc. 1st ACM Symposium on Computational Geometry, Baltimore, 1985, pages 235\u2013244.","DOI":"10.1145\/323233.323264"},{"key":"12_CR4","volume-title":"Planning, Geometry, and Complexity of Robot Motion","author":"C. \u00f3'D\u00fanlaing","year":"1986","unstructured":"C. \u00f3'D\u00fanlaing and C. K. Yap, \u201dA retraction method for planning the motion of a disc\u201d, in J. Schwartz, M. Sharir, and J. Hopcroft (eds.), Planning, Geometry, and Complexity of Robot Motion, Ablex Publishing Corp., Norwood, NJ, 1986."},{"issue":"2","key":"12_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune, \u201cA sweepline algorithm for Voronoi diagrams\u201d, Algorithmica 2 (2), 1987, pages 153\u2013174.","journal-title":"Algorithmica"},{"key":"12_CR6","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"F. K. Hwang, \u201cAn O(n log n) algorithm for rectilinear minimal spanning trees\u201d, JACM 26, 1979, pages 177\u2013182.","journal-title":"JACM"},{"key":"12_CR7","unstructured":"R. Klein, \u201cVoronoi diagrams in the Moscow metric\u201d, Technical Report No 7, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, to be presented at WG '88, Amsterdam."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"R. Klein and D. Wood, \u201cVoronoi diagrams based on general metrics in the plane\u201d, in R. Cori and M. Wirsing (eds.), Proc. 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Bordeaux, France, 1988, LNCS, pages 281\u2013191.","DOI":"10.1007\/BFb0035852"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee, \u201cTwo-dimensional Voronoi diagrams in the L p metric\u201d, JACM 27, 1980, pages 604\u2013618.","journal-title":"JACM"},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee and C. K. Wong, \u201cVoronoi diagrams in L 1 (L \u221e metrics with 2-dimensional storage applications\u201d, SIAM J. COMPUT. 9, 1980, pages 200\u2013211.","journal-title":"SIAM J. COMPUT."},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"F. Preparata and I. Shamos, \u201cComputational Geometry\u201d An Introduction, Springer, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, \u201cClosest-point problems\u201d, Proc. 6th IEEE Symposium on Foundations of Computer Science, 1975, pages 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"P. Widmayer, Y. F. Wu, and C. K. Wong, \u201cDistance problems in computational geometry for fixed orientations\u201d, Proc. 1st ACM Symposium on Computational Geometry, Baltimore, 1985, pages 186\u2013195.","DOI":"10.1145\/323233.323258"}],"container-title":["Lecture Notes in Computer Science","Computational Geometry and its Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50335-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:45:53Z","timestamp":1742589953000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50335-8_31"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540503354","9783540459750"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-50335-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}