Solving city block metric and digital geometry problems on the BSR model of parallel computation
Robert Alan Melter, Ivan Stojmenović · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
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).