{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:26:20Z","timestamp":1760441180537},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,7,13]],"date-time":"2013-07-13T00:00:00Z","timestamp":1373673600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s00453-013-9809-9","type":"journal-article","created":{"date-parts":[[2013,7,12]],"date-time":"2013-07-12T18:35:35Z","timestamp":1373654135000},"page":"429-449","source":"Crossref","is-referenced-by-count":7,"title":["The k-Nearest-Neighbor Voronoi Diagram Revisited"],"prefix":"10.1007","volume":"71","author":[{"given":"Chih-Hung","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Der-Tsai","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,7,13]]},"reference":[{"issue":"6","key":"9809_CR1","doi-asserted-by":"crossref","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. Int. J. Comput. Geom. Appl. 19(6), 595\u2013615 (2009)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9809_CR2","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matou\u0161ek, J., Schwarzkopf, I.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"key":"9809_CR3","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"P.K. Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica 13, 325\u2013345 (1995)","journal-title":"Algorithmica"},{"issue":"1","key":"9809_CR4","doi-asserted-by":"crossref","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 Comput. Geom. 4(1), 591\u2013604 (1984)","journal-title":"Discrete Comput. Geom."},{"key":"9809_CR5","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0097-3165(86)90122-6","volume":"41","author":"N. Alon","year":"1986","unstructured":"Alon, N., Gy\u00f6ri, E.: The number of small semispaces of a finite set of points in the plane. J. Comb. Theory, Ser. A 41, 154\u2013157 (1986)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"1","key":"9809_CR6","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02187788","volume":"5","author":"F. Aurenhammer","year":"1990","unstructured":"Aurenhammer, F.: A new duality result concerning Voronoi diagrams. Discrete Comput. Geom. 5(1), 243\u2013254 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9809_CR7","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/B978-044482537-7\/50006-1","volume-title":"Handbook of Computational Geometry","author":"F. Aurenhammer","year":"2000","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Handbook of Computational Geometry, pp. 201\u2013290. Elsevier, Amsterdam (2000)"},{"issue":"4","key":"9809_CR8","doi-asserted-by":"crossref","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. Int. J. Comput. Geom. Appl. 2(4), 363\u2013381 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9809_CR9","doi-asserted-by":"crossref","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. Algorithmica 9, 329\u2013356 (1993)","journal-title":"Algorithmica"},{"key":"9809_CR10","first-page":"617","volume-title":"Proceeding of IEEE Symposium on Foundations of Computer Science","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proceeding of IEEE Symposium on Foundations of Computer Science, pp. 617\u2013626 (2002)"},{"issue":"2","key":"9809_CR11","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"T.M. Chan","year":"1998","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of (\u2264k)-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013572 (1998)","journal-title":"SIAM J. Comput."},{"key":"9809_CR12","doi-asserted-by":"crossref","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 3, 205\u2013221 (1988)","journal-title":"Algorithmica"},{"issue":"11","key":"9809_CR13","doi-asserted-by":"crossref","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. Comput. 36(11), 1349\u20131454 (1987)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"9809_CR14","doi-asserted-by":"crossref","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 Comput. Geom. 2(1), 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9809_CR15","doi-asserted-by":"crossref","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 Comput. Geom. 4(1), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9809_CR16","doi-asserted-by":"crossref","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. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9809_CR17","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Welzl, E.: Constructing belts of two-dimensional arrangements with applications. SIAM J. Comput. 15(1), 271\u2013284 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9809_CR18","doi-asserted-by":"crossref","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. Comput. Geom. Theory Appl. 23(1), 85\u201398 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9809_CR19","doi-asserted-by":"crossref","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. Appl. Math. 14, 255\u2013265 (1966)","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"9809_CR20","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"D.T. Lee","year":"1980","unstructured":"Lee, D.T.: Two-dimensional Voronoi diagrams in the L p -metric. J. ACM 27(4), 604\u2013618 (1980)","journal-title":"J. ACM"},{"issue":"6","key":"9809_CR21","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. Comput. 31(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"key":"9809_CR22","first-page":"70","volume-title":"Proceeding of European Symposium on Algorithms","author":"C.-H. Liu","year":"2011","unstructured":"Liu, C.-H., Papadopoulou, E., Lee, D.T.: An output-sensitive approach for the L 1\/L \u221e k-nearest-neighbor Voronoi diagram. In: Proceeding of European Symposium on Algorithms, pp. 70\u201381 (2011)"},{"key":"9809_CR23","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01758836","volume":"8","author":"J.S.B. Mitchell","year":"1992","unstructured":"Mitchell, J.S.B.: L 1 shortest paths among polygonal obstacles in the plane. Algorithmica 8, 55\u201388 (1992)","journal-title":"Algorithmica"},{"issue":"1","key":"9809_CR24","doi-asserted-by":"crossref","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 Comput. Geom. 6(1), 307\u2013338 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"9809_CR25","doi-asserted-by":"crossref","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. Comput.-Aided Des. Integr. Circuits Syst. 20(5), 583\u2013597 (2001)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"issue":"5","key":"9809_CR26","doi-asserted-by":"crossref","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. Comput.-Aided Des. Integr. Circuits Syst. 30(5), 704\u2013716 (2011)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"issue":"5","key":"9809_CR27","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1142\/S0218195901000626","volume":"11","author":"E. Papadopoulou","year":"2001","unstructured":"Papadopoulou, E., Lee, D.-T.: The L \u221e Voronoi diagram of segments and VLSI applications. Int. J. Comput. Geom. Appl. 11(5), 503\u2013528 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9809_CR28","first-page":"390","volume-title":"Proceeding of ACM Symposium on Computational Geometry","author":"E. Ramos","year":"1999","unstructured":"Ramos, E.: On range reporting, ray shooting, and k-level construction. In: Proceeding of ACM Symposium on Computational Geometry, pp. 390\u2013399 (1999)"},{"key":"9809_CR29","series-title":"LNCS","first-page":"290","volume-title":"Proceeding of Japanese Conference on Discrete and Computational Geometry","author":"D. Schmitt","year":"1998","unstructured":"Schmitt, D., Spehner, J.C.: Order-k Voronoi diagrams, k-sections, and k-sets. In: Proceeding of Japanese Conference on Discrete and Computational Geometry. LNCS, vol. 1763, pp. 290\u2013304 (1998)"},{"key":"9809_CR30","first-page":"151","volume-title":"Proceeding of IEEE Symposium on Foundations of Computer Science","author":"M. Shamos","year":"1975","unstructured":"Shamos, M., Hoey, D.: Closest point problems. In: Proceeding of IEEE Symposium on Foundations of Computer Science, pp. 151\u2013162 (1975)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9809-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9809-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9809-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:12Z","timestamp":1559137512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9809-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,13]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9809"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9809-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,13]]}}}