The best known output-sensitive sequential algorithm for computing the viewshed on a polyhedral terrain from a. given viewpoint was proposed by Katz, Overmars, and Sharir,10 and achieves tune complexity O((κ + nα(n))logn) where n and κ 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 ((κ + nα(n)) log n) in a CREW PRAM model. This improves on previous parallel complexity while maintaining work efficiency with respect to the best sequential complexity known.
Parallelizing an algorithm for visibility on polyhedral terrain
Puppo E.;
1997-01-01
Abstract
The best known output-sensitive sequential algorithm for computing the viewshed on a polyhedral terrain from a. given viewpoint was proposed by Katz, Overmars, and Sharir,10 and achieves tune complexity O((κ + nα(n))logn) where n and κ 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 ((κ + nα(n)) log n) in a CREW PRAM model. This improves on previous parallel complexity while maintaining work efficiency with respect to the best sequential complexity known.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
