Algorithms in Combinatorial Geometry

This book offers a modern approach to computational geometry, an area that studies the computational complexity of geometric problems. Computational geometry is strongly connected to the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge.
The book consists of three parts : a combinatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by the attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. The book is also a collection of a large number of results giving the book an encyclopedic character.
Each chapter includes a set of exercises of various degrees of difficulty. One of the purposes of these collections of exercises and open problems is to give results that extend the material presented in the corresponding chapters ; another purpose is to point out related open problems. Each chapter also contains a collection of bibliographic notes.