PARALLEL ALGORITHM FOR SEGMENT VISIBILITY REPORTING

Authors
CHAN IW FRIESEN DK
Citation
Iw. Chan et Dk. Friesen, PARALLEL ALGORITHM FOR SEGMENT VISIBILITY REPORTING, Parallel computing, 19(9), 1993, pp. 973-978
Citations number
3
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
Parallel computing → ACNP
ISSN journal
01678191
Volume
19
Issue
9
Year of publication
1993
Pages
973 - 978
Database
ISI
SICI code
0167-8191(1993)19:9<973:PAFSVR>2.0.ZU;2-N
Abstract
In this paper, we present a parallel algorithm for solving the all-pai rs vertical segment visibility reporting (SVR) problem. Given a set S = {S0, S1,...,S(n-1)} of disjoint vertical segments in the plane, the SVR problem asks for the determination and reporting of all the distin ct visibility pairs. Our algorithm solves the SVR problem in O(log n) time using O(n log n) space and O(n) processors on an EREW PRAM (Exclu sive Read Exclusive Write Parallel Random Access Machine) computationa l model.