Axioms and Hulls

Presents efficient algorithms for finding convex hulls and Delaunay triangulations in generalizations of Euclidean space called CC systems (``counter clockwise systems'') and CCC systems. The underlying theme is a philosophy of algorithm design based on simple primitive operations that satisfy clear and concise axioms. Chapter 15, ``Parsimonious algorithms,'' is of independent interest.

Available from the publisher, Springer Verlag, Inc.. An electronic version of the text (but not all the illustrations) can also be downloaded as a compressed plain TeX file. You can also download all the programs I wrote for this book.

Errata

For a list of corrections to known errors in this book, you may download either the errata file in plain TeX format (9450 bytes) or the errata file in DVI format (16096 bytes) or the errata file in compressed PostScript format (31509 bytes); the latter files were generated by the TeX file, and last updated on 01 March 2025.

With these corrections, I hope the book is now error-free. But (sigh) it probably isn't. Therefore I will gratefully deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to

Prof. D. Knuth
Computer Science Department
CoDa Building room W208
389 Jane Stanford Way
Stanford University
Stanford, CA 94305-5008 USA.

I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Don Knuth's home page

Don Knuth's other books