4 January 1995 Solving visibility problems on BSR model of parallel computation
Author Affiliations +
Proceedings Volume 2356, Vision Geometry III; (1995) https://doi.org/10.1117/12.198614
Event: Photonics for Industrial Applications, 1994, Boston, MA, United States
Abstract
Broadcasting with selective reduction (BSR) is a model of parallel computation introduced by Akl, Guenther, and Lindon. The model is more powerful than any of the PRAM models, yet one and two criteria BSR do not require more hardware (up to a constant factor) to implement than PRAM. Besides power, the model provides the ability to write very short solutions to a variety of problems. For many problems BSR offers constant time solutions which were not possible to achieve with any PRAM. In this paper we apply BSR to solve, in constant time and with optimal O(n) number of processors (where n is the input size), several visibility problems. The parallel and point visibility problems of a set of n parallel line segments or n iso-oriented rectangles or n disks in the plane are solved on a two criteria BSR. The problem of constructing the dominance graph of a set of n iso-oriented rectangles is solved using a three criteria BSR.
© (1995) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Robert A. Melter, Ivan Stojmenovic, "Solving visibility problems on BSR model of parallel computation", Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198614; https://doi.org/10.1117/12.198614
PROCEEDINGS
8 PAGES


SHARE
KEYWORDS
Back to Top