| Arrangements | p. 1 |
| Introduction | p. 1 |
| Chronicles | p. 3 |
| Exact Construction of Planar Arrangements | p. 5 |
| Construction by Sweeping | p. 7 |
| Incremental Construction | p. 20 |
| Software for Planar Arrangements | p. 25 |
| The Cgal Arrangements Package | p. 26 |
| Arrangements Traits | p. 33 |
| Traits Classes from Exacus | p. 36 |
| An Emerging Cgal Curved Kernel | p. 38 |
| How To Speed Up Your Arrangement Computation in Cgal | p. 40 |
| Exact Construction in 3-Space | p. 41 |
| Sweeping Arrangements of Surfaces | p. 41 |
| Arrangements of Quadrics in 3D | p. 45 |
| Controlled Perturbation: Fixed-Precision Approximation of Arrangements | p. 50 |
| Applications | p. 53 |
| Boolean Operations on Generalized Polygons | p. 53 |
| Motion Planning for Discs | p. 57 |
| Lower Envelopes for Path Verification in Multi-Axis NC-Machining | p. 59 |
| Maximal Axis-Symmetric Polygon Contained in a Simple Polygon | p. 62 |
| Molecular Surfaces | p. 63 |
| Additional Applications | p. 64 |
| Further Reading and Open problems | p. 66 |
| Curved Voronoi Diagrams | p. 67 |
| Introduction | p. 68 |
| Lower Envelopes and Minimization Diagrams | p. 70 |
| Affine Voronoi Diagrams | p. 72 |
| Euclidean Voronoi Diagrams of Points | p. 72 |
| Delaunay Triangulation | p. 74 |
| Power Diagrams | p. 78 |
| Voronoi Diagrams with Algebraic Bisectors | p. 81 |
| Mobius Diagrams | p. 81 |
| Anisotropic Diagrams | p. 86 |
| Apollonius Diagrams | p. 88 |
| Linearization | p. 92 |
| Abstract Diagrams | p. 92 |
| Inverse Problem | p. 97 |
| Incremental Voronoi Algorithms | p. 99 |
| Planar Euclidean diagrams | p. 101 |
| Incremental Construction | p. 101 |
| The Voronoi Hierarchy | p. 106 |
| Medial Axis | p. 109 |
| Medial Axis and Lower Envelope | p. 110 |
| Approximation of the Medial Axis | p. 110 |
| Voronoi Diagrams in Cgal | p. 114 |
| Applications | p. 115 |
| Algebraic Issues in Computational Geometry | p. 117 |
| Introduction | p. 117 |
| Computers and Numbers | p. 118 |
| Machine Floating Point Numbers: the IEEE 754 norm | p. 119 |
| Interval Arithmetic | p. 120 |
| Filters | p. 121 |
| Effective Real Numbers | p. 123 |
| Algebraic Numbers | p. 124 |
| Isolating Interval Representation of Real Algebraic Numbers | p. 125 |
| Symbolic Representation of Real Algebraic Numbers | p. 125 |
| Computing with Algebraic Numbers | p. 126 |
| Resultant | p. 126 |
| Isolation | p. 131 |
| Algebraic Numbers of Small Degree | p. 136 |
| Comparison | p. 138 |
| Multivariate Problems | p. 140 |
| Topology of Planar Implicit Curves | p. 142 |
| The Algorithm from a Geometric Point of View | p. 143 |
| Algebraic Ingredients | p. 144 |
| How to Avoid Genericity Conditions | p. 145 |
| Topology of 3d Implicit Curves | p. 146 |
| Critical Points and Generic Position | p. 147 |
| The Projected Curves | p. 148 |
| Lifting a Point of the Projected Curve | p. 149 |
| Computing Points of the Curve above Critical Values | p. 151 |
| Connecting the Branches | p. 152 |
| The Algorithm | p. 153 |
| Software | p. 154 |
| Differential Geometry on Discrete Surfaces | p. 157 |
| Geometric Properties of Subsets of Points | p. 157 |
| Length and Curvature of a Curve | p. 158 |
| The Length of Curves | p. 158 |
| The Curvature of Curves | p. 159 |
| The Area of a Surface | p. 161 |
| Definition of the Area | p. 161 |
| An Approximation Theorem | p. 162 |
| Curvatures of Surfaces | p. 164 |
| The Smooth Case | p. 164 |
| Pointwise Approximation of the Gaussian Curvature | p. 165 |
| From Pointwise to Local | p. 167 |
| Anisotropic Curvature Measures | p. 174 |
| [epsilon]-samples on a Surface | p. 178 |
| Application | p. 179 |
| Meshing of Surfaces | p. 181 |
| Introduction: What is Meshing? | p. 181 |
| Overview | p. 187 |
| Marching Cubes and Cube-Based Algorithms | p. 188 |
| Criteria for a Correct Mesh Inside a Cube | p. 190 |
| Interval Arithmetic for Estimating the Range of a Function | p. 190 |
| Global Parameterizability: Snyder's Algorithm | p. 191 |
| Small Normal Variation | p. 196 |
| Delaunay Refinement Algorithms | p. 201 |
| Using the Local Feature Size | p. 202 |
| Using Critical Points | p. 209 |
| A Sweep Algorithm | p. 213 |
| Meshing a Curve | p. 215 |
| Meshing a Surface | p. 216 |
| Obtaining a Correct Mesh by Morse Theory | p. 223 |
| Sweeping through Parameter Space | p. 223 |
| Piecewise-Linear Interpolation of the Defining Function | p. 224 |
| Research Problems | p. 227 |
| Delaunay Triangulation Based Surface Reconstruction | p. 231 |
| Introduction | p. 231 |
| Surface Reconstruction | p. 231 |
| Applications | p. 231 |
| Reconstruction Using the Delaunay Triangulation | p. 232 |
| A Classification of Delaunay Based Surface Reconstruction Methods | p. 233 |
| Organization of the Chapter | p. 234 |
| Prerequisites | p. 234 |
| Delaunay Triangulations, Voronoi Diagrams and Related Concepts | p. 234 |
| Medial Axis and Derived Concepts | p. 244 |
| Topological and Geometric Equivalences | p. 249 |
| Exercises | p. 252 |
| Overview of the Algorithms | p. 253 |
| Tangent Plane Based Methods | p. 253 |
| Restricted Delaunay Based Methods | p. 257 |
| Inside / Outside Labeling | p. 261 |
| Empty Balls Methods | p. 268 |
| Evaluating Surface Reconstruction Algorithms | p. 271 |
| Software | p. 272 |
| Research Problems | p. 273 |
| Computational Topology: An Introduction | p. 277 |
| Introduction | p. 277 |
| Simplicial complexes | p. 278 |
| Simplicial homology | p. 282 |
| Morse Theory | p. 295 |
| Smooth functions and manifolds | p. 295 |
| Basic Results from Morse Theory | p. 300 |
| Exercises | p. 310 |
| Appendix - Generic Programming and The Cgal Library | p. 313 |
| The Cgal Open Source Project | p. 313 |
| Generic Programming | p. 314 |
| Geometric Programming and Cgal | p. 316 |
| Cgal Contents | p. 318 |
| References | p. 321 |
| Index | p. 341 |
| Table of Contents provided by Ingram. All Rights Reserved. |
