Effective Computational Geometry for Curves and Surfaces Book

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