In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms:- An O( {Mathematical expression}time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in an N-vertex polygon, possibly with holes. -O( {Mathematical expression}) time algorithms for computing on a Mesh-of-Processors of size N the set of all points on the boundary of an N-vertex polygon P which are visible in a given direction d as well as the visibility hull of P for a given direction d. - An O( {Mathematical expression}) time algorithm for detecting on a Mesh-of-Processors of size 2 N whether two N-vertex polygons are separable in a given direction and an O( {Mathematical expression}) time algorithm for detecting on a Mesh-of-Processors of size MN whether M N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.

Additional Metadata
Keywords Computational geometry, Mesh-of-Processors, Parallel algorithms, Separability-Visibility
Persistent URL dx.doi.org/10.1007/BF01901193
Journal The Visual Computer
Citation
Dehne, F. (1988). Solving visibility and separability problems on a mesh-of-processors. The Visual Computer, 3(6), 356–370. doi:10.1007/BF01901193