0 (Logn) Parallel Time Intersection and Union Algorithms for a Set of Planar Disc (Classic Reprint) - Softcover

Inhaltsangabe

Efficient parallel methods for computing boundaries of unions and intersections. This book explains how to determine the boundary shape created when many circular discs in the plane overlap, using parallel algorithms that run in polylog time.

The text presents a concrete characterization of the boundary, along with time and processor counts for both CREW and CRCW PRAM models. It shows how to compute all boundary arcs quickly and how to walk along the resulting contour. The work also analyzes how many boundary arcs can appear and proves results about the structure of the intersection and union of large sets of discs. Readers will find a blend of geometric insight, formal definitions, and parallel algorithm design that demonstrates the practical potential of parallel time theory for planar geometry.

• How to represent disc boundaries and related arcs in a precise, computable way.


• Parallel procedures to identify key points on boundaries and to assemble the overall contour of intersection and union.


• Analysis of time complexity and processor requirements on CREW and CRCW PRAM models.


• Theoretical bounds on the number of boundary arcs and implications for optimality.

Ideal for readers who want to understand fast parallel solutions to geometric problems and their practical implications in computational geometry.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.