Parallel Algorithms for Image Processing and Computational Geometry

这是为期3年的连续奖项的第一年。该研究包括在大规模并行计算机上设计、分析和实现有效的算法和范例来解决图像分析和计算几何中的问题。算法开发的重点将放在已有商用机器或原型的细粒度分布式存储器拓扑结构上。其中包括网格、超立方体、棱锥体和可重新配置网格。重点将放在机器人和图像处理的应用问题上。首先，将考虑以下内容：中级图像分析中的2维和3维问题，以及计算几何中的2维和3维问题。所考虑的所有问题的最优性是在适当的体系结构上当前尚未解决的问题。此外，对于所考虑的问题，似乎不能将用于2维对象的算法扩展到在最佳时间内解决用于3维对象的问题。相反，似乎将需要截然不同的方法。所考虑的问题涉及连通性、邻近性、面积、交集和包围多边形的最小面积，仅举几例。

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.