{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T01:08:44Z","timestamp":1725844124780},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319278629"},{"type":"electronic","value":"9783319278636"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-27863-6_71","type":"book-chapter","created":{"date-parts":[[2015,12,17]],"date-time":"2015-12-17T11:15:54Z","timestamp":1450350954000},"page":"755-766","source":"Crossref","is-referenced-by-count":0,"title":["Computing Voronoi Diagrams of Line Segments in \u211d K in O(n log n) Time"],"prefix":"10.1007","author":[{"given":"Jeffrey W.","family":"Holcomb","sequence":"first","affiliation":[]},{"given":"Jorge A.","family":"Cobb","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,18]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Delahaye, D., Puechmorel, S.: 3D airspace sectoring by evolutionary computation. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 1637\u20131644 (2006)","key":"71_CR1","DOI":"10.1145\/1143997.1144267"},{"key":"71_CR2","doi-asserted-by":"publisher","first-page":"3842","DOI":"10.1016\/j.patcog.2008.06.007","volume":"41","author":"A Cheddad","year":"2008","unstructured":"Cheddad, A., Mohamad, D., Manaf, A.: Exploiting voronoi diagram properties in face segmentation and feature extraction. Pattern Recogn. 41, 3842\u20133859 (2008)","journal-title":"Pattern Recogn."},{"doi-asserted-by":"crossref","unstructured":"Sabha, M., Dutr\u00e9, P.: Feature-based texture synthesis and editing using voronoi diagrams. In: Sixth International Symposium on Voronoi Diagrams, pp. 165\u2013170 (2009)","key":"71_CR3","DOI":"10.1109\/ISVD.2009.29"},{"key":"71_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02716576","volume":"15","author":"PD Agarwal","year":"1996","unstructured":"Agarwal, P.D., Shwarzkopf, O., Harir, M.: The Overlay of Lower Envelopes and its Applications. Disc. Comput. Geom. 15, 1\u201313 (1996)","journal-title":"Disc. Comput. Geom."},{"key":"71_CR5","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M Sharir","year":"1994","unstructured":"Sharir, M.: Almost tight upper bounds for lower envelopes in higher dimensions. Disc. Comput. Geom. 12, 327\u2013345 (1994)","journal-title":"Disc. Comput. Geom."},{"unstructured":"Descartes, R.: Principia Philosophi\u01e3, Amsterdam (1644)","key":"71_CR6"},{"key":"71_CR7","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1515\/crll.1850.40.209","volume":"40","author":"P Dirichelt","year":"1850","unstructured":"Dirichelt, P.: \u00dcber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal F\u00fcr Die Reine Und Angewandte Mathematik, Berlin 40, 209\u2013227 (1850)","journal-title":"Journal F\u00fcr Die Reine Und Angewandte Mathematik, Berlin"},{"key":"71_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1515\/crll.1908.133.97","volume":"133","author":"G Voronoi","year":"1908","unstructured":"Voronoi, G.: Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiqes, Premier M\u00e9moire, Sur quelques propri\u00e9t\u00e9s des formes quadratiques positives parafites. Journal F\u00fcr die reine und angewandte, Mathematik, Berlin 133, 97\u2013102 (1908)","journal-title":"Journal F\u00fcr die reine und angewandte, Mathematik, Berlin"},{"key":"71_CR9","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1515\/crll.1908.134.198","volume":"134","author":"G Voronoi","year":"1908","unstructured":"Voronoi, G.: Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiqes, Deuxi\u00e8me M\u00e9moire, Recherches sur les parall\u00e9llo\u00e8dres primitifs. Journal F\u00fcr die reine und angewandte, Mathematik, Berlin 134, 198\u2013287 (1908)","journal-title":"Journal F\u00fcr die reine und angewandte, Mathematik, Berlin"},{"key":"71_CR10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1515\/crll.1909.136.67","volume":"136","author":"G Voronoi","year":"1909","unstructured":"Voronoi, G.: Nouvelles applications des param\u00e8tres continus \u00e0 th\u00e9orie des formes quadratiqes, Deuxi\u00e8me M\u00e9moire, Recherches sur les parall\u00e9llo\u00e8dres primitifs. Journal F\u00fcr die reine und angewandte, Mathematik, Berlin 136, 67\u2013182 (1909)","journal-title":"Journal F\u00fcr die reine und angewandte, Mathematik, Berlin"},{"issue":"2","key":"71_CR11","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1093\/comjnl\/24.2.167","volume":"24","author":"DF Watson","year":"1981","unstructured":"Watson, D.F.: Computing the n-dimensional delaunay tessellation with application to voronoi polytopes. Comput. J. 24(2), 167\u2013172 (1981)","journal-title":"Comput. J."},{"issue":"2","key":"71_CR12","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1093\/comjnl\/24.2.162","volume":"24","author":"A Bowyer","year":"1981","unstructured":"Bowyer, A.: Computing Dirichlet Tessellations. Comput. J. 24(2), 162\u2013166 (1981)","journal-title":"Comput. J."},{"issue":"7","key":"71_CR13","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1080\/00207160701466362","volume":"85","author":"I Boada","year":"2008","unstructured":"Boada, I., Coll, N., Madern, N., Sellar\u00e8s, J.: Approximations of 2D and 3D Generalized Voronoi Diagrams. International Journal of Computer Mathematics 85(7), 1003\u20131022 (2008)","journal-title":"International Journal of Computer Mathematics"},{"issue":"2","key":"71_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0925-7721(01)00003-7","volume":"18","author":"M Held","year":"2001","unstructured":"Held, M.: VRONI: an engineering approach to the reliable and efficient computation of voronoi diagrams of points and line segments. Comput. Geom. 18(2), 95\u2013123 (2001)","journal-title":"Comput. Geom."},{"key":"71_CR15","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.cad.2008.08.004","volume":"41","author":"M Held","year":"2009","unstructured":"Held, M., Huber, S.: Topology-oriented incremental computation of voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41, 327\u2013338 (2009)","journal-title":"Comput. Aided Des."},{"unstructured":"Gold, C., Remmele, P., and Roos, T.: Voronoi diagrams of line segments made easy. In: Canadian Conference on Computational Geometry (1995)","key":"71_CR16"},{"doi-asserted-by":"crossref","unstructured":"Hemmer, M., Setter, O., Halperin, D.: Constructing the exact voronoi diagram of arbitrary lines in three-dimensional space with fast point-location. In: 18th Annual European Symposium, pp. 6\u20138 (2010)","key":"71_CR17","DOI":"10.1007\/978-3-642-15775-2_34"},{"key":"71_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-319-14249-4_8","volume-title":"Advances in Visual Computing","author":"JW Holcomb","year":"2014","unstructured":"Holcomb, J.W., Cobb, J.A.: Voronoi diagrams of line segments in 3D, with application to automatic rigging. In: Bebis, G., Boyle, R., Parvin, B., Koracin, D., McMahan, R., Jerald, J., Zhang, H., Drucker, S.M., Kambhamettu, C., El Choubassi, M., Deng, Z., Carlson, M. (eds.) ISVC 2014, Part I. LNCS, vol. 8887, pp. 75\u201386. Springer, Heidelberg (2014)"},{"key":"71_CR19","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2001)"},{"unstructured":"Kepler, J.: Strena seu de Nive Sexangula, 1611","key":"71_CR20"},{"key":"71_CR21","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.4007\/annals.2005.162.1065","volume":"162","author":"T Hales","year":"2005","unstructured":"Hales, T.: A proof of the kepler conjecture. Ann. Math. 162, 1065\u20131185 (2005)","journal-title":"Ann. Math."}],"container-title":["Lecture Notes in Computer Science","Advances in Visual Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-27863-6_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,29]],"date-time":"2022-05-29T15:43:17Z","timestamp":1653838997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-27863-6_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319278629","9783319278636"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-27863-6_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}