Share Email Print

Proceedings Paper

Solving city block metric and digital geometry problems on the 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

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 m2 processors. The problems on an nxn binary image which are solved here all use BSR with n2 processors and include: histogramming (one criterion), distance transform (one criterion), medial axis transform (three criteria) and discrete Voronoi diagram of labeled images (two criteria).

Paper Details

Date Published: 1 December 1993
PDF: 10 pages
Proc. SPIE 2060, Vision Geometry II, (1 December 1993); doi: 10.1117/12.165010
Show Author Affiliations
Robert A. Melter, Long Island Univ. (United States)
Ivan Stojmenovic, Univ. of Ottawa (Canada)

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

© SPIE. Terms of Use
Back to Top