1 Arrangements Efi Fogel, Dan Halperin, Lutz Kettner, Monique Teillaud, Ron Wein, Nicola Wolpert 1.1 Introduction1.2 Chronicles1.3 Exact Construction of Planar Arrangements 1.3.1Construction by Sweeping 1.3.2 Incremental Construction1.4 Software for Planar Arrangements1.4.1 The Cgal Arrangements Package1.4.2 Arrangements Traits 1.4.3 Traits Classes from Exacus 1.4.4An Emerging Cgal Curved Kernel1.4.5 How To Speed UpYour Arrangement Computation in Cgal 1.5 Exact Construction in 3-Space 1.5.1 Sweeping Arrangements of Surfaces 1.5.2Arrangements of Quadricsin 3D1.6 Controlled Perturbation: Fixed-Precision Approximation of Arrangements1.7 Applications 1.7.1 Boolean Operations for Conics 1.7.2 Motion Planning for Discs 1.7.3 Lower Envelopes for Path Verification in Multi-Axis NC-Machining1.7.4 Maximal Axis-Symmetric Polygon Containedin a Simple Polygon 1.7.5 Molecular Surfaces1.7.6 Additional Applications 1.8 Further Reading and Open problems2 Curved Voronoi Diagrams Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec2.1 Introduction2.2 Lower Envelopes and Minimization Diagrams 2.3 Affine Voronoi Diagrams 2.3.1 Euclidean Voronoi Diagrams of Points2.3.2 Delaunay Triangulation2.3.3 PowerDiagrams2.4 Voronoi Diagrams with Algebraic Bisectors 2.4.1 Möbius Diagrams2.4.2 Anisotropic Diagrams 2.4.3Apollonius Diagrams2.5 Linearization 2.5.1Abstract Diagrams2.5.2 Inverse Problem 2.6 Incremental Voronoi Algorithms2.6.1 Planar Euclidean diagrams2.6.2 Incremental Construction2.6.3 The Voronoi Hierarchy 2.7 Medial Axis 2.7.1 Medial Axis and Lower Envelope 2.7.2 Approximation of the Medial Axis 2.8 Voronoi Diagrams in Cgal 2.9 Applications 3 Algebraic Issues in Computational Geometry Bernard Mourrain, Sylvain Pion, Susanne Schmitt, Jean-Pierre Técourt, Elias Tsigaridas, Nicola Wolpert 3.1 Introduction3.2 Computers and Numbers3.2.1 Machine Floating Point Numbers: the IEEE 754 norm........1193.2.2 Interval Arithmetic ......................................1203.2.3 Filters..................................................1213.3 Effective Real Numbers .......................................1233.3.1 Algebraic Numbers ......................................1243.3.2 Isolating Interval Representation of Real Algebraic Numbers 3.3.3 Symbolic Representation of Real Algebraic Numbers .........1253.4 Computing with Algebraic Numbers ............................1263.4.1 Resultant...............................................1263.4.2 Isolation................................................1313.4.3Algebraic Numbers of Small Degree ........................1363.4.4 Comparison.............................................1383.5 Multivariate Problems ........................................1403.6 Topology of Planar Implicit Curves.............................1423.6.1 The Algorithm from a Geometric Point of View .............1433.6.2 Algebraic Ingredients.....................................1443.6.3 How to Avoid Genericity Conditions .......................1453.7 Topology of 3d Implicit Curves.................................1463.7.1 Critical Points and Generic Position........................1473.7.2 The Projected Curves ....................................1483.7.3 Lifting a Point of the Projected Curve......................1493.7.4 Computing Points of the Curve above CriticalValues.........1513.7.5 Connecting the Branches .................................1523.7.6 The Algorithm ..........................................1533.8 Software ....................................................1544 Differential Geometry on Discrete Surfaces David Cohen-Steiner, Jean-Marie Morvan 4.1 Geometric Properties of Subsets of Points .......................1574.2 Length and Curvature of a Curve...............................1584.2.1 The Length of Curves ....................................1584.2.2 The Curvature of Curves .................................1594.3 The Area of a Surface.........................................1614.3.1 Definition of the Area ....................................1614.3.2 An Approximation Theorem ..............................1624.4 CurvaturesofSurfaces ........................................1644.4.1 The Smooth Case........................................1644.4.2 Pointwise Approximation of the Gaussian Curvature .........1654.4.3 From Pointwise to Local..................................1674.4.4 Anisotropic Curvature Measures...........................1744.4.5 o-samples on a Surface....................................1785 Meshing of Surfaces Jean-Daniel Boissonnat, David Cohen-Steiner, Bernard Mourrain, Günter Rote, Gert Vegter 5.1 Introduction: What is Meshing?................................1815.1.1 Overview ...............................................1875.2 Marching Cubesand Cube-Based Algorithms ....................1885.2.1 Criteria for a Correct Mesh Inside a Cube ..................1905.2.2 Interval Arithmetic for Estimating the Range of a Function ...1905.2.3 Global Parameterizability: Snyder's Algorithm...............1915.2.4 Small Normal Variation ..................................1965.3 DelaunayRefinementAlgorithms...............................2015.3.1 Using the Local Feature Size ..............................2025.3.2 Using Critical Points.....................................2095.4 A Sweep Algorithm...........................................2135.4.1Meshing a Curve ........................................2155.4.2Meshing a Surface .......................................2165.5 Obtaining a Correct Mesh by Morse Theory .....................2235.5.1 Sweeping through Parameter Space ........................2235.5.2 Piecewise-Linear Interpolation of the Defining Function5.6 Research Problems............................................2276 Delaunay Triangulation Based Surface Reconstruction Frédéric Cazals, Joachim Giesen 6.1 Introduction.................................................2316.1.1 Surface Reconstruction ...................................2316.1.2Applications ............................................2316.1.3 Reconstruction Using the Delaunay Triangulation............2326.1.4 A Classification of Delaunay Based Surface Reconstruction Methods6.1.5 Organization of the Chapter ..............................2346.2 Prerequisites.................................................2346.2.1Delaunay Triangulations, Voronoi Diagrams and Related Concepts6.2.2 Medial Axis and Derived Concepts.........................2446.2.3 Topological and Geometric Equivalences....................2496.2.4 Exercises ...............................................2526.3 Overview of the Algorithms....................................2536.3.1Tangent Plane Based Methods ............................2536.3.2Restricted Delaunay Based Methods .......................2576.3.3Inside/Outside Labeling.................................2616.3.4Empty Balls Methods ....................................2686.4 Evaluating Surface Reconstruction Algorithms 6.5 Software ....................................................2726.6 Research Problems ...........................................2737 Computational Topology: An Introduction Günter Rote, Gert Vegter 7.1 Introduction.................................................2777.2 Simplicialcomplexes..........................................2787.3 Simplicial homology ..........................................2827.4 MorseTheory................................................2957.4.1 Smooth functions and manifolds ...........................2957.4.2 Basic Results from Morse Theory..........................3007.5 Exercises....................................................3107.6 Appendix:SomeBasicResultsfromLinearAlgebra...............3128 Appendix -Generic Programming and The Cgal Library Efi Fogel, Monique Teillaud .......................................3158.1 The Cgal OpenSourceProject ...............................3158.2 Generic Programming ........................................3168.3 Geometric Programming ......................................3188.4 Cgal ......................................................320References Index

Computational geometry emerged as a discipline in the seventies and has had considerable success in improving the asymptotic complexity of the solutions tobasicgeometricproblemsincludingconstructionsofdatastructures,convex hulls, triangulations, Voronoi diagrams and geometric arrangements as well as geometric optimisation. However, in the mid-nineties, it was recognized that the computational geometry techniques were far from satisfactory in practice and a vigorous e?ort has been undertaken to make computational geometry more practical. This e?ort led to major advances in robustness, geometric software engineering and experimental studies, and to the development of a large library of computational geometry algorithms, Cgal. The goal of this book is to take into consideration the multidisciplinary nature of the problem and to provide solid mathematical and algorithmic foundationsfore?ectivecomputationalgeometryforcurvesandsurfaces. This book covers two main approaches. In a ?rst part, we discuss exact geometric algorithms for curves and s- faces. We revisit two prominent data structures of computational geometry, namely arrangements (Chap. 1) and Voronoi diagrams (Chap. 2) in order to understand how these structures, which are well-known for linear objects, behave when de?ned on curved objects. The mathematical properties of these structures are presented together with algorithms for their construction. To ensure the e?ectiveness of our algorithms, the basic numerical computations that need to be performed are precisely speci?ed, and tradeo?s are considered between the complexity of the algorithms (i. e. the number of primitive calls), and the complexity of the primitives and their numerical stability. Chap.