Algorithms in Combinatorial Geometry

§Computational geometry emerged in the early seventies as an area of research in its own right. From the beginning, it was obvious that there were strong connections to questions studied in 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. This 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 approach to the subject is new. The book is also an encyclopedic collection of results in the field. §Each chapter includes a set of exercises of various degrees of difficulty whose purpose is to give results that extend the material presented and to point out related open problems. Each chapter also contains bibliographic notes which point out solutions in the existing literature to some of the more difficult problems from the exercise section.