{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:54:38Z","timestamp":1725738878652},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_18","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"208-219","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Higher Order Abstract Voronoi Diagrams"],"prefix":"10.1007","author":[{"given":"Cecilia","family":"Bohler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Cheilaris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maksym","family":"Zavershynskyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Abellanas, M., Hurtado, F., Palop, B.: Transportation Networks and Voronoi Diagrams. In: Proceedings International Symposium on Voronoi Diagrams in Science and Engineering (2004)"},{"issue":"2","key":"18_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0925-7721(02)00167-0","volume":"26","author":"H.-K. Ahn","year":"2003","unstructured":"Ahn, H.-K., Cheong, O., van Oostrum, R.: Casting a Polyhedron with Directional Uncertainty. Computational Geometry: Theory and Applications\u00a026(2), 129\u2013141 (2003)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"7","key":"18_CR3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s00454-003-2947-0","volume":"31","author":"O. Aichholzer","year":"2004","unstructured":"Aichholzer, O., Aurenhammer, F., Palop, B.: Quickest Paths, Straight Skeletons, and the City Voronoi Diagram. Discrete and Computational Geometry\u00a031(7), 17\u201335 (2004)","journal-title":"Discrete and Computational Geometry"},{"issue":"1","key":"18_CR4","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory, Ser. A\u00a041(1), 154\u2013157 (1986)","journal-title":"Journal of Combinatorial Theory, Ser. A"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F. Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys\u00a023(3), 345\u2013405 (1991)","journal-title":"ACM Computing Surveys"},{"issue":"6","key":"18_CR6","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F. Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R., Krasser, H.: Farthest Line Segment Voronoi Diagrams. Information Processing Letters\u00a0100(6), 220\u2013225 (2006)","journal-title":"Information Processing Letters"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Klein, R.: Voronoi Diagrams. In: Sack, J.R., Urrutia, G. (eds.) Handbook on Computational Geometry, pp. 201\u2013290. Elsevier (1999)","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company (to appear, 2013)","DOI":"10.1142\/8685"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1142\/S0218195906001963","volume":"16","author":"S.W. Bae","year":"2006","unstructured":"Bae, S.W., Chwa, K.-Y.: Voronoi Diagrams for a Transportation Network on the Euclidean Plane. International Journal on Computational Geometry and Applications\u00a016, 117\u2013144 (2006)","journal-title":"International Journal on Computational Geometry and Applications"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Wormser, C., Yvinec, M.: Curved Voronoi Diagrams. In: Boissonnat, J.D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces. Springer, Mathematics and Visualization (2006)","DOI":"10.1007\/978-3-540-33259-6"},{"key":"18_CR11","unstructured":"Descartes, R.: Principia Philosophiae. Ludovicus Elzevirius, Amsterdam, 1644"},{"key":"18_CR12","unstructured":"Fortune, S.: Voronoi Diagrams and Delaunay Triangulations. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 20, pp. 377\u2013388. CRC Press LLC (1997)"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0097-3165(80)90011-4","volume":"29","author":"J.E. Goodman","year":"1980","unstructured":"Goodman, J.E., Pollack, R.: On the Combinatorial Classification of Non-Degenerate Configurations in the Plane. Journal of Combinatorial Theory, Ser. A\u00a029, 220\u2013235 (1980)","journal-title":"Journal of Combinatorial Theory, Ser. A"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-540-39658-1_32","volume-title":"Algorithms - ESA 2003","author":"M.I. Karavelas","year":"2003","unstructured":"Karavelas, M.I., Yvinec, M.: The Voronoi Diagram of Planar Convex Objects. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 337\u2013348. Springer, Heidelberg (2003)"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"R. Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. LNCS, vol.\u00a0400. Springer, Heidelberg (1989)"},{"issue":"9","key":"18_CR16","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R. Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi Diagrams Revisited. Computational Geometry: Theory and Applications\u00a042(9), 885\u2013902 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R. Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized Incremental Construction of Abstract Voronoi Diagrams. Computational Geometry: Theory and Applications\u00a03, 157\u2013184 (1993)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"6","key":"18_CR18","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. Computers\u00a031(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Computers"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-23719-5_7","volume-title":"Algorithms \u2013 ESA 2011","author":"C.-H. Liu","year":"2011","unstructured":"Liu, C.-H., Papadopoulou, E., Lee, D.T.: An Output-Sensitive Approach for the L\n                           1\/L\u2009\u221e\u2009 k-Nearest-Neighbor Voronoi Diagram. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 70\u201381. Springer, Heidelberg (2011)"},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF02574686","volume":"6","author":"K. Mehlhorn","year":"1991","unstructured":"Mehlhorn, K., Meiser, S., \u00d3\u2019D\u00fanlaing, C.: On the Construction of Abstract Voronoi Diagrams. Discrete and Computational Geometry\u00a06, 211\u2013224 (1991)","journal-title":"Discrete and Computational Geometry"},{"issue":"6","key":"18_CR21","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1142\/S0218195901000663","volume":"11","author":"K. Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Meiser, S., Rasch, R.: Furthest Site Abstract Voronoi Diagrams. International Journal of Computational Geometry and Applications\u00a011(6), 583\u2013616 (2001)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley Series in Probability and Statistics (2000)","DOI":"10.1002\/9780470317013"},{"key":"18_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-35261-4_21","volume-title":"Algorithms and Computation","author":"E. Papadopoulou","year":"2012","unstructured":"Papadopoulou, E., Zavershynskyi, M.: On Higher Order Voronoi Diagrams of Line Segments. In: Chao, K.-M., Hsu, T.-s., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 177\u2013186. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:41:18Z","timestamp":1557913278000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}