Computational geometry. An introduction. (English) Zbl 0759.68037

Texts and Monographs in Computer Science. New York etc.: Springer-Verlag. XIV, 398 p. (1985).
This is the second printing (death-line in 1988) of a central and excellent book on computational geometry [first printing in 1985 by F. P. Preparata and M. I. Shamos, Text and monographs in computer science, New York, Springer-Verlag (1985; Zbl 0575.68059)]. Minor errors are corrected and additional comments are given. Also some new topics are discussed. Among others this are the following: The bridged chain method in geometric searching (optimal techniques), iterated search and fractional cascading, an expanded discussion of fractional cascading, and the linear-time construction of the Voronoi diagram of a convex polygon. In the meantime several other open questions have been solved, for instance optimal triangulation, so further work will be necessary to give an up-to-date third printing. Some new papers are added in the list of references.
Reviewer: H.-D.Hecker (Jena)


68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)


Zbl 0575.68059