Solving city block metric and digital geometry problems on the BSR model of parallel computation

Robert A. Melter; Ivan Stojmenovic

doi:10.1117/12.165010

1 December 1993 Solving city block metric and digital geometry problems on the BSR model of parallel computation

Robert A. Melter, Ivan Stojmenovic

Proceedings Volume 2060, Vision Geometry II; (1993) https://doi.org/10.1117/12.165010
Event: Optical Tools for Manufacturing and Advanced Automation, 1993, Boston, MA, United States

Abstract

in this paper we solve several geometric and image problems using the BSR (broadcasting with selective reduction) model of parallel computation. All of the solutions presented are constant time algorithms. The computational geometry problems are based on city block distance metrics: all nearest neighbors and furthest pairs of m points in a plane are computed on a two criteria BSR with m processors, the all nearest foreign neighbors and the all furthest foreign pairs of m points in the plane problems are solved on three criteria BSR with m processors while the area and perimeter of m iso-oriented rectangles are found on a one criterion BSR with m² processors. The problems on an nxn binary image which are solved here all use BSR with n² processors and include: histogramming (one criterion), distance transform (one criterion), medial axis transform (three criteria) and discrete Voronoi diagram of labeled images (two criteria).

Citation Download Citation

Robert A. Melter and Ivan Stojmenovic "Solving city block metric and digital geometry problems on the BSR model of parallel computation", Proc. SPIE 2060, Vision Geometry II, (1 December 1993); https://doi.org/10.1117/12.165010

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