An efficient VLSI architecture for digital geometry

The main contribution of this work is to show that a number of fundamental digital geometry tasks can be solved fast on a novel VLSI architecture obtained by augmenting the mesh with multiple broadcast architecture (MMB) with precharged 1-bit row and column buses. The new architecture that we call mesh with hybrid buses (MHB) is readily implementable in VLSI with no increase in the area or the wiring complexity of the MMB chip. More importantly, the new architecture affords us an exponential gain in the running time when compared with the MMB. Specifically, with a digital image pretiled onto an MHB of size √n×√n one pixel per processor we show that the problems of computing the convex hull of the image, computing the diameter and the width of the image, deciding whether two images are linearly separable, computing several moments and low-level descriptors of the image including the perimeter, area, center, and median row of its convex hull can be solved in O(log n) time. The fastest possible algorithms for the problems above on the MMB run in Θ(n^1/6 )