Cover image for Computational geometry in C
Computational geometry in C
O'Rourke, Joseph.
Personal Author:
Second edition.
Publication Information:
Cambridge, UK, ; New York, NY, USA : Cambridge University Press, 1998.
Physical Description:
xiii, 376 pages : illustrations ; 26 cm

Format :


Call Number
Material Type
Home Location
Item Holds
QA448.D38 O76 1998 Adult Non-Fiction Central Closed Stacks-Non circulating

On Order



This is the revised and expanded 1998 edition of a popular introduction to the design and implementation of geometry algorithms arising in areas such as computer graphics, robotics, and engineering design. The basic techniques used in computational geometry are all covered: polygon triangulations, convex hulls, Voronoi diagrams, arrangements, geometric searching, and motion planning. The self-contained treatment presumes only an elementary knowledge of mathematics, but reaches topics on the frontier of current research, making it a useful reference for practitioners at all levels. The second edition contains material on several new topics, such as randomized algorithms for polygon triangulation, planar point location, 3D convex hull construction, intersection algorithms for ray-segment and ray-triangle, and point-in-polyhedron. The code in this edition is significantly improved from the first edition (more efficient and more robust), and four new routines are included. Java versions for this new edition are also available. All code is accessible from the book's Web site ( or by anonymous ftp.

Reviews 1

Choice Review

Discrete geometry is a relatively modern discipline with roots in antiquity. It has received much attention recently because of its utility in computer imaging and a wide range of computer-oriented applications. This modern orientation was named "computational geometry" by Shamos in his 1978 thesis. O'Rourke has written a fine introduction to computational geometry; he balances the foundational mathematical problems, the various algorithms yielding solutions to those problems, and C programs that implement the algorithms and more concrete applications like robotics and animation. There is a good discussion of data structures useful in storing and utilizing geometric information. The reader should have a working knowledge of C in order to best follow the examples. Among the basic topics covered are triangulations, convex hulls, Voronoi diagrams and their dual, the Delaunay triangulation. The book states that the C programs are available from the author's homepage . Java versions of the programs may also be found there. A working knowledge of C is needed to follow the Internet material also. Otherwise, the book is highly recommended. Upper-division undergraduates and up. W. Abikoff University of Connecticut

Table of Contents

1 Polygon triangulation
2 Polygon partitioning
3 Convex hulls in two dimensions
4 Convex hulls in three dimensions
5 Voronoi diagrams
6 Arrangements
7 Search and intersection
8 Motion planning
9 Sources