# Computational Geometry in C (Second Edition)

by Joseph O'Rourke

Second Edition: printed 28 September 1998. Purchasing information:

• Hardback: ISBN 0521640105, \$69.95 (55.00 PST)
• Paperback: ISBN 0521649765, \$29.95 (19.95 PST)
Cambridge University Press servers: in Cambridge; in New York; Cambridge (NY) catalog entry (includes jacket text and chapter titles). Also amazon.com.

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).
Basic statistics (in comparison to First Edition):
• approx. 50 pages longer
• 31 new figures.
• 49 new exercises.
• 74 new references
• 4 new programs.
New code:
• 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).
Significant code improvements:
• 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.
New coverage of these topics:
• 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):

Reviews (of 2nd Ed.):
• 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