Parallel algorithm for segment visibility reporting (Q688184)

We present a parallel algorithm for solving the all-pairs vertical segment visibility reporting (SVR) problem. Given a set \(S=\{S_ 0,S_ 1,\ldots,S_{n-1}\}\) of disjoint vertical segments in the plane, the SVR problem asks for the determination and reporting of all the distinct 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 (Exclusive Read Exclusive Write Parallel Random Access Machine) computational model.