CONSTANT-TIME CONVEXITY PROBLEMS ON RECONFIGURABLE MESHES

The purpose of this paper is to demonstrate that the versatility of th e reconfigurable mesh can be exploited to devise constant-time algorit hms for a number of important computational tasks relevant to robotics , computer graphics, image processing, and computer vision. In all our algorithms, we assume that one or two n-vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size root n x root n. In this setup, we propose constant-time solutions fo r testing an arbitrary polygon for convexity, solving the point locati on problem, solving the supporting lines problem, solving the stabbing problem, determining the minimum area/perimeter corner triangle for a convex polygon, determining the k-maximal vertices of a restricted cl ass of convex polygons, constructing the common tangents of two separa ble convex polygons, deciding whether two convex polygons intersect, a nswering queries concerning two convex polygons, and computing the sma llest distance between the boundaries of two convex polygons. To the b est of our knowledge, this is the first time that O(1) time algorithms to solve dense instances of these problems are proposed on reconfigur able meshes. (C) 1995 Academic Press, Inc.