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