{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,12]],"date-time":"2025-07-12T01:08:42Z","timestamp":1752282522532},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_7","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"70-81","source":"Crossref","is-referenced-by-count":5,"title":["An Output-Sensitive Approach for the L 1\/L \u2009\u221e\u2009 k-Nearest-Neighbor Voronoi Diagram"],"prefix":"10.1007","author":[{"given":"Chih-Hung","family":"Liu","sequence":"first","affiliation":[]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[]},{"given":"D. T.","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"7_CR1","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1142\/S0218195909003143","volume":"19","author":"M. Abellanas","year":"2009","unstructured":"Abellanas, M., Bose, P., Garcia, J., Hurtado, F., Nicolas, C.M., Ramos, P.A.: On structural and graph theoretic properties of higher order Delaunay graphs. Internat. J. Comput. Geom. Appl.\u00a019(6), 595\u2013615 (2009)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"3","key":"7_CR2","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matousek, J., Schwarzkopf, I.: Constructing levels in arrangements and higher order Voronoi diagrams. Siam J. on Computing\u00a027(3), 654\u2013667 (1998)","journal-title":"Siam J. on Computing"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1984","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing Voronoi diagram of a convex polygon. Discrete and Computational Geometry\u00a04, 591\u2013604 (1984)","journal-title":"Discrete and Computational Geometry"},{"key":"7_CR4","volume-title":"Handbook of Computational Geometry","author":"F. Aurenhammer","year":"2000","unstructured":"Aurenhammer, F., Klein, R.: Voronoi Diagrams. In: Handbook of Computational Geometry. Elseiver, Amsterdam (2000)"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1142\/S0218195992000214","volume":"2","author":"F. Aurenhammer","year":"1992","unstructured":"Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Internat. J. Comput. Geom. Appl.\u00a02, 363\u2013381 (1992)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01228508","volume":"9","author":"J.D. Boissonnat","year":"1993","unstructured":"Boissonnat, J.D., Devillers, O., Teillaud, M.: A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmia\u00a09, 329\u2013356 (1993)","journal-title":"Algorithmia"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01762115","volume":"3","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: An algorithm for segment dragging and its implementation. Algorithmica\u00a03, 205\u2013221 (1988)","journal-title":"Algorithmica"},{"issue":"11","key":"7_CR8","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1109\/TC.1987.5009474","volume":"36","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi Diagram. IEEE Trans. on Computers\u00a036(11), 1349\u20131454 (1987)","journal-title":"IEEE Trans. on Computers"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K.L. Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete and Computational Geometry\u00a02, 195\u2013222 (1987)","journal-title":"Discrete and Computational Geometry"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete and Computational Geometry\u00a04, 387\u2013421 (1989)","journal-title":"Discrete and Computational Geometry"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. on Computing\u00a015, 341\u2013363 (1986)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"7_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0925-7721(01)00027-X","volume":"23","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Hammar, M., van Kreveld, M.: Higher order Delaunay triangulations. Computaional Geometry\u00a023(1), 85\u201398 (2002)","journal-title":"Computaional Geometry"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M. Hanan","year":"1966","unstructured":"Hanan, M.: On Steiner\u2019s problem with rectilinear distance. SIAM J. on Applied Mathematics\u00a014, 255\u2013265 (1966)","journal-title":"SIAM J. on Applied Mathematics"},{"issue":"6","key":"7_CR14","first-page":"478","volume":"31","author":"D.-T. Lee","year":"1982","unstructured":"Lee, D.-T.: On k-nearest neighbor Voronoi Diagrams in the plane. IEEE Trans. on Computers\u00a031(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. on Computers"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"J.S.B. Mitchell","year":"1992","unstructured":"Mitchell, J.S.B.: L1 Shortest Paths Among Polygonal Obstacles in the Plane. Algorithmica\u00a08, 55\u201388 (1992)","journal-title":"Algorithmica"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K. Mulmuley","year":"1991","unstructured":"Mulmuley, K.: On levels in arrangements and Voronoi diagrams. Discrete and Computational Geometry\u00a06, 307\u2013338 (1991)","journal-title":"Discrete and Computational Geometry"},{"issue":"5","key":"7_CR17","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1109\/43.920683","volume":"20","author":"E. Papadopoulou","year":"2001","unstructured":"Papadopoulou, E.: Critical Area computation for missing material defects in VLSI circuits. IEEE Trans. on CAD\u00a020(5), 583\u2013597 (2001)","journal-title":"IEEE Trans. on CAD"},{"issue":"5","key":"7_CR18","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1109\/TCAD.2010.2100550","volume":"30","author":"E. Papadopoulou","year":"2011","unstructured":"Papadopoulou, E.: Net-aware Critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans. on CAD\u00a030(5), 704\u2013716 (2011)","journal-title":"IEEE Trans. on CAD"},{"issue":"5","key":"7_CR19","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1142\/S0218195901000626","volume":"11","author":"E. Papadopoulou","year":"2001","unstructured":"Papadopoulou, E., Lee, D.-T.: The L\n                  \u2009\u221e\u2009 Voronoi Diagram of Segments and VLSI Applications. Internat. J. Comput. Geom. Appl.\u00a011(5), 503\u2013528 (2001)","journal-title":"Internat. J. Comput. Geom. Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T11:14:40Z","timestamp":1554117280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}