**
Second Edition:
**
printed 28 September 1998.
Purchasing information:

- Hardback: ISBN 0521640105, $69.95 (55.00 PST)
- Paperback: ISBN 0521649765, $29.95 (19.95 PST)

Contents:

Some highlights:- 376+xiii pages, 270 exercises, 210 figures, 259 references.
- Although I've retained the title
*...in C*, all code has been translated to Java, and both C and Java code is available free. - Java Applet to permit interactive use of the code: CompGeom Java Applet
- First Edition code improved: Postscript output, more efficient, more robust.
- New code (see below).
- Expanded coverage of randomized algorithms, ray-triangle intersection, and other topics (see below).

- approx. 50 pages longer
- 31 new figures.
- 49 new exercises.
- 74 new references
- 4 new programs.

- To compute the Delaunay triangulation from the 3D hull in O(n^2).
- To intersect a ray with a triangle.
- To decide if a point is inside a polyhedron.
- To compute the convolution (Minkowski sum) of a convex polygon with a general polygon.
- To generate regularly distributed points on the surface of a sphere (see Figure above).

- Triangulation code now O(n^2) rather than n^3. Uses lists rather than arrays.
- Graham scan handles collinear points more cleanly.
- Convex hull in 3D starts with double-covered triangle. Volume determinant computations much faster. Overflow handled better.
- Segment-segment intersection code handles special cases cleanly.
- Point-in-polygon code classifies all boundary points correctly.
- Intersection of convex polygons handles special cases more uniformly.
- Robot arm configuration more robust.

- Partition into monotone mountains (for triangulation).
- Randomized trapezoid decomposition.
- Randomized triangulation.
- The ultimate convex hull algorithm.
- Randomized 3D hull construction.
- Twin edge data structure.
- Furthest-point Voronoi diagram figure.
- Red-blue matching.
- Intersection of segment and triangle.
- Point-in-polyhedron.
- The Bentley-Ottmann algorithm for intersecting segments.
- Boolean operations between two polygons.
- Segment search tree.
- Sources and further reading: annotated bibliography.

More extensive (but still partial) solutions manual available. Write me at orourke@cs.smith.edu.

**Errata (in 2nd Edition)**:

- Top 10 Geometry Algorithm Books
- Miriam L. Lucian, SIAM Review, Vol. 42, No. 2, June 2000, pp. 335-339.
- R. Goldberg, Computing Reviews, [9906-0411] June 1999, p.284.
- H.-D. Hecker, Mathematical Reviews, MR 99k:68198 (1999).
- Michael Dekhtyar, SIGACT News, Vol. 30, no. 3 (Issue 112) Sep. 1999, 8-13.
- Dave Jewell, Developers Review, Vol. 11, Aug. 1999.
- S. Stifter, Zentralblatt fu:r Mathematik, Vol. 912, 1999.
- Carsten Whimster, The Codesmith's Library.
- Graham Kendall, Association of C and C++ Users.
- Brian Hook, 3D Graphics Book List.
- Three reader reviews at amazon.com: Lee Carlson, Pete Gonzalez, Bob Williamson.

First Edition

Last Update to this page: