Solving visibility problems on BSR model of parallel computation

Robert A. Melter; Ivan Stojmenovic

doi:10.1117/12.198614

4 January 1995 Solving visibility problems on BSR model of parallel computation

Robert A. Melter, Ivan Stojmenovic

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.

Citation Download Citation

Robert A. Melter and Ivan Stojmenovic "Solving visibility problems on BSR model of parallel computation", Proc. SPIE 2356, Vision Geometry III, (4 January 1995); https://doi.org/10.1117/12.198614

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available