Solutions to De Berg's Computational Geometry book exercises (2nd edition)

Solutions to De Berg's Computational Geometry book exercises (2nd edition)

Post by Alexander Gleyz » Sat, 19 Apr 2003 05:35:44


I'm a GIS software engineer developing custom algorithms.
I found this book very useful, but unfortunately it has no solutions
to the exercises. I'm doing the exercises, but I need to have the solutions,
so that I know if I'm in the right direction.

Does anyone know where I can find those?




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

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 " C," all code
   has been translated to Java, and both C and Java code is available
   via links from
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

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.

2. Bug in Alpha channel

3. GenesisVFX for LightWave 3D coming soon...

4. Mark De Berg's paper on ray shooting, depth orders, and HSR


6. Solutions to exercises from the book Into 2 algo by Cormen Leiserson et al [OT]

7. Becoming a computer animator

8. Call for Papers - 2nd CGC Workshop on Computational Geometry

9. Book Announcement: Handbook of Discrete & Computational Geometry

10. Request for computational geometry book review

11. Intro book on Computational Geometry

12. Books on Computational Geometry