Axioms and Hulls

by Donald E. Knuth (Heidelberg: Springer-Verlag, 1992), ix+109pp.
(Lecture Notes in Computer Science, no. 606.)
ISBN 3-540-55611-7
Chinese translation by Su Yunlin (Jiang Xi Science and Technology Press), in preparation.

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 (6992 bytes) or the errata file in DVI format (12932 bytes) or the errata file in compressed PostScript format (26320 bytes); the latter files were generated by the TeX file, and last updated on 05 May 2021.

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
Gates Building 1B
Stanford University
Stanford, CA 94305-9015 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

Valid HTML 4.01 Transitional