Excerpt from Parallel Computational Geometry
Computational geometry addresses algorithmic problems in diverse areas such as VLSI design, robotics, and computer graphics. Since 1975 there has been a wide development of sequential algorithms for geometric problems, but until 1985 there was little published about developing parallel algorithms for such problems. A notable exception was the Ph.D. research of Anita Chow (1980) which seems to have been the pioneering work in the field but unfortunately only a portion of it has appeared in the open literature.
This paper contributes some parallel algorithms for solving geometric problems:
(1) Convex hulls in two and three dimensions
(2) Voronoi diagrams and proximity problems
(3) Detecting segment intersections and triangulating a polygon
(4) Polygon optimization problems
(5) Creating data structures in two and three dimensions to answer some standard queries.
It is seldom obvious how to generate parallel algorithms in this area since popular techniques such as contour tracing, plane sweeping, or gift wrapping involve an explicitly sequential (iterative) approach (see [Preparata and Shamos (1985)] for more details). In this paper we exploit data-structures that are simple enough to compute efficiently in parallel while being powerful enough to answer queries efficiently. However, the queries may be answered slightly less efficiently than would be possible if the data-structures were constructed sequentially. 'Efficient' here means polylogarithmic in parallel time.
All the algorithms presented here will be NC-algorithms, i.e., algorithms executable in polylog depth on polynomial-size circuits. We caution that the circuits here are slightly different from those used in machine-based complexity theory in that each node of our circuit can compute an infinite precision arithmetic operation. Furthermore these algorithms shall all be described as if they were implemented on a CREW PRAM - a concurrent-read, exclusive-write parallel random access machine. Such a machine is conceived as having a large number of processors with common access to a common memory. Any number of processors can read the same memory cell simultaneously in 0(1) steps, and any processor can write to a memory cell in 0(1) steps, but if two processors attempt to write to the same cell simultaneously then the machine enters an undefined state.
We should mention here that Anita Chow's dissertation pays close attention to the model of computation involved, and in several cases she provides algorithms for implementation on two models of parallel computation: the CREW PRAM model, and the cube-connected cycles (CCC) network. As mentioned before, in the CREW model, all the processors share the same memory; however, in the CCC network, each processor has its own memory, and is connected to at most four other processors. For details on the CCC model, see [Chow (1980)].
It follows from [Kozen and Yap (1985)] that most common computational geometry problems including all the problems considered in this paper have, in principle, NC-algorithms. Recall that they combined the techniques of [Ben-Or, Kozen and Reif (1984)] and [Collins (1975)] to give parallel algorithms for computing cell decompositions with adjacency information; for fixed dimensions, these algorithms are in NC.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com Это и многое другое вы найдете в книге Parallel Computational Geometry (Classic Reprint)