Computational geometry in C. (English) Zbl 0816.68124

Cambridge: Univ. Press. ix, 346 p. $ 24.95; £16.95 /sc; $ 59.95; £35.00 /hc (1994).
This book is written as an undergraduate text book in computational geometry. The main contents concern polygon partitioning, convex hulls, Voronoi diagrams, arrangement of lines, geometric searching, and motion planning. Basic materials are presented in great detail, with C programming codes and rigorous mathematical proofs. Also included are some advanced materials relating to recent developments at the research frontier. The advanced topics are generally sketched out with brief descriptions of the underlying geometric concept, with further details presented in exercise form. References are also supplied quite faithfully throughout the text. As is fitting in a text book aimed at undergraduate students, the materials presented are carefully tailored: unnecessary details are eliminated and related geometric concepts and structures are helpfully pieced together. As a result, the book is written in a style which makes it remarkably easy to read and understand. Abundant graphical illustrations also play an important role here.
The author does an excellent job in maintaining the balance between basic geometric concepts and advanced research results. The key ideas are explained intuitively with illustrative examples which are often superior to those used in the original papers. Further references are skillfully inserted as appropriate, with brief discussion, while not interrupting the main stream of explanation. The C programming codes in the book offer a further level of balance between theory and practice. Attempts are also made to present algorithms which produce optimal coding, though not necessarily optimal performance.
The book considers three geometric structures to be of primary importance in computational geometry: convex hulls, Voronoi diagrams, and arrangement. The duality between point and line/plane plays an important part in integrating the three concepts. Though the duality has not been generalized to polygons in computational geometry literatures (including this book), a little consideration of the envelope theory in differential geometry could transform line/curve segments to developable surfaces under a similar duality. Nevertheless, there still remains an important question of how to compute the arrangement of developable surfaces efficiently.
It is now quite common practice for an algorithm course to incorporate a two to three week lectures on computational geometry. The core chapters of this book would serve this purpose satisfactorily. The book also provides indispensable computational tools and conceptual frameworks for researchers in science and engineering who are working on geometric problems.
Reviewer: M.-S.Kim (Pohang)


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science