OPTIMAL PARALLEL HYPERCUBE ALGORITHMS FOR POLYGON PROBLEMS

We present parallel techniques on hypercubes for solving optimally a c lass of polygon problems. We thus obtain optimal O(log n)-time, n-proc essor hypercube algorithms for the problems of computing the portions of an n-vertex simple polygonal chain C that are visible from a given source point, computing the convex hull of C, testing an n-vertex simp le polygon P for monotonicity, and other related problems as well, pre viously it was not known how to achieve these complexity bounds on hyp ercubes, one of the main difficulties being that there is no known opt imal sorting hypercube algorithm that achieves these bounds. In fact t hese are the first optimal geometric hypercube algorithms that do not assume that the input is given already sorted by x or y coordinates. T he hypercube model we use is the standard one, with O(1) local memory per processor, and with one-port communication.