19881101
Solving visibility and separability problems on a meshofprocessors
Publication
Publication
The Visual Computer , Volume 3  Issue 6 p. 356 370
In this paper we study parallel algorithms for the MeshofProcessors 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 MeshofProcessors of size N the visibility polygon from a point located in an Nvertex polygon, possibly with holes. O( {Mathematical expression}) time algorithms for computing on a MeshofProcessors of size N the set of all points on the boundary of an Nvertex 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 MeshofProcessors of size 2 N whether two Nvertex polygons are separable in a given direction and an O( {Mathematical expression}) time algorithm for detecting on a MeshofProcessors of size MN whether M Nvertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the MeshofProcessors) with respect to time and number of processors.
Additional Metadata  

Computational geometry, MeshofProcessors, Parallel algorithms, SeparabilityVisibility  
dx.doi.org/10.1007/BF01901193  
The Visual Computer  
Organisation  School of Computer Science 
Dehne, F. (1988). Solving visibility and separability problems on a meshofprocessors. The Visual Computer, 3(6), 356–370. doi:10.1007/BF01901193
