Computational Geometry - Algorithms and Applications

Author: (Netherlands) Berg, M. et al. Translated by Deng Junhui
Publisher:
Publish Date: 2005-09-01
Features: Computational geometry is an important branch of computer theoretical science. Since it was separated from algorithm design and analysis in the late 1970s, the discipline has undergone tremendous development in less than 30 years, producing a series of significant theoretical achievements and finding wide applications in numerous practical fields. The first four chapters of this book discuss geometric algorithms, including geometric intersection, triangulation, and linear programming, among which the random algorithms involved are a distinctive feature of the book. Chapters 5 to 10 introduce various geometric structures, including geometric search, kd-trees, region trees, trapezoidal graphs, Voronoi diagrams, permutations, Delaunay triangulation, interval trees, priority search trees, and segment trees. Chapters 11 to 16 continue to explore several geometric algorithms and data structures in the context of practical problems, including high-dimensional convex hulls, spatial bisection and BSP trees, motion planning, mesh generation and quad trees, shortest path search and visibility graphs, simplex region search and partition trees and cutting trees, further deepening the content of the previous ten chapters. This book is not only comprehensive but also closely tied to practical applications, with a clear focus and both in-depth explanations and "Notes and Comments" as well as "Exercises" at the end of each chapter, providing readers with opportunities for deeper understanding. As a result, it has been widely used as a textbook in many universities around the world in recent years. China's research in computational geometry started relatively late, and it is believed that the publication of this book will help promote the development of teaching in this field domestically.