TR-123: Solving Visibility and Separability Problems on a Mesh-of-Processors

Abstract

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility as well as related separability problems for sets of simple polygons in the plane; in particular, we solve the following problems:
( 1 ) compute for a point p inside a N-vertex simple polygon with holes the visibility polygon containing all points visible from p

( 2) for the parallel visibility model (visibility from a point with infinite distance) compute the portion of a N-vertex simple polygon visible in a given direction d and the visibility hull with respect to direction d

(3) determine whether two N-vertex simple polygons are separable (without collision) by a single translation in a given direction d

( 4 ) determine for a set of M N-vertex simple polygons whether they are sequentially separable in a given direction d, i.e. whether there exists a sequence of translations in direction d, one for each polygon, which allows to separate them without collisions between polygons.

The parallel algorithms presented in this paper have an asymptotically optimal time complexity of O(–IN) for problems 1-3 and O(✓M N) for problem 4, respectively, and require a linear number of processing elements ..