The Mesh with Hybrid Buses: An Efficient Parallel Architecture for Digital Geometry

The first main contribution of this work is to propose an efficient VLSI architecture obtained by augmenting the Mesh with Multiple Broadcasting (MMB) with precharged 1-bit row and column buses. The new architecture that we call Mesh with Hybrid Buses (MHB, for short) is realizable in VLSI with no increase in the area or the wiring complexity of the MMB chip. Our second main contribution is to show that the MHB is extremely well suited for solving an entire slew of digital geometry tasks. The MHB is not a reconfigurable architecture. Yet, quite remarkably, for a large number of fundamental digital geometry tasks, the MHB offers a level of performance previously attained only by reconfigurable architectures. Specifically, with a digital image pretiled onto a MHB of size p n \Theta p 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 a set of digital points is a digital li..