文档介绍：Implementing these basic routines in a robust manner is not easy, and takes a PREFACE
lot of time. Although it is good to do this at least once, it is useful to have
a software library available that contains the basic data types and routines.
Pointers to such libraries can be found on our World Wide Web site.
World Wide Web. This book is panied by a World Wide Web site,
which provides lots of additional material, like an addendum, pointers to geo-
metric software and to an online literature database containing close to 10,000
papers written putational geometry, and links to other sites that contain
information putational geometry. The address is
You can also use our d us errors you found and any other
comments you have about the book.
About the second edition. This second edition is largely the same as the first
edition; most changes are corrections of small errors. In principle it is possi-
ble for students in a course to still use the first edition. In that case, however,
you should be aware of the following changes. First of all, we went carefully
over all the exercises, reformulating or removing some old ones and adding
a number of new ones. Secondly, larger revisions have occured in Chapter 4
(where the treatment of unbounded linear programs is different) and in Chap-
ter 7 (where several details in the algorithm have changed).
Acknowledgements. Writing a textbook is a long process, even with four
authors. Over the past years many people helped us by providing useful ad-
vice on what to put in the book and what not, by reading chapters and sug-
gesting changes, and by finding and correcting errors. In particular we would
like to thank Pankaj Agarwal, Helmut Alt, Marshall Bern, Jit Bose, Hazel Ev-
erett, Gerald Farin, Steve Fortune, Geert-Jan Giezeman, Mordecai Colin, Dan
Halperin, Richard Karp, Matthew Katz, Klara Kedem, Nelson Max, Renk van
Oostrum, Henry Shapiro, Sven Skyum, Jack Snoeyink, Gert Vegter, Pet