## The Codesmith's Library

### Computational Geometry in C, 2nd Edition

Written by Carsten Whimster

## Computational Geometry in C, 2nd Edition

I first heard the announcement of this book on the newsgroup comp.graphics.algorithms, and after contacting the author, a copy arrived at my door very quickly. Here are the chapters:

```
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
Bibliography
Index
```

Some topics are easy; some are hard. Most authors can make easy topics seem easy, but it takes a very good author to make a tricky subject seem easy. I have not taken any geometry courses, but reading through this book, the proofs are thoroughly convincing and the exercises range from trivial to impossible. Well, almost. Some of the exercises are actually open questions, and are marked as such, ie. no one yet knows the answer.

The basic format of the book is quite simple: introduce the area being discussed, motivate the material with some applications, and then dive into the material itself. Usually proofs are presented, although some are left as exercises to the reader. Often code is presented (the complete code is supposedly at the web site for the book,) but not always. Lots of clear diagrams accompany the text as well.

Search and Intersection is a chapter with many little gems, loosely related, from segment-segment intersection, through point in triangle, and point in polygon routines, to extreme points, and more.

In case you are wondering from the title, Motion Planning deals with the topic of planning a path through a series of obstacles, for example by a robot. As such, it outlines the various methods for determining path width and so on for objects of non-zero dimensions. Perhaps this is the technical term for this material, but by chance I have not heard of it before.

This book is outstanding. There is no question about that. It is obvious from the beginning that the author is in love with the material he is covering, and judging by the number of papers on important topics that the author himself wrote, he is deeply immersed in his field at a professional level. In addition to research and teaching, Joseph O'Rourke is the comp.graphics.algorithms FAQ maintainer.

Several other reviewers are professors and lecturers at other universitites, and it is obvious from the comments that this book is well suited to teaching an undergraduate course. It might be a touch too hands-on for a graduate level course, but with the hard exercises included, it might not be a bad fit at that level after all.

The source and bibliography are very thorough, listing 14 pages of books, papers, and other related materials, including a couple of web sites. I never needed the index, but it looks of the same quality as the rest of the book.

## Summary

If you need to understand the theory behind some of the more common and frequently coded graphics algorithms, such as those for polygon partitioning, convex hulls, Voronoi diagram determination and more, then this book is your tool. Clearly written, thorough, interesting, and well illustrated, I have rarely seen a book of this caliber. My main regret is that the publisher did not give it a hardcover binding. This book will remain handy on my closest shelf until a better one is written, and when this happens, I fully expect it to be written by Joseph O'Rourke.

I give it 10/10, without hesitation.

Computational Geometry in C, Joseph O'Rourke

• Cambridge University Press, ISBN 0-521-64976-5, (price unmarked)
• Intended audience: All Graphics Programmers
• Mark: 10/10

## Reviewed Books

Our Bookstore has reviews and links to Amazon for all books we have reviewed in the past, as well as several books waiting to be reviewed, and others which we recommend.