Computational geometry algorithms for the systolic screen
A digitized plane Π of size M is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processor P ij represents pixel (i, j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called a systolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we present O(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem for n disjoint digitized images; and constructing the Voronoi diagram of n planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., all L p metrics). These algorithms imply O(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.
|Keywords||Clustering, Computational geometry, Convex hull, Digitized pictures, Hulls, Maxima, Mesh-of-processors, Parallel computing, Separability, Systolic array, Visibility, Voronoi diagram|
Dehne, F, Hassenklover, A.-L., Sack, J.-R, & Santoro, N. (1991). Computational geometry algorithms for the systolic screen. Algorithmica, 6(1-6), 734–761. doi:10.1007/BF01759069