Parallelizing and algorithm for visibility on polyhedral terrain

The best known output-sensitive sequential algorithm for computing the viewshedon a polyhedral terrain from a given viewpoint was proposed by Katz, Overmars, and
Sharir 10, and achieves time complexity O((k + n(n)) logn) where n and k are the
input and output sizes respectively, and () is the inverse Ackermann's function. In
this paper, we present a parallel algorithm that is based on the work mentioned above,
and achieves O(log2
n) time complexity, with work complexity O((k +n(n)) logn) in a
CREW PRAM model. This improves on previous parallel complexity while maintaining
work e ciency with respect to the best sequential complexity known.