This is the first year of a 3-year continuing award. The research consists of the design, analysis, and implementation of efficient algorithms and paradigms to solve problems in image analysis and computational geometry on massively parallel computers. The focus of the algorithm development will be on fine-grained distributed memory topologies for which commercially available machines or prototypes already exit. These include the mesh, hypercube, pyramid, and reconfigurable mesh. The concentration will be on problems with application to robotics and image processing. Initially, the following will be considered: 2-and 3-dimensional problems in intermediate-level image analysis, as well as 2- and 3-dimensional problems in computational geometry. The optimality of all of the problems considered ar currently open problems on the appropriate architectures. Further, it does not appear that for the problems considered, algorithms for 2-dimensional objects can be extended to solve the problems for 3-dimensional objects in optimal time. Rather, it appears that radically different approaches will be required. The problems considered involve connectivity, proximity, area, intersection, and minimal-area enclosing polygons, to name a few.
