SOLVING VISIBILITY PROBLEMS ON MCCS OF SMALLER SIZE

The paper presents mesh-connected computer (MCC) algorithms to solve the visibility problem for a set of disjoint simple objects such as line segments, circles, and simple polygons in the plane. Given a set of n such objects, the algorithms compute, on a n n MCC, a view of these objects in O( n) time. Both parallel and perspective views are considered. Earlier published algorithms for computing the views are sequential and have O(n log n) time complexity. Consider the solutions to solve problems of size n on MCCs with p processors, where p < n. An analysis is presented of the time performance and the limitations imposed by the computational and communication requirements, and the trade-offs between the size of the MCC and the time complexity that can be achieved. 1991.

Overview