Akl S.G., Lyons K.A. Parallel Computational Geometry

Prentice Hall, 1993. — 220 p.This book reviews contributions made to the field of parallel computational geometry since its inception about a decade ago. Parallel algorithms are presented for each problem, or family of problems, in computational geometry. The models of parallel computation used to develop these algorithms cover a very wide range, and include the parallel random access machine (PRAM) as well as several networks for interconnecting processors on a parallel computer. Current trends and future directions for research in this field are also identified. Each chapter concludes with a set of problems and a list of references.
The book is addressed to graduate students in computer science, engineering, and mathematics, as well as to practitioners and researchers in these disciplines. We assume the reader to be generally familiar with the concepts of algorithm design and analysis, computational geometry, and parallelism.Models of Parallel Computation.
Convex Hull.
Intersection Problems.
Geometric Searching.
Visibility and Separability.
Nearest Neighbors.
Voronoi Diagrams.
Geometric Optimization.
Triangulation of Polygons and Point Sets.
Current Trends.
Future Directions.