Computational geometry. An introduction. (English) Zbl 0575.68059

Preparata, Franco P.; Shamos, Michael Ian

Texts and Monographs in Computer Science. New York etc.: Springer-Verlag. XII, 390 p. DM 148.00 (1985).

Computational Geometry concerns with systematic study of geometric algorithms. The beauty of problems attracted many researchers and in the past decade computational geometry took a strong development. This book offers a panoramic view of computational geometry informing the reader about the basic concepts and algorithms. For each presented algorithm its time-complexity is evaluated. The contents of the book include geometric searching and retrieval, convex hull constructions and related problems, proximity, intersection, and the geometry of rectangles. The rigorous presentation of problems, the numerous examples, and the suggestive figures make the book accessible for a large number of readers.

Reviewer: D.Lucanu

MSC:

68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
68P10	Searching and sorting
05B25	Combinatorial aspects of finite geometries
68Q25	Analysis of algorithms and problem complexity
68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
05-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics

Keywords:

geometric algorithms; time-complexity; searching; convex hull; proximity; intersection; rectangles