Computational Geometry and Computer Graphics in C++ [Facsimile] [Paperback]

Are my references deficient because the papers it cites are no less than four years old (relative to the book's release date), and some even date to the 1970s? Most of the methods I present were devised years and even decades ago. I chose these methods to suit the book's purpose and audience; I chose methods that are basic, yet which a less sophisticated reader will find interesting and accessible. Similarly, I chose the book's references so they would be relevant to the book's content and useful to the reader.

The choice of what topics to present is always to some degree at the author's discretion, particularly in a book such as this which explores ideas without attempting comprehensive coverage. Critics can always be found who will take issue at the omission of this topic or the inclusion of that, or with how some topic is presented. But again, I chose the material with my book's objectives and audience in mind.

Relative to the expectations of a computational geometer or a graduate student, my book cannot compare to Preparata and Shamos', or to Mark deBerg's. Their audience doesn't require a book that spends half its time covering such fundamentals as algorithm analysis, lists and stacks, search trees, and elementary sorting and searching methods. Their audience would expect only the most limited coverage of these things, or no coverage at all. In contrast, given my book's target audience, to omit these topics would be to leave out the very background that the rest of the book not only requires, but that the intended reader likely lacks. Omitting such material would be a disservice to the intended reader. Likewise, to include certain more difficult topics which are the meat of these more advanced books would go well beyond the scope of my book, and to do this would also be a disservice to the intended reader. My book differs significantly from these other books in its objectives and its intended audience.

The first three chapters introduce the reader to the notion of algorithms and data structures. The author uses the boundary-intersection problem to illustrate the main points of the chapter, such as algorithmic paradigms and abstract data types. Complexity measures for algorithms are discussed briefly, along with mathematical induction. The linked list data structures he discusses are very important in computational geometry, especially the pointer-based implementation.

In chapter 4, the author discusses the data structures that are needed for dealing with geometric structures in dimension 2 and 3. After a review of vector algebra he defines the point class and then the vertex class. The latter, along with the polygon class, is used to define polygons as a cycle of vertices which are stored in a circular doubly linked list. These are generalized to 3 dimensions where classes are given for points, triangles, and edges. The author then gives an algorithm for finding the intersection of a line and a triangle, which uses projection, and tests for degeneracy before projecting.

The next part of the book deals with applications of the algorithms, such as finding a star-shaped polygon in a finite set of points, finding the convex hull of a set of points, the decision problem for points inside polygons, the Cyrus-Beck and Sutherland-Hodgman algorithms for clipping geometric objects to convex polygons, and an O(nlogn) algorithm for triangulating a monotone polygon. The treatment is very understandable and should prepare the reader for more advanced reading (especially in computer graphics). The famous gift wrapping algorithm for finding the convex hull is given, along with the Graham scan algorithm. Issues more pertinent to computer graphics, such as rendering are discussed also. The hidden surface removal problem is solved via depth sorting. An algorithm is also given for finding the Delaunay triangulation. In addition, the author does a nice job of showing how to use plane-sweep algorithms for computational geometry problems in the plane. An interesting O((r + n)logn) time algorithm for finding the number r of pairs of n line segments in the plane that intersect. Voronoi diagrams are discussed also, which are extensively used in applications. The latter few chapters are more specialized than the rest of the book, and concentrate on divide and conquer algorithms and binary search trees.