Computational geometry

In the past decade the systematic study of geometric algorithms has evolved to form the very active field of research known as computational geometry. Computational Geometry: An Introduction presents a comprehensive, systematic, and coherent treatment of its subject. A fundamental task of computational geometry is identifying condepts, properties, and techniques which aid efficient algorithmic implementations from geometric problems. The approach taken here is the presentation of algorithms and the evaluation of their worst-case complexity. The particular classes of problems addressed include geometric searching and retrieval, convex hull construction and related problems, proximity, intersection, and the geometry of rectangles. Computational Geometry: An Introduction presents its methodology through detailed case studies. The book, primarily conceived as an early graduate text, should also be essential to researchers and professionals in the fields of computer-aided design, computer graphics and robotics.