{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T16:46:14Z","timestamp":1777567574448,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540507284","type":"print"},{"value":"9783540460763","type":"electronic"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"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":[[1989]]},"DOI":"10.1007\/3-540-50728-0_61","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:32:52Z","timestamp":1330201972000},"page":"434-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Voronoi diagrams in the moscow metric"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Klein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"30_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":"30_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":"30_CR3","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. 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":"30_CR4","doi-asserted-by":"crossref","unstructured":"F. Dehne and R. Klein, \u201cA sweepcircle algorithm for Voronoi diagrams\u201d, presented at the Workshop on Graph-Theoretic Concepts in Computer Science (WG 87), Staffelstein, 1987. To appear in LNCS.","DOI":"10.1007\/3-540-19422-3_5"},{"issue":"2","key":"30_CR5","doi-asserted-by":"crossref","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":"30_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":"30_CR7","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\u2013291.","DOI":"10.1007\/BFb0035852"},{"key":"30_CR8","doi-asserted-by":"crossref","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\np metric\u201d, JACM 27, 1980, pages 604\u2013618.","journal-title":"JACM"},{"issue":"3","key":"30_CR9","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata, \u201cEuclidean shortest paths in the presence of rectilinear barriers\u201d, Networks 14(3), pages 393\u2013410.","journal-title":"Networks"},{"key":"30_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\n1 (L\n\u221e) metrics with 2-dimensional storage applications\u201d, SIAM J. COMPUT. 9, 1980, pages 200\u2013211.","journal-title":"SIAM J. COMPUT."},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell and Ch. H. Papadimitriou, \u201cThe weighted region problem\u201d, Proc. 3rd ACM Symposium on Computational Geometry, Waterloo, 1987, pages 30\u201338.","DOI":"10.1145\/41958.41962"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, \u201cClosest-point problems\u201d, Proc 16th IEEE Symposium on Foundations of Computer Science, 1975, pages 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"30_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","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:15:11Z","timestamp":1578525311000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_61"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}