This book covers combinatorial data structures and algorithms, algebraic issues in geometric computing, approximation of curves and surfaces, and computational topology. Each chapter fully details and provides a tutorial introduction to important concepts and results. The focus is on methods which are both well founded mathematically and efficient in practice. Coverage includes references to open source software and discussion of potential applications of the presented techniques.

Computational geometry emerged as a discipline in the seventies and has had considerable success in improving the asymptotic complexity of the solutions to basic geometric problems including constructions of data structures, 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 foundations for effective computational geometry for curves and surfaces. This book covers two main approaches.