{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:19:04Z","timestamp":1777616344058,"version":"3.51.4"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,4,28]],"date-time":"2009-04-28T00:00:00Z","timestamp":1240876800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,7]]},"DOI":"10.1007\/s00454-009-9173-3","type":"journal-article","created":{"date-parts":[[2009,4,27]],"date-time":"2009-04-27T15:23:00Z","timestamp":1240845780000},"page":"94-130","source":"Crossref","is-referenced-by-count":12,"title":["The Voronoi Diagram of Three Lines"],"prefix":"10.1007","volume":"42","author":[{"given":"Hazel","family":"Everett","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lazard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Lazard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohab","family":"Safey\u00a0El\u00a0Din","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,28]]},"reference":[{"key":"9173_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"K. Appel","year":"1977","unstructured":"Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. Parts\u00a0I and\u00a0II. Ill. J. Math. 21, 429\u2013567 (1977)","journal-title":"Ill. J. Math."},{"key":"9173_CR2","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: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, Chap.\u00a05, pp. 201\u2013290. Elsevier, Amsterdam (2000)"},{"key":"9173_CR3","doi-asserted-by":"crossref","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: Proceedings of the 21st ACM Annual Symposium on Computational Geometry (SoCG\u201905), pp. 99\u2013115 (2005)","DOI":"10.1145\/1064092.1064110"},{"key":"9173_CR4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0925-7721(01)00054-2","volume":"22","author":"J.-D. Boissonnat","year":"2002","unstructured":"Boissonnat, J.-D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations in CGAL. Comput. Geom. Theory Appl. 22, 5\u201319 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9173_CR5","series-title":"Mathematics and Visualization","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/978-3-540-33259-6_2","volume-title":"Effective Computational Geometry for Curves and Surfaces","author":"J.-D. Boissonnat","year":"2006","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. Mathematics and Visualization, pp.\u00a067\u2013116. Springer, Berlin (2006)"},{"issue":"2","key":"9173_CR6","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00454-005-1230-y","volume":"35","author":"C. Borcea","year":"2006","unstructured":"Borcea, C., Goaoc, X., Lazard, S., Petitjean, S.: Common tangents to spheres in \u211d3. Discrete Comput. Geom. 35(2), 287\u2013300 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"9173_CR7","doi-asserted-by":"crossref","unstructured":"Cheng, J., Lazard, S., Pe\u00f1aranda, L., Pouget, M., Rouillier, F., Tsigaridas, E.: On the topology of planar algebraic curves. In: Proceedings of the 25th ACM Annual Symposium on Computational Geometry (SoCG\u201909) (2009)","DOI":"10.1145\/1542362.1542424"},{"key":"9173_CR8","doi-asserted-by":"crossref","DOI":"10.1142\/2196","volume-title":"Machine Proofs in Geometry: Automated Production of Readable Proofs for Geometry Theorems","author":"S.-C. Chou","year":"1994","unstructured":"Chou, S.-C., Gao, X.-S., Zhang, J.-Z.: Machine Proofs in Geometry: Automated Production of Readable Proofs for Geometry Theorems. World Scientific, Singapore (1994)"},{"issue":"2","key":"9173_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jsco.2002.0547","volume":"34","author":"G.E. Collins","year":"2002","unstructured":"Collins, G.E., Johnson, J.R., Krandick, W.: Interval arithmetic in cylindrical algebraic decomposition. J. Symb. Comput. 34(2), 145\u2013157 (2002)","journal-title":"J. Symb. Comput."},{"key":"9173_CR10","series-title":"Graduate Texts in Mathematics","volume-title":"Using Algebraic Geometry","author":"D. Cox","year":"2005","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Using Algebraic Geometry, 2nd edn. Graduate Texts in Mathematics, vol.\u00a0185. Springer, New York (2005)","edition":"2"},{"key":"9173_CR11","unstructured":"Culver, T.: Computing the medial axis of a polyhedron reliably and efficiently. Ph.D. thesis, University of North Carolina at Chapel Hill (2000)"},{"key":"9173_CR12","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1145\/566282.566333","volume-title":"SMA \u201902: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications","author":"T.K. Dey","year":"2002","unstructured":"Dey, T.K., Zhao, W.: Approximate medial axis as a Voronoi subcomplex. In: SMA \u201902: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications, pp. 356\u2013366. ACM, New York (2002)"},{"issue":"3","key":"9173_CR13","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.jsc.2007.10.006","volume":"43","author":"L. Dupont","year":"2008","unstructured":"Dupont, L., Lazard, D., Lazard, S., Petitjean, S.: Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm. J. Symb. Comput. 43(3), 168\u2013191 (2008)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"9173_CR14","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jsc.2007.10.012","volume":"43","author":"L. Dupont","year":"2008","unstructured":"Dupont, L., Lazard, D., Lazard, S., Petitjean, S.: Near-optimal parameterization of the intersection of quadrics: II. A classification of pencils. J. Symb. Comput. 43(3), 192\u2013215 (2008)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"9173_CR15","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.jsc.2007.10.007","volume":"43","author":"L. Dupont","year":"2008","unstructured":"Dupont, L., Lazard, D., Lazard, S., Petitjean, S.: Near-optimal parameterization of the intersection of quadrics: III. Parameterizing singular intersections. J. Symb. Comput. 43(3), 216\u2013232 (2008)","journal-title":"J. Symb. Comput."},{"issue":"6","key":"9173_CR16","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1142\/S0218195908002763","volume":"18","author":"I. Emiris","year":"2008","unstructured":"Emiris, I., Tsigaridas, E., Tzoumas, G.: Predicates for the exact Voronoi diagram of ellipses under the Euclidean metric. Int. J. Comput. Geom. Appl. 18(6), 567\u2013597 (2008) (Special Issue on SoCG\u201906)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9173_CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0925-7721(01)00056-6","volume":"21","author":"M. Etzion","year":"2002","unstructured":"Etzion, M., Rappoport, A.: Computing Voronoi skeletons of a 3-d polyhedron by space subdivision. Comput. Geom. Theory Appl. 21(3), 87\u2013120 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9173_CR18","doi-asserted-by":"crossref","unstructured":"Everett, H., Lazard, D., Lazard, S., Safey El Din, M.: The Voronoi diagram of three lines in \u211d3. In: Proceedings of the 23rd ACM Annual Symposium on Computational Geometry (SoCG\u201907), S. Korea, pp. 255\u2013264 (2007)","DOI":"10.1145\/1247069.1247116"},{"key":"9173_CR19","unstructured":"Faug\u00e8re, J.-C.: FGb\u2014A software for computing Gr\u00f6bner bases. http:\/\/fgbrs.lip6.fr"},{"key":"9173_CR20","first-page":"377","volume-title":"Handbook of Discrete and Computational Geometry","author":"S. Fortune","year":"1997","unstructured":"Fortune, S.: Voronoi diagrams and Delaunay triangulations. In: Handbook of Discrete and Computational Geometry, pp. 377\u2013388. CRC, Boca Raton (1997)"},{"key":"9173_CR21","first-page":"277","volume":"33","author":"K. Hoff","year":"1999","unstructured":"Hoff, K., Culver, T., Keyser, J., Lin, M., Manocha, D.: Fast computation of generalized Voronoi diagrams using graphics hardware. Comput. Graph. 33, 277\u2013286 (1999) (Proceedings of ACM SIGGRAPH 1999, Annual Conference Series)","journal-title":"Comput. Graph."},{"key":"9173_CR22","unstructured":"Karavelas, M.I.: A robust and efficient implementation for the segment Voronoi diagram. In: International Symposium on Voronoi Diagrams in Science and Engineering, pp. 51\u201362 (2004)"},{"issue":"9","key":"9173_CR23","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1016\/S0167-8396(99)00032-1","volume":"16","author":"J. Keyser","year":"1999","unstructured":"Keyser, J., Krishnan, S., Manocha, D.: Efficient and accurate B-Rep generation of low degree sculptured solids using exact arithmetic: I\u00a0Representations, II\u00a0Computation. Comput. Aided Geom. Des. 16(9), 841\u2013859, 861\u2013882 (1999)","journal-title":"Comput. Aided Geom. Des."},{"issue":"3","key":"9173_CR24","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1137\/S0097539702408387","volume":"32","author":"V. Koltun","year":"2003","unstructured":"Koltun, V., Sharir, M.: Three dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations. SIAM J. Comput. 32(3), 616\u2013642 (2003)","journal-title":"SIAM J. Comput."},{"key":"9173_CR25","doi-asserted-by":"crossref","first-page":"67","DOI":"10.4310\/jdg\/1090347525","volume":"56","author":"K. Kurdyka","year":"2000","unstructured":"Kurdyka, K., Orro, P., Simon, S.: Semialgebraic Sard theorem for generalized critical values. J. Differ. Geom. 56, 67\u201392 (2000)","journal-title":"J. Differ. Geom."},{"key":"9173_CR26","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"S.M. LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006) (Also available at http:\/\/planning.cs.uiuc.edu\/ )"},{"issue":"11\u201312","key":"9173_CR27","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1002\/(SICI)1097-0312(199811\/12)51:11\/12<1387::AID-CPA6>3.0.CO;2-0","volume":"51","author":"P. Lax","year":"1998","unstructured":"Lax, P.: On the discriminant of real symmetric matrices. Commun. Pure Appl. Math. 51(11\u201312), 1387\u20131396 (1998)","journal-title":"Commun. Pure Appl. Math."},{"key":"9173_CR28","series-title":"Solid Mechanics and Its Applications","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/978-94-015-8192-9_16","volume-title":"Computational Kinematics","author":"D. Lazard","year":"1993","unstructured":"Lazard, D.: On the representation of rigid-body motions and its application to generalized platform manipulators. In: Angeles, J., Hommel, G., Kov\u00e0cs, P. (eds.) Computational Kinematics. Solid Mechanics and Its Applications, vol. 28, pp. 175\u2013182. Kluwer, Dordrecht (1993)"},{"key":"9173_CR29","series-title":"Lecture Notes Series in Computing","first-page":"66","volume-title":"5th Asian Symposium on Computers Mathematics\u2014ASCM 2001","author":"D. Lazard","year":"2001","unstructured":"Lazard, D.: On the specification for solvers of polynomial systems. In: 5th Asian Symposium on Computers Mathematics\u2014ASCM 2001. Lecture Notes Series in Computing, vol. 9, pp. 66\u201375. World Scientific, Singapore (2001)"},{"issue":"10","key":"9173_CR30","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/360349.360355","volume":"19","author":"J. Levin","year":"1976","unstructured":"Levin, J.: A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces. Commun. ACM 19(10), 555\u2013563 (1976)","journal-title":"Commun. ACM"},{"key":"9173_CR31","unstructured":"Maple System: Waterloo Maple Software. http:\/\/www.maplesoft.com"},{"key":"9173_CR32","unstructured":"Milenkovic, V.J.: Robust construction of the Voronoi diagram of a polyhedron. In: Proceedings of the 5th Canadian Conference on Computational Geometry (CCCG\u201993), pp. 473\u2013478 (1993)"},{"issue":"2","key":"9173_CR33","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.comgeo.2004.05.003","volume":"30","author":"B. Mourrain","year":"2005","unstructured":"Mourrain, B., T\u00e9court, J.-P., Teillaud, M.: On the computation of an arrangement of quadrics in 3D. Comput. Geom. Theory Appl. 30(2), 145\u2013164 (2005) (Special issue, 19th European Workshop on Computational Geometry)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"9173_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W. Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 1\u201329 (2008)","journal-title":"J. ACM"},{"key":"9173_CR35","doi-asserted-by":"crossref","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations\u2014Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"2000","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations\u2014Concepts and Applications of Voronoi Diagrams, 2nd edn. Wiley, New York (2000)","edition":"2"},{"key":"9173_CR36","unstructured":"Parillo, P., Papachristodoulou, A., Prajna, S., Seiler, P.: SOSTOOLS\u2014A MATLAB toolbox for sums of squares optimization programs. http:\/\/www.cds.caltech.edu\/sostools\/"},{"key":"9173_CR37","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"Robertson, N., Sanders, D.P., Seymour, P.D., Thomas, R.: The four colour theorem. J. Comb. Theory Ser. B 70, 2\u201344 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9173_CR38","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1006\/jcom.2000.0563","volume":"16","author":"F. Rouillier","year":"2000","unstructured":"Rouillier, F., Roy, M.-F., Safey El Din, M.: Finding at least one point in each connected component of a real algebraic set defined by a single equation. J. Complex. 16, 716\u2013750 (2000)","journal-title":"J. Complex."},{"issue":"1","key":"9173_CR39","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s11786-007-0003-9","volume":"1","author":"M. Safey El Din","year":"2007","unstructured":"Safey El Din, M.: Testing sign conditions on a multivariate polynomial and applications. Math. Comput. Sci. 1(1), 177\u2013207 (2007)","journal-title":"Math. Comput. Sci."},{"key":"9173_CR40","unstructured":"Safey\u00a0El\u00a0Din, M.: RAG\u2019Lib\u2014A library for real algebraic geometry. http:\/\/www-calfor.lip6.fr\/~safey\/RAGLib\/"},{"key":"9173_CR41","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/860854.860901","volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201903)","author":"M. Safey El Din","year":"2003","unstructured":"Safey El Din, M., Schost, E.: Polar varieties and computation of at least one point in each connected component of a smooth real algebraic set. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC\u201903), pp. 224\u2013231. ACM, Philadelphia (2003)"},{"issue":"3","key":"9173_CR42","first-page":"417","volume":"32","author":"M. Safey El Din","year":"2004","unstructured":"Safey El Din, M., Schost, E.: Properness defects of projections and computation of one point in each connected component of a real algebraic set. Discrete Comput. Geom. 32(3), 417\u2013430 (2004)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"9173_CR43","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.comgeo.2004.02.007","volume":"33","author":"E. Sch\u00f6mer","year":"2006","unstructured":"Sch\u00f6mer, E., Wolpert, N.: An exact and efficient approach for computing a cell in an arrangement of quadrics. Comput. Geom. Theory Appl. 33(1\u20132), 65\u201397 (2006) (Special Issue on Robust Geometric Algorithms and Their Implementations)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9173_CR44","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1002\/cpa.3160370605","volume":"37","author":"J.T. Schwartz","year":"1984","unstructured":"Schwartz, J.T., Sharir, M.: On the \u201cpiano movers\u201d problem: V. The case of a rod moving in three-dimensional space amidst polyhedral obstacles. Commun. Pure Appl. Math. 37, 815\u2013848 (1984)","journal-title":"Commun. Pure Appl. Math."},{"key":"9173_CR45","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/PL00009319","volume":"18","author":"O. Schwarzkopf","year":"1997","unstructured":"Schwarzkopf, O., Sharir, M.: Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications. Discrete Comput. Geom. 18, 269\u2013288 (1997)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9173_CR46","first-page":"3","volume":"36","author":"C. Segre","year":"1883","unstructured":"Segre, C.: Studio sulle quadriche in uno spazio lineare ad un numero qualunque di dimensioni. Mem. della R. Acc. delle Scienze di Torino 36(2), 3\u201386 (1883)","journal-title":"Mem. della R. Acc. delle Scienze di Torino"},{"key":"9173_CR47","doi-asserted-by":"crossref","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. Discrete Comput. Geom. 12, 327\u2013345 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9173_CR48","unstructured":"Teichmann, M., Teller, S.: Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions. Technical report 766, Laboratory of Computer Science, MIT (1997)"},{"issue":"4","key":"9173_CR49","first-page":"1027","volume":"1","author":"J. Viro (Drobotukhina)","year":"1990","unstructured":"Viro (Drobotukhina), J., Viro, O.: Configurations of skew lines. Leningrad Math. J. 1(4), 1027\u20131050 (1990) (Revised version in English: arXiv:math\/0611374 )","journal-title":"Leningrad Math. J."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9173-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9173-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9173-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T16:00:19Z","timestamp":1633363219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9173-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,28]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9173"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9173-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,28]]}}}