Constant-time convex polygon algorithms on reconfigurable meshes
Stephan Olariu, Jim L. Schwing, Jinming Zhang · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
In an attempt to overcome the inefficiency of handling data transfer operations over long distances, mesh-connected computers have recently been augmented by the addition of various types of bus systems. One of the most efficient such augmented computer systems is referred to as the reconfigurable mesh, that is, a mesh-connected computer overlaid with a reconfigurable bus system. In this paper we propose constant-time algorithms on reconfigurable meshes for a number of important computational geometry tasks relevant to computer vision. These include testing an arbitrary polygon for convexity, computing the union and intersection of two convex polygons, testing whether two convex polygons are separable and, if so, constructing a separating line, solving the polygon containment problem for convex polygons, and others. Our solutions rely on a recently developed VLSI-optimal sorting algorithm for reconfigurable meshes and on a number of novel data movement techniques. The proposed algorithms translate immediately into constant-time algorithms that work on binary images.