Optimal parallel hull construction for simple polygons in O(log log n) time
Hubert Wagener · 1992
The author proposes an optimal parallel algorithm for computing the convex hull of a simple polygon. The algorithm achieves a runtime of O(log log n) using O(n/log log n) processors of a CRCW-PRAM. The data structure representing the convex hull is not the standard one, i.e. an array storing the vertices of the hull in clockwise order. Indeed, a lower bound of Omega (log n/log log n) on the runtime for any algorithm employing a polynomial number of processors and computing the array-representation is known. Nevertheless, the representation is adequate for further parallel processing; standard queries like computing the intersection of the hull with a given line, etc., can be answered in time O(log n/(log p+1)+1) using p processors. In addition subchain hull queries are supported optimally in time O(log k/(log p+1)+1), where k is the length of the subchain. The algorithm can easily be adapted to other hull-like structures for simple polygons; as e.g. the orthogonal hull, and the visibility region from a point under various definitions of visibility.>