A Parallel Algorithm for Computing Polygon Set Operations

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²n²) processors and a time complexity of O(max(2log m, log²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²n²) and time complexity of O(log m) and O(2log m, log n) 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, taking advantage of the topological structure of the two polygons. We believe this will result in better performance on the average as compared to the worst case. Though all the algorithms presented here are deterministic, randomized algorithms such as sample sort can be used for the sorting subcomponent of the algorithms to obtain fast practical implementations.