Share Email Print

Proceedings Paper

Solving visibility problems on BSR model of parallel computation
Author(s): Robert A. Melter; Ivan Stojmenovic
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 4 January 1995
PDF: 8 pages
Proc. SPIE 2356, Vision Geometry III, (4 January 1995); doi: 10.1117/12.198614
Show Author Affiliations
Robert A. Melter, Long Island Univ. (United States)
Ivan Stojmenovic, Univ. of Ottawa (Canada)

Published in SPIE Proceedings Vol. 2356:
Vision Geometry III
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top