A parallel algorithm for computing polygon set operations
Raghu R. Karinthi, K. Srinivas, George S. Almasi · 2002
We present a parallel algorithm for performing Boolean set operations on generalized polygons that have holes in them. The intersection algorithm has a processor complexity of O(m/sup 2/n/sup 2/) processors and a time complexity of O(max(2logm, log/sup 2/n)), where m is the maximum number of vertices in any loop of a polygon, and n is the maximum number of loops per polygon. The union and difference algorithms have a processor complexity of O(m/sup 2/n/sup 2/) and time complexity of O(logm) and O(2logm, logn) respectively. The algorithm is based on the EREW PRAM model. The algorithm tries to minimize the intersection point computations by intersecting only a subset of loops of the polygons based on of their topological relationships.>