Parallelizing and algorithm for visibility on polyhedral terrain

TitleParallelizing and algorithm for visibility on polyhedral terrain
Publication TypeJournal Articles
Year of Publication1997
AuthorsTeng YA, Mount D, Puppo E, Davis LS
JournalInternational Journal of Computational Geometry and Applications
Volume7
Issue1/2
Pagination75 - 84
Date Published1997///
Abstract

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.