TR-136: Optimal Visibility Algorithms for Binary Images on the Hypercube

Abstract

Consider a nxn binary image. Given a direction D, the parallel visibility
problem consists of determining for each pixel of the image the portion that is visible
(i.e., not obstructed by any other black pixel of the image) in direction D from infinity. A related problem, referred to as point visibility, is to compute for each pixel the
portion that is visible from a given point p.
In this paper, we derive O(logn) time SIMD algorithms for each of these two
problems on the hypercube where a processor is assigned to every pixel of the image. Since the worst case communication distance of two processors in a n2-processor hypercube is 2 log n, it follows thqt both of the above algorithms are asymptotically optimal.