Solving visibility problems on MCC's Conference Paper uri icon

abstract

  • 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 are presented. For a collection of n such objects, the algorithms show how to compute, on a √n × √n MCC, a view of these objects in O(√n) time. Both parallel and perspective view are considered. The previous algorithms for computing the views are sequential and have O(nlog n) time complexity. For the above tasks, methods to solve problems of size n on MCCs with p processors, where p < n, are also described. The time complexity and the limitations imposed by the computational and communication requirements are analyzed.

author list (cited authors)

  • Lu, M.

publication date

  • December 1988