{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:17:21Z","timestamp":1774685841237,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642157745","type":"print"},{"value":"9783642157752","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_34","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T10:47:32Z","timestamp":1283338052000},"page":"398-409","source":"Crossref","is-referenced-by-count":9,"title":["Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space"],"prefix":"10.1007","author":[{"given":"Michael","family":"Hemmer","sequence":"first","affiliation":[]},{"given":"Ophir","family":"Setter","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"34_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02716576","volume":"15","author":"P.K. Agarwal","year":"1996","unstructured":"Agarwal, P.K., Schwarzkopf, O., Sharir, M.: The overlay of lower envelopes and its applications. Disc. Comput. Geom.\u00a015(1), 1\u201313 (1996)","journal-title":"Disc. Comput. Geom."},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J., Urrutia, G. (eds.) Handb. Comput. Geom., ch.\u00a05, pp. 201\u2013290. Elsevier, Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"34_CR3","volume-title":"Generic Programming and the STL","author":"M.H. Austern","year":"1999","unstructured":"Austern, M.H.: Generic Programming and the STL. Addison-Wesley, Reading (1999)"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Berberich, E., Hemmer, M., Kerber, M.: A generic algebraic kernel for non-linear geometric applications. Research Report 7274, INRIA (2010)","DOI":"10.1145\/1998196.1998224"},{"key":"34_CR5","first-page":"99","volume-title":"Proc. 21st Annu. ACM Symp. Comput. Geom.","author":"E. Berberich","year":"2005","unstructured":"Berberich, E., Hemmer, M., Kettner, L., Sch\u00f6mer, E., Wolpert, N.: An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. In: Mitchell, J., Rote, G., Kettner, L. (eds.) Proc. 21st Annu. ACM Symp. Comput. Geom., pp. 99\u2013106. ACM Press, Pisa (2005)"},{"key":"34_CR6","volume-title":"Models for the Perception of Speech and Visual Form","author":"H. Blum","year":"1967","unstructured":"Blum, H.: A transformation for extracting new descriptors of shape. In: WathenDunn, W. (ed.) Models for the Perception of Speech and Visual Form. MIT Press, Cambridge (1967)"},{"key":"34_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/11561071_34","volume-title":"Algorithms \u2013 ESA 2005","author":"J.D. Boissonnat","year":"2005","unstructured":"Boissonnat, J.D., Delage, C.: Convex hull and Voronoi diagram of additively weighted points. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 367\u2013378. Springer, Heidelberg (2005)"},{"key":"34_CR8","series-title":"Mathematics and Visualization","volume-title":"Effective Computational Geometry for Curves and Surfaces","year":"2006","unstructured":"Boissonnat, J.D., Teillaud, M. (eds.): Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization. Springer, Heidelberg (2006)"},{"issue":"1","key":"34_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cagd.2003.07.008","volume":"21","author":"T. Culver","year":"2004","unstructured":"Culver, T., Keyser, J., Manocha, D.: Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design\u00a021(1), 65\u201398 (2004)","journal-title":"Computer Aided Geometric Design"},{"key":"34_CR10","first-page":"106","volume-title":"Proc. 14th Annu. ACM Symp. Comput. Geom.","author":"O. Devillers","year":"1998","unstructured":"Devillers, O.: Improved incremental randomized Delaunay triangulation. In: Proc. 14th Annu. ACM Symp. Comput. Geom., pp. 106\u2013115. ACM Press, New York (1998)"},{"issue":"2","key":"34_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.comgeo.2004.02.002","volume":"29","author":"L. Devroye","year":"2004","unstructured":"Devroye, L., Lemaire, C., Moreau, J.M.: Expected time analysis for Delaunay point location. Computational Geometry\u00a029(2), 61\u201389 (2004)","journal-title":"Computational Geometry"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-540-75520-3_56","volume-title":"Algorithms \u2013 ESA 2007","author":"L. Dupont","year":"2007","unstructured":"Dupont, L., Hemmer, M., Petitjean, S., Sch\u00f6mer, E.: Complete, exact and efficient implementation for computing the adjacency graph of an arrangement of quadrics. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 633\u2013644. Springer, Heidelberg (2007)"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Disc. Comput. Geom.\u00a01, 25\u201344 (1986)","journal-title":"Disc. Comput. Geom."},{"key":"34_CR14","first-page":"227","volume-title":"Proc. 22nd Annu. ACM Symp. Comput. Geom.","author":"I.Z. Emiris","year":"2006","unstructured":"Emiris, I.Z., Tsigaridas, E.P., Tzoumas, G.M.: The predicates for the Voronoi diagram of ellipses. In: Proc. 22nd Annu. ACM Symp. Comput. Geom., pp. 227\u2013236. ACM Press, New York (2006)"},{"issue":"1-2","key":"34_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.comgeo.2004.02.006","volume":"33","author":"I.Z. Emiris","year":"2006","unstructured":"Emiris, I.Z., Karavelas, M.I.: The predicates of the Apollonius diagram: Algorithmic analysis and implementation. Comput. Geom. Theory Appl.\u00a033(1-2), 18\u201357 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Everett, H., Gillot, C., Lazard, D., Lazard, S., Pouget, M.: The Voronoi diagram of three arbitrary lines in ${\\mathbb R}^3$ . In: Abstracts of 25th Eur. Workshop Comput. Geom. (2009)","DOI":"10.1007\/s00454-009-9173-3"},{"key":"34_CR17","first-page":"255","volume-title":"Proc. 23rd Annu. ACM Symp. Comput. Geom.","author":"H. Everett","year":"2007","unstructured":"Everett, H., Lazard, S., Lazard, D., Din, M.S.E.: The Voronoi diagram of three lines. In: Proc. 23rd Annu. ACM Symp. Comput. Geom., pp. 255\u2013264. ACM Press, New York (2007)"},{"key":"34_CR18","volume-title":"Modern Computer Algebra","author":"J. zur Gathen von","year":"1999","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)"},{"key":"34_CR19","unstructured":"Halperin, D., Kavraki, L.E., Latombe, J.C.: Robotics. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handb. Disc. Comput. Geom., 2nd edn., ch.\u00a048, pp. 1065\u20131093. Chapman & Hall\/CRC, Boca Raton (2004)"},{"issue":"6","key":"34_CR20","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/j.cagd.2008.09.010","volume":"26","author":"I. Hanniel","year":"2009","unstructured":"Hanniel, I., Elber, G.: Computing the Voronoi cells of planes, spheres and cylinders in ${\\mathbb R}^3$ . Comput. Aided Geom. Des.\u00a026(6), 695\u2013710 (2009)","journal-title":"Comput. Aided Geom. Des."},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Haran, I., Halperin, D.: An experimental study of point location in planar arrangements in CGAL. ACM Journal of Experimental Algorithmics\u00a013 (2008)","DOI":"10.1145\/1412228.1412237"},{"key":"34_CR22","unstructured":"Frey, P.J.: : MEDIT : An interactive Mesh visualization Software. Technical Report RT-0253, INRIA (December 2001)"},{"key":"34_CR23","unstructured":"Karavelas, M.I.: A robust and effient implementation for the segment Voronoi diagram. In: Int. Symp. on Voronoi Diagrams in Sci. and Engineering, pp. 51\u201362 (2004)"},{"key":"34_CR24","first-page":"586","volume-title":"Proc. 10th Annu. Eur. Symp. Alg.","author":"M.I. Karavelas","year":"2002","unstructured":"Karavelas, M.I., Yvinec, M.: Dynamic additively weighted Voronoi diagrams in 2D. In: Proc. 10th Annu. Eur. Symp. Alg., pp. 586\u2013598. Springer, London (2002)"},{"key":"34_CR25","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-85126-4_3","volume-title":"Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence","author":"D.S. Kim","year":"2008","unstructured":"Kim, D.S., Seo, J., Kim, D., Cho, Y., Ryu, J.: The beta-shape and beta-complex for analysis of molecular structures. In: Gavrilova, M.L. (ed.) Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence. Studies in Computational Intelligence, vol.\u00a0158, pp. 47\u201366. Springer, Heidelberg (2008)"},{"issue":"3","key":"34_CR26","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1137\/S0097539702408387","volume":"32","author":"V. Koltun","year":"2003","unstructured":"Koltun, V., Sharir, M.: 3-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations. SIAM J. on Computing\u00a032(3), 616\u2013642 (2003)","journal-title":"SIAM J. on Computing"},{"key":"34_CR27","unstructured":"Milenkovic, V.: Robust construction of the Voronoi diagram of a polyhedron. In: Proc. 5th Canad. Conf. Comput. Geom., pp. 473\u2013478 (1993)"},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Mulmuley, K.: A fast planar partition algorithm, I. In: Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pp. 580\u2013589 (1988)","DOI":"10.1109\/SFCS.1988.21974"},{"key":"34_CR29","unstructured":"Myers, N.: Traits: A new and useful template technique. C++ Gems\u00a017 (1995)"},{"key":"34_CR30","unstructured":"Rineau, L., Yvinec, M.: 3D surface mesh generation. In: CGAL Editorial Board CGAL User and Reference Manual (ed.), 3.5 edn. (2009)"},{"key":"34_CR31","doi-asserted-by":"crossref","unstructured":"Setter, O., Sharir, M., Halperin, D.: Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space. Transactions on Computational Sciences (to appear, 2010)","DOI":"10.1007\/978-3-642-16007-3_1"},{"issue":"1","key":"34_CR32","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.\u00a012(1), 327\u2013345 (1994)","journal-title":"Disc. Comput. Geom."},{"key":"34_CR33","unstructured":"The CGAL Project: CGAL User and Reference Manual. CGAL Editorial Board, 3.6 edn. (2010), http:\/\/www.cgal.org\/"},{"key":"34_CR34","doi-asserted-by":"crossref","unstructured":"Wein, R., van den Berg, J.P., Halperin, D.: The visibility-Voronoi complex and its applications. Computational Geometry: Theory and Applications\u00a036(1), 66\u201387 (2007); special Issue on the 21st European Workshop on Computational Geometry - EWCG 2005","DOI":"10.1016\/j.comgeo.2005.11.007"},{"key":"34_CR35","first-page":"260","volume-title":"Proc. 24th Annu. ACM Symp. Comput. Geom.","author":"E. Yaffe","year":"2008","unstructured":"Yaffe, E., Halperin, D.: Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space. In: Proc. 24th Annu. ACM Symp. Comput. Geom., pp. 260\u2013269. ACM Press, New York (2008)"},{"key":"34_CR36","doi-asserted-by":"crossref","unstructured":"Yap, C.K., Dub\u00e9, T.: The exact computation paradigm. In: Du, D.Z., Hwang, F.K. (eds.) Computing in Euclidean Geometry, 2nd edn. LNCS, vol.\u00a01, pp. 452\u2013492. World Scientific, Singapore (1995)","DOI":"10.1142\/9789812831699_0011"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,7]],"date-time":"2021-11-07T16:30:10Z","timestamp":1636302610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}