Book Details

Internet Resource: Please Login to download book

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. 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 effiective computational geometry fo rcurves and surfaces. 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 de?ned on curved objects.