Book Announcement: Computational Geometry in C (2nd Ed.)

[Joseph O'Rourke]

COMPUTATIONAL GEOMETRY IN C (SECOND EDITION)
Joseph O'Rourke
Cambridge University Press.

Printed 28 September 1998; shipping as of 2 October 1998.
Hardback:  ISBN 0521640105, $69.95 (55.00 PST)
Paperback: ISBN 0521649765, $29.95 (19.95 PST)

Some highlights:
1. 376+xiii pages, 270 exercises, 210 figures, 259 references.
2. Although I've retained the title "...in C," all code
   has been translated to Java, and both C and Java code is available 
   via links from http://cs.smith.edu/~orourke.
3. A Java Applet permits interactive use of the code.  See previous URL.
4. First Edition code improved:  Postscript output, more efficient,
   more robust.
5. New code (see below).
6. Expanded coverage of randomized algorithms, ray-triangle intersection,
   and other topics (see below).

Basic statistics:
1.  approx. 50 pages longer
2.  31 new figures.
3.  49 new exercises.
4.  74 new references
5.   4 new programs.

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

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

New coverage of these topics:
1.  Partition into monotone mountains (for triangulation).
2.  Randomized trapezoid decomoposition.
3.  Randomized triangulation.
4.  The ultimate convex hull algorithm.
5.  Randomized 3D hull construction.
6.  Twin edge data structure.
7.  Furthest-point Voronoi diagram figure.
8.  Red-blue matching.
9.  Intersection of segment and triangle.
10. Point-in-polyhedron.
11. The Bentley-Ottmann algorithm for intersecting segments.
12. Boolean operations between two polygons.
13. Segment search tree.
14. Sources and further reading: annotated bibliography.


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme