Effective Computational Geometry for Curves and Surfaces / Edition 1

by Jean-Daniel Boissonnat, Monique Teillaud

Overview

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 effort has been undertaken to make computational geometry more practical. This effort 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 foundationsforeffectivecomputationalgeometryforcurvesandsurfaces. This book covers two main approaches. In a first 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 defined on curved objects. The mathematical properties of these structures are presented together with algorithms for their construction. To ensure the effectiveness of our algorithms, the basic numerical computations that need to be performed are precisely specified, and tradeoffs 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.

Product Details

ISBN-13:	9783642069871
Publisher:	Springer Berlin Heidelberg
Publication date:	10/27/2010
Series:	Mathematics and Visualization
Edition description:	Softcover reprint of hardcover 1st ed. 2006
Pages:	344
Product dimensions:	6.10(w) x 9.25(h) x 0.03(d)

Table of Contents

1 Arrangements - Efi Fogel, Dan Halperin, Lutz Kettner, Monique Teillaud, Ron Wein, Nicola Wolpert.- 2 Curved Voronoi Diagrams - Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec.- 3 Algebraic Issues in Computational Geometry - Bernard Mourrain, Sylvain Pion, Susanne Schmitt, Jean-Pierre Técourt, Elias Tsigaridas, Nicola Wolpert.- 4 Differential Geometry on Discrete Surfaces - David Cohen-Steiner, Jean-Marie Morvan.- 5 Meshing of Surfaces - Jean-Daniel Boissonnat, David Cohen-Steiner, Bernard Mourrain, Günter Rote, Gert Vegter.- 6 Delaunay Triangulation Based Surface Reconstruction - Frédéric Cazals, Joachim Giesen.- 7 Computational Topology: An Introduction - Günter Rote, Gert Vegter.- 8 Appendix - Generic Programming and the Cgal Library - Efi Fogel, Monique Teillaud.- References.- Index.

Editorial Reviews

From the reviews:

"Boissonat and Teillaud 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, MathDL, March, 2007)

From the Publisher