CGAL User and Reference Manual

[AA95] O. Aichholzer and F. Aurenhammer. Straight skeletons for general polygonal figures. Technical Report 432, Inst. for Theor. Comput. Sci., Graz Univ. of Technology, Graz, Austria, 1995.

[AAAG95] O. Aichholzer, D. Alberts, F. Aurenhammer, and B. Gärtner. A novel type of skeleton for polygons. J. Universal Comput. Sci., 1(12):752-761, 1995.

[AAD07] Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. In Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pages 1106-1113, 2007.

[AB99] Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481-504, 1999.

[AB03] Dominique Attali and Jean-Daniel Boissonnat. Complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete and Computational Geometry, 30(3):437-452, 2003.

[Abb] J. Abbott. Quadratic interval refinement for real roots. Poster presented at the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006).

[ABL03] Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier. Complexity of the Delaunay triangulation of points on surfaces: The smooth case. In Proc. 19th Annual Symposium on Computational Geometry, pages 237-246, 2003.

[ACR03] Nina Amenta, Sunghee Choi, and Günter Rote. Incremental constructions con BRIO. In Proc. 19th Annu. Sympos. Comput. Geom., pages 211-219, 2003.

[ACSYD05] Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. Variational tetrahedral meshing. ACM Transactions on Graphics, 24:617-625, 2005. SIGGRAPH '2005 Conference Proceedings.

[AFH02] P. K. Agarwal, E. Flato, and D. Halperin. Polygon decomposition for efficient construction of Minkowski sums. Computational Geometry: Theory and Applications, 21:39-61, 2002.

[AKM+87] A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 1987.

[Ale01] Andrei Alexandrescu. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, 2001.

[AM93a] S. Arya and D. M. Mount. Algorithms for fast vector quantization. In Data Compression Conference, pages 381-390. IEEE Press, 1993.

[AM93b] S. Arya and D. M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 271-280, 1993.

[And78] K. R. Anderson. A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 7(1):53-55, 1978.

[And79] A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inform. Process. Lett., 9(5):216-219, 1979.

[AS00] Pankaj K. Agarwal and Micha Sharir. Arrangements and their applications. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 49-119. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[AT78] S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Inform. Process. Lett., 7(5):219-222, 1978.

[Aus98] Matthew H. Austern. Generic Programming and the STL. Addison-Wesley, 1998.

[Bau75] B. G. Baumgart. A polyhedron representation for computer vision. In Proc. AFIPS Natl. Comput. Conf., volume 44, pages 589-596. AFIPS Press, Alrington, Va., 1975.

[BB97] F. Bernardini and C. Bajaj. Sampling and reconstructing manifolds using alpha-shapes. Technical Report CSD-TR-97-013, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN, 1997.

[BBP01] H. Brönnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics, 109:25-47, 2001.

[BDH96] C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. The Quickhull algorithm for convex hulls. ACM Trans. Math. Softw., 22(4):469-483, December 1996.

[BDP+02] Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. Comput. Geom. Theory Appl., 22:5-19, 2002.

[BDTY00] Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 11-18, 2000.

[BEH+02] Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Kurt Mehlhorn, and Elmar Schömer. A computational basis for conic arcs and boolean operations on conic polygons. In Rolf Möhring and Rajeev Raman, editors, Algorithms - ESA 2002: 10th Annual European Symposium, volume 2461 of Lecture Notes in Computer Science, pages 174-186, Rome, Italy, September 2002. Springer.

[BEH+05] Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Joachim Reichel, Susanne Schmitt, Elmar Schömer, and Nicola Wolpert. Exacus: Efficient and exact algorithms for curves and surfaces. In Gerth S. Brodal and Stefano Leonardi, editors, 13th Annual European Symposium on Algorithms (ESA 2005), volume 3669 of Lecture Notes in Computer Science, pages 155-166, Palma de Mallorca, Spain, October 2005. European Association for Theoretical Computer Science (EATCS), Springer.

[Ben75] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, September 1975.

[BEPP99] Hervé Brönnimann, Ioannis Emiris, Victor Pan, and Sylvain Pion. Sign determination in Residue Number Systems. Theoret. Comput. Sci., 210(1):173-197, 1999. Special Issue on Real Numbers and Computers.

[BF02] Jean-Daniel Boissonnat and Julia Flötotto. A local coordinate system on a surface. In Proc. 7th ACM Symposium on Solid Modeling and Applications, 2002.

[BFH95] Heinzgerd Bendels, Dieter W. Fellner, and Sven Havemann. Modellierung der grundlagen: Erweiterbare datenstrukturen zur modellierung und visualisierung polygonaler welten. In D. W. Fellner, editor, Modeling - Virtual Worlds - Distributed Graphics, pages 149-157, Bad Honnef / Bonn, 27.-28. November 1995.

[BG89] D. Bertsimas and M. Grigni. On the space-filling curve heuristic for the euclidean traveling salesman problem. Operations Research Letters, 8:241-244, 1989.

[BGH97] Julien Basch, Leonidas Guibas, and John Hershberger. Data structures for mobile data. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 747-756, 1997.

[BHKT07] Eric Berberich, Michael Hemmer, Menelaos I. Karavelas, and Monique Teillaud. Revision of the interface specification of algebraic kernel. Technical Report ACS-TR-243301-01, INRIA Sophia-Antipolis, Max Planck Institut für Informatik, National University of Athens, 2007.

[BMS94] C. Burnikel, K. Mehlhorn, and S. Schirra. On degeneracy in geometric computations. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 16-23, 1994.

[BO05] Jean-Daniel Boissonnat and Steve Oudot. Provably good sampling and meshing of surfaces. Graphical Models, 67:405-451, 2005.

[BPP95] Gavin Bell, Anthony Parisi, and Mark Pesce. Vrml the virtual reality modeling language: Version 1.0 specification., May 26 1995. Third Draft.

[Bro97] J. L. Brown. Systems of coordinates associated with points scattered in the plane. Comput. Aided Design, 14:547-559, 1997.

[Bur96] C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. Ph.D thesis, Universität des Saarlandes, March 1996.

[But71] Arthur Butz. Alternative algorithm for Hilbert's space-filling curve. IEEE Transactions on computers, pages 424-425, 1971.

[BY98] Jean-Daniel Boissonnat and Mariette Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.

[BYB09a] Dobrina Boltcheva, Mariette Yvinec, and Jean-Daniel Boissonnat. Feature preserving delaunay mesh generation from 3d multi- material images. Computer Graphics Forum, 28:1455-14645, 2009. special issue for EUROGRAPHICS Symposium on Geometry Processing.

[BYB09b] Dobrina Boltcheva, Mariette Yvinec, and Jean-Daniel Boissonnat. Mesh generation from 3d multi-material images. In Medical Image Computing and Computer-Assisted Intervention, volume 5762 of Lecture Notes in Computer Science, pages 283-290, 2009.

[Byk78] A. Bykat. Convex hull of a finite set of points in two dimensions. Inform. Process. Lett., 7:296-298, 1978.

[C++98] International standard ISO/IEC 14882: Programming languages - C++. American National Standards Institute, 11 West 42nd Street, New York 10036, 1998.

[CC78] E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10:350-355, 1978.

[CD85] Bernard Chazelle and D. P. Dobkin. Optimal convex decompositions. In G. T. Toussaint, editor, Computational Geometry, pages 63-133. North-Holland, Amsterdam, Netherlands, 1985.

[CDE+00] Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. Sliver exudation. J. ACM, 47(5):883-904, 2000.

[CDL07] S.-W. Cheng, T. K. Dey, and J. A. Levine. A practical delaunay meshing algorithm for a large class of domains. In Meshing Roundtable, pages 477-494, 2007.

[CDR07] Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos. Delaunay refinement for piecewise smooth complexes. In SODA, pages 1096-1105, Philadelphia, PA, USA, 2007.

[Cha84] Bernard Chazelle. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput., 13:488-507, 1984.

[Che93] L. P. Chew. Guaranteed-quality mesh generation for curved surfaces. In Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 274-280, 1993.

[Che04] L. Chen. Mesh Smoothing Schemes based on Optimal Delaunay Triangulations. In Proceedings of 13th International Meshing Roundtable, pages 109-120, 2004.

[Che09] Otfried Cheong. IPE manual and library documentation, 6.0pre32 edition, 2009.

[CLRS01] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, 2nd edition, 2001.

[CMS93] K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3(4):185-212, 1993.

[CP05a] F. Cazals and M. Pouget. Estimating differential quantities using polynomial fitting of osculating jets. Computer Aided Geometric Design, 22(2), 2005. Conference version: Symp. on Geometry Processing 2003.

[CP05b] F. Cazals and M. Pouget. Smooth surfaces, umbilics, lines of curvatures, foliations, ridges and the medial axis: selected topics. Int. J. of Computational Geometry and Applications, 15(5):511-536, 2005.

[CP05c] F. Cazals and M. Pouget. Topology driven algorithms for ridge extraction on meshes. Technical Report RR-5526, INRIA, 2005.

[CT09] Manuel Caroli and Monique Teillaud. Computing 3D periodic triangulations. In Proceedings 17th European Symposium on Algorithms, volume 5757 of Lecture Notes in Computer Science, pages 37-48, 2009. Full version available as INRIA Research Report 6823

[Dam10] G. Damiand. Contributions aux Cartes Combinatoires et Cartes Généralisées : Simplification, Modèles, Invariants Topologiques et Applications. Habilitation à diriger des recherches, Université Lyon 1, Septembre 2010.

[dBvKOS97] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.

[dBvKOS00] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.

[dC76] M. de Carmo. Differential Geometry of Curves and Surfaces. Prentice Hall, Englewood Cliffs, NJ, 1976.

[dCCLT09] Pedro M.M. de Castro, Frederic Cazals, Sebastien Loriot, and Monique Teillaud. Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphere. Computational Geometry : Theory and Applications, 42(6-7):536 - 550, 2009.

[DEGN99] Tamal Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry Nekhayev. Topology preserving edge contraction. geometric combinatorics. Publ. Inst. Math. (Beograd) (N.S.), 66:23-45, 1999.

[Dev98] Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998.

[Dev02] Olivier Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163-180, 2002.

[Dev09] Olivier Devillers. Vertex removal in two dimensional Delaunay triangulation: Asymptotic complexity is pointless. Research Report 7104, INRIA, 2009.

[DFG99] Q. Du, V. Faber, and M. Gunzburger. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM review, 41(4):637-676, 1999.

[DFMT00] Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 139-147, 2000.

[DFMT02] Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Comput. Geom. Theory Appl., 22:119-142, 2002.

[DLPT98] Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. Theory Appl., 11:187-208, 1998.

[DMA02] Mathieu Desbrun, Mark Meyer, and Pierre Alliez. Intrinsic parameterizations of surface meshes. Computer Graphics Forum, 21(3):209-218, September 2002.

[DP03] Olivier Devillers and Sylvain Pion. Efficient exact geometric predicates for Delaunay triangulations. In Proc. 5th Workshop Algorithm Eng. Exper., pages 37-44, 2003.

[DPT02] Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181-199, 2002.

[DT03] Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in a 3D Delaunay triangulation. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 313-319, 2003.

[DT06] Olivier Devillers and Monique Teillaud. Perturbations and vertex removal in Delaunay and regular 3D triangulations. Research Report 5968, INRIA, 2006.

[DW02] Q. Du and D. Wang. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. International Journal for Numerical Methods in Engineering, 56:1355-1373, 2002.

[Dwy89] R. A. Dwyer. Higher-dimensional Voronoi diagrams in linear expected time. In Proc. 5th Annu. ACM Sympos. Comput. Geom., pages 326-333, 1989.

[Edd77] W. F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw., 3:398-403 and 411-412, 1977.

[EDD+95] Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle. Multiresolution analysis of arbitrary meshes. In Computer Graphics (Proc. SIGGRAPH '95), volume 29, pages 173-182, 1995. Examples in

[Ede92] H. Edelsbrunner. Weighted alpha shapes. Technical Report UIUCDCS-R-92-1760, Dept. Comput. Sci., Univ. Illinois, Urbana, IL, 1992.

[Ede99] H. Edelsbrunner. Deformable smooth surface design. Discrete Comput. Geom., 21:87-115, 1999.

[EE98] David Eppstein and Jeff Erickson. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. In Symposium on Computational Geometry, pages 58-67, 1998.

[Eig08] Arno Eigenwillig. Real Root Isolation for Exactand Approximate Polynomials Using Descartes ' Rule of Signs. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany, 2008.

[EK99] G. Elber and M.-S. Kim, editors. Computer Aided Design, volume 31, 1999. Special Issue on Offsets, Sweeps and Minkowski Sums.

[EK08] Arno Eigenwillig and Michael Kerber. Exact and efficient 2d-arrangements of arbitrary algebraic curves. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA08), 2008. 122-131.

[EKP+04] Ioannis Z. Emiris, Athanasios Kakargias, Sylvain Pion, Monique Teillaud, and Elias P. Tsigaridas. Towards an open curved kernel. In Proc. 20th Annu. ACM Sympos. Comput. Geom., pages 438-446, 2004.

[EKW07] Arno Eigenwillig, Michael Kerber, and Nicola Wolpert. Fast and exact geometric analysis of real algebraic plane curves. In Christopher W. Brown, editor, Proocedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pages 151-158, 2007.

[EM94] H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes. ACM Trans. Graph., 13(1):43-72, January 1994.

[Eri02] Jeff Erickson. Dense point sets have sparse Delaunay triangulations. In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 125-134, 2002.

[ES96] H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15:223-241, 1996.

[Far90] G. Farin. Surfaces over Dirichlet tesselations. Comput. Aided Geom. Design, 7:281-292, 1990.

[FBF77] J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209-226, 1977.

[FH00] Eyal Flato and Dan Halperin. Robust and efficient construction of planar Minkowski sums. In Abstracts 16th European Workshop Comput. Geom., pages 85-88. Ben-Gurion University of the Negev, 2000.

[FH05] M. S. Floater and K. Hormann. Surface parameterization: a tutorial and survey. In N. A. Dodgson, M. S. Floater, and M. A. Sabin, editors, Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pages 157-186. Springer, Berlin, Heidelberg, 2005.

[FJ83] G. N. Frederickson and D. B. Johnson. Finding kth paths and p-centers by generating and searching good data structures. J. Algorithms, 4:61-80, 1983.

[FJ84] G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: sorted matrices. SIAM J. Comput., 13:14-30, 1984.

[Flo03a] Michael Floater. Mean value coordinates. Computer Aided Design, 20(1):19-27, 2003.

[Flö03b] Julia Flötotto. A coordinate system associated to a point cloud issued from a manifold: definition, properties and applications. Thèse de doctorat en sciences, Université de Nice-Sophia Antipolis, France, 2003.

[FO98] Petr Felkel and Stěpán Obdržálek. Straight skeleton implementation. In László Szirmay Kalos, editor, 14th Spring Conference on Computer Graphics (SCCG'98), pages 210-218, 1998.

[Gär99] B. Gärtner. Fast and robust smallest enclosing balls. In Proc. 7th annu. European Symposium on Algorithms (ESA), volume 1643 of Lecture Notes in Computer Science, pages 325-338. Springer-Verlag, 1999.

[GGHT97] M. Goodrich, L. J. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 284-293, 1997.

[GH97] M. Garland and P. S. Heckbert. Surface simplification using quadric error metrics. In Proc. SIGGRAPH '97, pages 209-216, 1997.

[GHH+03] Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Ketter, Kurt Mehlhorn, and Michael Seel. Boolean operations on 3d selective nef complexes data structure, algorithms, and implementation. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003: 11th Annual European Symposium, volume 2832 of Lecture Notes in Computer Science, pages 174-186, Budapest, Hugary, September 2003. Springer.

[GHJV95] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.

[GKR04] Leonidas Guibas, Menelaos Karaveles, and Daniel Russel. A computational framework for handling motion. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, pages 129-141, 2004.

[GM98] Leonidas Guibas and David Marimont. Rounding arrangements dynamically. Internat. J. Comput. Geom. Appl., 8:157-176, 1998.

[Gra] Torbjörn Granlund. GMP, the GNU multiple precision arithmetic library.

[Gra72] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132-133, 1972.

[Gre83] Daniel H. Greene. The decomposition of polygons into convex parts. In Franco P. Preparata, editor, Computational Geometry, volume 1 of Adv. Comput. Res., pages 235-259. JAI Press, Greenwich, Conn., 1983.

[GRS83] Leonidas J. Guibas, L. Ramshaw, and J. Stolfi. A kinetic framework for computational geometry. In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pages 100-111, 1983.

[GS78] Leonidas J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th Annu. IEEE Sympos. Found. Comput. Sci., Lecture Notes Comput. Sci., pages 8-21. Springer-Verlag, 1978.

[GS85] Leonidas J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4(2):74-123, April 1985.

[GS97a] B. Gärtner and S. Schönherr. Exact primitives for smallest enclosing ellipses. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 430-432, 1997.

[GS97b] Bernd Gärtner and Sven Schönherr. Smallest enclosing ellipses - fast and exact. Serie B - Informatik B 97-03, Freie Universität Berlin, Germany, June 1997. URL

[GS98a] Bernd Gärtner and Sven Schönherr. Smallest enclosing circles - an exact and generic implementation in C++. Serie B - Informatik B 98-04, Freie Universität Berlin, Germany, April 1998. URL

[GS98b] Bernd Gärtner and Sven Schönherr. Smallest enclosing ellipses - an exact and generic implementation in C++. Serie B - Informatik B 98-05, Freie Universität Berlin, Germany, April 1998. URL

[GS00] Bernd Gärtner and Svend Schönherr. An efficient, exact, and generic quadratic programming solver for geometric optimization. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 110-118, 2000.

[GvL83] G. Golub and C. van Loan. Matrix Computations. Johns Hopkins Univ. Press, Baltimore, MA, 1983.

[GVRLR98] L. Gonzalez-Vega, T. Recio, H. Lombardi, and M.-F. Roy. Sturm-habicht sequences, determinants and real roots of univariate polynomials. In B.F. Caviness and J.R. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 300-316. Springer, 1998.

[Hal04] Dan Halperin. Arrangements. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 24, pages 529-562. Chapman & Hall/CRC, 2nd edition, 2004.

[Han91] E. N. Hanson. The interval skip list: a data structure for finding all intervals that overlap a point. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes Comput. Sci., pages 153-164. Springer-Verlag, 1991.

[HDD+92] Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Surface reconstruction from unorganized points. In Computer Graphics (Proc. SIGGRAPH '90), volume 26, pages 71-77, 1992.

[HDD+93] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. In Proc. SIGGRAPH '93, pages 19-26, 1993.

[HGY+99] P. W. Hallinan, G. Gordon, A.L. Yuille, P. Giblin, and D. Mumford. Two-and Three-Dimensional Patterns of the Face. A.K.Peters, 1999.

[HH05] Idit Haran and Dan Halperin. Efficient point location in cgal arrangements using landmarks, 2005.

[HM83] S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conf. Found. Comput. Theory, volume 158 of Lecture Notes Comput. Sci., pages 207-218. Springer-Verlag, 1983.

[Hob99] J. D. Hobby. Practical segment intersection with finite precision output. Comput. Geom. Theory Appl., 13(4):199-214, October 1999.

[Hof89a] C. Hoffmann. Geometric and Solid Modeling. Morgan-Kaufmann, San Mateo, CA, 1989.

[Hof89b] C. M. Hoffmann. The problems of accuracy and robustness in geometric computation. IEEE Computer, 22(3):31-41, March 1989.

[Hof89c] Christoph M. Hoffmann. Geometric and Solid Modeling - An Introduction. Morgan Kaufmann, 1989.

[Hof99] M. Hoffmann. A simple linear algorithm for computing rectangular three-centers. In Proc. 11th Canad. Conf. Comput. Geom., pages 72-75, 1999.

[Hof04] Christoph M. Hoffmann. Solid modeling. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 56, pages 1257-1278. Chapman & Hall/CRC, 2nd edition, 2004.

[HP02] D. Halperin and E. Packer. Iterated snap rounding. Computational Geometry: Theory and Applications, 23(2):209-225, 2002.

[HS95] G. R. Hjaltason and H. Samet. Ranking in spatial databases. In M. J. Egenhofer and J. R. Herring, editors, Advances in Spatial Databases - Fourth International Symposium, number 951 in Lecture Notes Comput. Sci., pages 83-95, August 1995.

[HS00] Hisamoto Hiyoshi and Kokichi Sugihara. Voronoi-based interpolation with higher continuity. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 242-250, 2000.

[HW96] Jed Hartman and Josie Wernecke. The VRML 2.0 Handbook: Building Moving Worlds on the Web. Addison-Wesley, 1996.

[Jar73] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Inform. Process. Lett., 2:18-21, 1973.

[Jos99] Nicolai M. Josuttis. The C++ Standard Library, A Tutorial and Reference. Addison-Wesley, 1999.

[Kar04] Menelaos I. Karavelas. A robust and efficient implementation for the segment Voronoi diagram. In Proc. Internat. Symp. on Voronoi diagrams in Science and Engineering (VD2004), pages 51-62, 2004.

[KBH06] Michael Kazhdan, M. Bolitho, and Hugues Hoppe. Poisson Surface Reconstruction. In Symp. on Geometry Processing, pages 61-70, 2006.

[KE02] Menelaos I. Karavelas and Ioannis Z. Emiris. Predicates for the planar additively weighted Voronoi diagram. Technical Report ECG-TR-122201-01, INRIA Sophia-Antipolis, Sophia-Antipolis, May 2002.

[KE03] Menelaos I. Karavelas and Ioannis Z. Emiris. Root comparison techniques applied to computing the additively weighted Voronoi diagram. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 320-329, 2003.

[Ker09] Michael Kerber. Geometric Algorithms for Algebraic Curves and Surfaces. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany, 2009.

[Ket98] L. Kettner. Designing a data structure for polyhedral surfaces. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 146-154, 1998.

[Ket99] L. Kettner. Using generic programming for designing a data structure for polyhedral surfaces. Comput. Geom. Theory Appl., 13:65-90, 1999.

[Kha96] L. Khachiyan. Rounding of polytopes in the real number model of computation. Mathematics of Operations Research, 21(2):307-320, 1996.

[Kle89] Rolf Klein. Concrete and Abstract Voronoi Diagrams, volume 400 of Lecture Notes Comput. Sci. Springer-Verlag, 1989.

[KLPY99] Vijay Karamcheti, Chen Li, Igor Pechtchanski, and Chee Yap. The CORE Library Project, 1.2 edition, 1999.

[KM76] K. Kuratowski and A. Mostowski. Set Theory. North-Holland Publishing Co., 1976.

[KMP+08] Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Classroom examples of robustness problems in geometric computations. Computational Geometry: Theory and Applications, 40(1):61-78, may 2008.

[Kob00] Leif Kobbelt. 3-subdivision. In Computer Graphics (Proc. SIGGRAPH '00), volume 34, pages 103-112, 2000.

[KV05] N.G.H. Kruithof and G. Vegter. Meshing skin surfaces with certified topology. In Proceedings of the nineth International CADGraphics conference, page to appear., 2005.

[KY02] Menelaos Karavelas and Mariette Yvinec. Dynamic additively weighted voronoi diagrams in 2d. In Proc. 10th European Symposium on Algorithms, pages 586-598, 2002.

[Lat91] J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.

[LD03] R. G. Laycock and A. M. Day. Automatically generating roof models from building footprints. In The 11-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2003. Journal of WSCG - FULL Papers, volume 11, 2003.

[Lev05] Bruno Levy. Numerical methods for digital geometry processing. In Israel Korea Bi-National Conference - Invited talk, extended abstract (full paper will be available shortly), November 2005.

[Lie91] P. Lienhardt. Topological models for boundary representation: a comparison with n-dimensional generalized maps. Computer-Aided Design, 23(1):59-82, 1991.

[Lie94] P. Lienhardt. N-dimensional generalized combinatorial maps and cellular quasi-manifolds. Internat. J. Comput. Geom. Appl., 4(3):275-324, 1994.

[LPRM02] Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. Least squares conformal maps for automatic texture atlas generation. In Proceedings of the 29th Conference on Computer Graphics and Interactive Techniques SIGGRAPH, volume 21(3) of ACM Transactions on Graphics, pages 362-371, 2002.

[LPT09] Sylvain Lazard, Luis Peñaranda, and Elias Tsigaridas. Univariate algebraic kernel and application to arrangements. In Jan Vahrenhold, editor, SEA, volume 5526 of Lecture Notes in Computer Science, pages 209-220. Springer, 2009.

[LS05] Yuanxin Liu and Jack Snoeyink. A comparison of five implementations of 3D delaunay tessellation. In János Pach Jacob E. Goodman and Emo Welzl, editors, Combinatorial and Computational Geometry, pages 439-458. MSRI Publications, 2005.

[LT98] Peter Lindstrom and Greg Turk. Fast and memory efficient polygonal simplification. In IEEE Visualization, pages 279-286, 1998.

[LT99] P. Lindstrom and G. Turk. Evaluation of memoryless simplification. IEEE Transactions on Visualization and Computer Graphics, 5(2):98-115, /1999.

[MAD05] Abdelkrim Mebarki, Pierre Alliez, and Olivier Devillers. Farthest point seeding for efficient placement of streamlines. In Proceeding of IEEE Visualization, 2005.

[Män88] M. Mäntylä. An Introduction to Solid Modeling. Computer Science Press, Rockville, MD, 1988.

[Meh84] Kurt Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, volume 3 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Heidelberg, Germany, 1984.

[Mel87] A. Melkman. On-line construction of the convex hull of a simple polyline. Inform. Process. Lett., 25:11-12, 1987.

[Mey06] Michal Meyerovitch. Robust, generic, and efficient constructions of envelopes of surfaces in three-dimensional space. Master's thesis, Tel-Aviv University, Israel, 2006.

[MG06] J. Matoušek and B. Gärtner. Understanding and Using Linear Programming. Springer-Verlag, 2006.

[MN00] Kurt Mehlhorn and Stefan Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK, 2000.

[MNS+96] Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel, Raimund Seidel, and Christian Uhrig. Checking geometric programs or verification of geometric structures. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 159-165, 1996.

[MNSU] K. Mehlhorn, S. Näher, M. Seel, and C. Uhrig. The LEDA User Manual. Max-Planck-Insitut für Informatik, 66123 Saarbrücken, Germany.

[MP78] D. E. Muller and F. P. Preparata. Finding the intersection of two convex polyhedra. Theoret. Comput. Sci., 7:217-236, 1978.

[MP05] Guillaume Melquiond and Sylvain Pion. Formal certification of arithmetic filters for geometric predicates. In Proc. 17th IMACS World Congress on Scientific, Applied Mathematics and Simulation, 2005.

[MPFa] MPFI - the multiple precision floating-point interval library. Revol, Nathalie and Rouillier, Fabrice.

[MPFb] MPFR - the multiple precision floating-point reliable library. The MPFR Team.

[MS96] David R. Musser and Atul Saini. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 1996.

[MSW92] J. Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 1-8, 1992.

[Mul90] K. Mulmuley. A fast planar partition algorithm, I. J. Symbolic Comput., 10(3-4):253-280, 1990.

[Mye95] Nathan C. Myers. Traits: a new and useful template technique. C++ Report, June 1995.

[OBS04] Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel. Ridge-valley lines on meshes via implicit surface fitting. ACM Trans. Graph., 23(3):609-612, 2004.

[Orl90] M. Orlowski. A new algorithm for the largest empty rectangle problem. Algorithmica, 5:65-73, 1990.

[ORY05] Steve Oudot, Laurent Rineau, and Mariette Yvinec. Meshing volumes bounded by smooth surfaces. In Proc. 14th International Meshing Roundtable, pages 203-219, 2005.

[PABL07] M. Poudret, A. Arnould, Y. Bertrand, and P. Lienhardt. Cartes combinatoires ouvertes. Research Notes 2007-1, Laboratoire SIC E.A. 4103, F-86962 Futuroscope Cedex, France, October 2007.

[PB89] L. K. Platzman and J. J. Bartholdi, III. Spacefilling curves and the planar travelling salesman problem. J. ACM, 36(4):719-737, October 1989.

[Ped70] D. Pedoe. Geometry, a comprehensive course. Dover Publications, New York, 1970.

[Pet01] S. Petitjean. A survey of methods for recovering quadrics in triangle meshes. ACM Computing Surveys, 34(2), 2001.

[Phi96] Mark Phillips. Geomview Manual, Version 1.6.1 for Unix Workstations. The Geometry Center, University of Minnesota, 1996.

[Pip93] B. Piper. Properties of local coordinates based on dirichlet tesselations. Computing Suppl., 8:227-239, 1993.

[Por01] I. Porteous. Geometric Differentiation (2nd Edition). Cambridge University Press, 2001.

[PP93] U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1):15-36, 1993.

[PTVF02] W. Press, S. Teukolsky, W. Vetterling, and B. Flannery. Numerical Recipes in C++. Cambridge University Press, 2nd edition, 2002.

[Pug90] W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668-676, 1990.

[Req80] Aristides G. Requicha. Representations for rigid solids: Theory, methods, and systems. ACM Computing Surveys, 12(4):437-464, 1980.

[RS] RS - A software for real solving of algebraic systems. Rouillier, Fabrice.

[Rup95] J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms, 18:548-585, 1995.

[RY07] Laurent Rineau and Mariette Yvinec. A generic software design for Delaunay refinement meshing. Comput. Geom. Theory Appl., 38:100-110, 2007.

[RZ04] Fabrice Rouillier and Paul Zimmermann. Efficient isolation of polynomial's real roots. Journal of Computational and Applied Mathematics, 162(1):33-50, 2004.

[Sam90] H. Samet. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990.

[Sch95] O. Schwarzkopf. The extensible drawing editor Ipe. In Proceedings of the eleventh annual symposium on Computational geometry, pages 410-411. ACM New York, NY, USA, 1995.

[Sch96] Michael Schutte. Zufällige konvexe mengen. Master's thesis, Freie Universität Berlin, Germany, 1996.

[Sch00] Stefan Schirra. Robustness and precision issues in geometric computation. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, chapter 14, pages 597-632. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[Sei91] R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):51-64, 1991.

[She98a] Jonathan R. Shewchuk. A condition guaranteeing the existence of higher-dimensional constrained delaunay triangulations. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 76-85, 1998.

[She98b] Jonathan R. Shewchuk. Tetrahedral mesh generation by Delaunay refinement. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 86-95, 1998.

[She00] Jonathan R. Shewchuk. Mesh generation for domains with small angles. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 1-10, 2000.

[Sib80] R. Sibson. A vector identity for the Dirichlet tesselation. Math. Proc. Camb. Phil. Soc., 87:151-155, 1980.

[Sib81] R. Sibson. A brief description of natural neighbour interpolation. In Vic Barnet, editor, Interpreting Multivariate Data, pages 21-36. John Wiley & Sons, Chichester, 1981.

[Sil97] Silicon Graphics Computer Systems, Inc. Standard template library programmer's guide., 1997.

[Skl72] J. Sklansky. Measuring concavity on rectangular mosaic. IEEE Trans. Comput., C-21:1355-1364, 1972.

[SL95] Alexander Stepanov and Meng Lee. The standard template library, October 1995.

[SLL02] Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. Boost Graph Library. Addison-Wesley, 2002.

[SM00] M. Seel and K. Mehlhorn. Infimaximal frames: A technique for making lines look like segments. Research Report MPI-I-2000-1-005, MPI für Informatik, Saarbrücken, Germany, December 2000.

[SP05] Le-Jeng Shiue and Jörg Peters. Mesh refinement based on euler encoding. In Proceedings of the International Conference on Shape Modeling and Applications 2005, pages 343-348, 2005.

[STV+95] Christian Schwarz, Jürgen Teich, Alek Vainshtein, Emo Welzl, and Brian L. Evans. Minimal enclosing parallelogram with application. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages C34-C35, 1995.

[SW96] Micha Sharir and Emo Welzl. Rectilinear and polygonal p-piercing and p-center problems. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 122-132, 1996.

[Tar83] R. E. Tarjan. Data Structures and Network Algorithms, volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.

[Tei99] Monique Teillaud. Three dimensional triangulations in CGAL. In Abstracts 15th European Workshop Comput. Geom., pages 175-178. INRIA Sophia-Antipolis, 1999.

[Ter05] P. Terdiman. OPCODE 3D Collision Detection library, 2005.

[Tou83] G. T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON '83, pages A10.02/1-4, 1983.

[Tou09] Jane Tournois. Optimisation de maillages. Thèse de doctorat en sciences, Université Nice Sophia-Antipolis, Nice, France, 2009.

[TSA09] Jane TOURNOIS, Rahul SRINIVASAN, and Pierre ALLIEZ. Perturbing slivers in 3D Delaunay meshes. In Proceedings of the 18th International Meshing Roundtable, october 2009.

[Tut63] W. T. Tutte. How to draw a graph. Proceedings London Mathematical Society, 13(52):743-768, 1963.

[TWAD09] Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Transactions on Graphics, 28(3):75:1-75:9, 2009. SIGGRAPH '2009 Conference Proceedings.

[Vai90] A. Vainshtein. Finding minimal enclosing parallelograms. Diskretnaya Matematika, 2:72-81, 1990. In Russian.

[vLS82] J. van Leeuwen and Anneke A. Schoone. Untangling a travelling salesman tour in the plane. In J. R. Mühlbacher, editor, Proc. 7th Internat. Workshop Graph-Theoret. Concepts Comput. Sci., pages 87-98, München, 1982. Hanser.

[VRM96] The virtual reality modeling language specification: Version 2.0, ISO/IEC CD 14772., August 4 1996.

[vzGG99] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.

[Wei85] K. Weiler. Edge-based data structures for solid modeling in a curved surface environment. IEEE Comput. Graph. Appl., 5(1):21-40, 1985.

[Wel91] Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, volume 555 of Lecture Notes Comput. Sci., pages 359-370. Springer-Verlag, 1991.

[Wer94] Josie Wernicke. The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Release 2. Addison-Wesley, 1994.

[WW02] Joe Warren and Henrik Weimer. Subdivision Methods for Geometric Design. Morgan Kaufmann Publishers, New York, 2002.

[Yap97] C. Yap. Towards exact geometric computation. Comput. Geom. Theory Appl., 7(1):3-23, 1997.

[YD95] C. K. Yap and T. Dubé. The exact computation paradigm. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 452-492. World Scientific, Singapore, 2nd edition, 1995.

[ZE02] Afra Zomorodian and Herbert Edelsbrunner. Fast software for box intersection. Int. J. Comput. Geom. Appl., 12:143-172, 2002.