You are here

Effective Computational Geometry for Curves and Surfaces

Jean-Daniel Boissonnat and Monique Teillaud, editors
Publisher: 
Springer Verlag
Publication Date: 
2007
Number of Pages: 
343
Format: 
Hardcover
Series: 
Mathematics and Visualization
Price: 
99.00
ISBN: 
9783540332589
Category: 
Anthology
[Reviewed by
Luiz Henrique de Figueiredo
, on
03/25/2007
]

Computational Geometry is study of algorithms for geometric problems. Historically, Computational Geometry has meant several different, but related, disciplines. The classical book Perceptrons, by Minsky and Pappert (1969), was about neural networks but was subtitled "An introduction to computational geometry". Another classical book was Computational Geometry for Design and Manufacture, by Faux and Pratt (1979); it was about what is now called computer-aided design and geometric modeling.

Nowadays, Computational Geometry is a well-established sub-discipline of computer science and deals mainly with discrete geometry, with emphasis on algorithms that are optimal in the worst case. The classical reference for this brand of Computational Geometry is the book Computational Geometry: An Introduction by Preparata and Shamos (1985). Since the mid 1990s an effort has been under way to attack practical geometric problems with an increasing emphasis on algorithms that can be implemented in practice, so as to get closer to industrial applications.

Boissonat and Teillard have collected in this book the foundations of a computational geometry that no longer deals exclusively with linear objects but also with curved objects that arise in applications. The book is composed of eight chapters written by teams of experts in each theme, and is the result of an European Union project named ECG .

The book can serve as an advanced graduate course on computational geometry and as a reference for researchers interested in geometric algorithms for curved objects.


Luiz Henrique de Figueiredo is a researcher at IMPA in Rio de Janeiro, Brazil. His main interests are numerical methods in computer graphics, but he remains an algebraist at heart. He is also one of the designers of the Lua language.

1 Arrangements
Efi Fogel, Dan Halperin, Lutz Kettner, Monique Teillaud, Ron Wein, Nicola Wolpert 1.1 Introduction
1.2 Chronicles
1.3 Exact Construction of Planar Arrangements
1.3.1Construction by Sweeping
1.3.2 Incremental Construction
1.4  Software for Planar Arrangements
1.4.1 The Cgal Arrangements Package
1.4.2 Arrangements Traits
1.4.3 Traits Classes from Exacus
1.4.4An Emerging Cgal Curved Kernel
1.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 3D
1.6 Controlled Perturbation: Fixed-Precision Approximation of Arrangements
1.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-Machining
1.7.4 Maximal Axis-Symmetric Polygon Containedin a Simple Polygon
1.7.5 Molecular Surfaces
1.7.6 Additional Applications
1.8 Further Reading and Open problems
2 Curved Voronoi Diagrams
Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec
2.1 Introduction
2.2 Lower Envelopes and Minimization Diagrams
2.3 Affine Voronoi Diagrams
2.3.1 Euclidean Voronoi Diagrams of Points
2.3.2 Delaunay Triangulation
2.3.3 PowerDiagrams
2.4 Voronoi Diagrams with Algebraic Bisectors
2.4.1 Möbius Diagrams
2.4.2 Anisotropic Diagrams
2.4.3Apollonius Diagrams
2.5 Linearization
2.5.1Abstract Diagrams
2.5.2 Inverse Problem
2.6 Incremental Voronoi Algorithms
2.6.1 Planar Euclidean diagrams
2.6.2 Incremental Construction
2.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 Introduction
3.2 Computers and Numbers
3.2.1 Machine Floating Point Numbers: the IEEE 754 norm........119
3.2.2 Interval Arithmetic ......................................120
3.2.3 Filters..................................................121
3.3 Effective Real Numbers .......................................123
3.3.1 Algebraic Numbers ......................................124
3.3.2 Isolating Interval Representation of Real Algebraic Numbers
3.3.3 Symbolic Representation of Real Algebraic Numbers .........125
3.4 Computing with Algebraic Numbers ............................126
3.4.1 Resultant...............................................126
3.4.2 Isolation................................................131
3.4.3Algebraic Numbers of Small Degree ........................136
3.4.4 Comparison.............................................138
3.5 Multivariate Problems ........................................140
3.6  Topology of Planar Implicit Curves.............................142
3.6.1 The Algorithm from a Geometric Point of View .............143
3.6.2 Algebraic Ingredients.....................................144
3.6.3 How to Avoid Genericity Conditions .......................145
3.7  Topology of 3d Implicit Curves.................................146
3.7.1 Critical Points and Generic Position........................147
3.7.2 The Projected Curves ....................................148
3.7.3 Lifting a Point of the Projected Curve......................149
3.7.4 Computing Points of the Curve above CriticalValues.........151
3.7.5 Connecting the Branches .................................152
3.7.6 The Algorithm ..........................................153
3.8 Software ....................................................154
4 Differential Geometry on Discrete Surfaces
David Cohen-Steiner, Jean-Marie Morvan 
4.1 Geometric Properties of Subsets of Points .......................157
4.2  Length and Curvature of a Curve...............................158
4.2.1 The Length of Curves ....................................158
4.2.2 The Curvature of Curves .................................159
4.3   The Area of a Surface.........................................161
4.3.1 Definition of the Area ....................................161
4.3.2 An Approximation Theorem ..............................162
4.4 CurvaturesofSurfaces ........................................164
4.4.1 The Smooth Case........................................164
4.4.2 Pointwise Approximation of the Gaussian Curvature .........165
4.4.3 From Pointwise to Local..................................167
4.4.4 Anisotropic Curvature Measures...........................174
4.4.5 o-samples on a Surface....................................178
5 Meshing of Surfaces
Jean-Daniel Boissonnat, David Cohen-Steiner, Bernard Mourrain, Günter Rote, Gert Vegter
5.1 Introduction: What is Meshing?................................181
5.1.1 Overview ...............................................187
5.2 Marching Cubesand Cube-Based Algorithms ....................188
5.2.1 Criteria for a Correct Mesh Inside a Cube ..................190
5.2.2 Interval Arithmetic for Estimating the Range of a Function ...190
5.2.3 Global Parameterizability: Snyder’s Algorithm...............191
5.2.4 Small Normal Variation ..................................196
5.3 DelaunayRefinementAlgorithms...............................201
5.3.1 Using the Local Feature Size ..............................202
5.3.2 Using Critical Points.....................................209
5.4 A Sweep Algorithm...........................................213
5.4.1Meshing a Curve ........................................215
5.4.2Meshing a Surface .......................................216
5.5 Obtaining a Correct Mesh by Morse Theory .....................223
5.5.1 Sweeping through Parameter Space ........................223
5.5.2 Piecewise-Linear Interpolation of the Defining Function
5.6 Research Problems............................................227
6 Delaunay Triangulation Based Surface Reconstruction
Frédéric Cazals, Joachim Giesen
6.1 Introduction.................................................231
6.1.1 Surface Reconstruction ...................................231
6.1.2Applications ............................................231
6.1.3 Reconstruction Using the Delaunay Triangulation............232
6.1.4 A Classification of Delaunay Based Surface Reconstruction Methods
6.1.5 Organization of the Chapter ..............................234
6.2 Prerequisites.................................................234
6.2.1Delaunay Triangulations, Voronoi Diagrams and Related Concepts
6.2.2 Medial Axis and Derived Concepts.........................244
6.2.3 Topological and Geometric Equivalences....................249
6.2.4 Exercises ...............................................252
6.3 Overview of the Algorithms....................................253
6.3.1Tangent Plane Based Methods ............................253
6.3.2Restricted Delaunay Based Methods .......................257
6.3.3Inside/Outside Labeling.................................261
6.3.4Empty Balls Methods ....................................268
6.4 Evaluating Surface Reconstruction Algorithms
6.5 Software ....................................................272
6.6 Research Problems ...........................................273
7 Computational Topology: An Introduction
Günter Rote, Gert Vegter
7.1 Introduction.................................................277
7.2 Simplicialcomplexes..........................................278
7.3 Simplicial homology ..........................................282
7.4 MorseTheory................................................295
7.4.1 Smooth functions and manifolds ...........................295
7.4.2 Basic Results from Morse Theory..........................300
7.5 Exercises....................................................310
7.6 Appendix:SomeBasicResultsfromLinearAlgebra...............312
8 Appendix -Generic Programming and The Cgal Library
Efi Fogel, Monique Teillaud .......................................315
8.1 The Cgal OpenSourceProject ...............................315
8.2 Generic Programming ........................................316
8.3 Geometric Programming ......................................318
8.4 Cgal ......................................................320
References
Index