Parallel Algorithms for Image Analysis, Computational Geometry and Graphs

本研究包括在并行计算机上设计、分析和实现有效的算法和范例，以解决图像分析、计算几何和图论中的问题。该算法将针对以下类型的问题：(1)对于网格：计算几何，包括动态和静态问题；(2)对于金字塔：由派生度量定义的受限图片；(3)树形网格和超立方体：基本的数据移动操作，应用于图像分析、计算几何和图论；此外，还将开发一种映射，允许金字塔算法在树网格上有效运行；(4)对于具有可重构总线的网格：基本数据移动操作、图像分析和图论；此外，还将演示该模型结合了许多其他体系结构的优点；(5)并行随机存取机：动态计算几何。解决图像分析和计算几何问题的算法将在超立方体多处理器上实现，我们将专注于高级数据缩减技术和执行数据缩减时出现的负载平衡问题。

This research consists of the design, analysis, and implementation of efficient algorithms and paradigms for the solution of problems in image analysis, computational geometry, and graph theory on parallel computers. The algorithms will be aimed at the following types of problems: (1) for the mesh: computational geometry, including dynamic as well as static problems; (2) for the pyramid: restricted pictures which are defined by derived metrics; (3) for the mesh-of-trees and hypercube: fundamental data-movement operations, with application to image analysis, computational geometry, and graph theory; also, a mapping will be developed that will allow pyramid algorithms to run efficiently on a mesh-of-trees; (4) for the mesh with a reconfigurable bus: fundamental data-movement operations, image analysis, and graph theory; also, a demonstration will be provided that this model combines the advantages of a number of other architectures; and (5) for the parallel random access machine: dynamic computational geometry. Algorithms to solve problems in image analysis and computational geometry will be implemented on a hypercube multiprocessor, where we will concentrate on advanced data reduction techniques and load-balancing issues that arise when data reduction is performed.