Consider a n×n 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(log n) time SIMD algorithms for each of these two problems on the hypercube, where one 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 that both of the above algorithms are asymptotically optimal.

, , ,
International Journal of Parallel Programming
School of Computer Science

Dehne, F, Pham, Q.T. (Quoc T.), & Stojmenović, I. (Ivan). (1990). Optimal visibility algorithms for binary images on the hypercube. International Journal of Parallel Programming, 19(3), 213–224. doi:10.1007/BF01407955