The focus of this research is on the design, analysis, and implementation of efficient algorithms and paradigms to solve problems in image analysis and computational geometry on parallel computers. Specifically, algorithms are considered for a scalable model of computation that provides a reliable metric in terms of a comparison of running times between algorithms on commercially available medium-grained parallel machines. The algorithms typically combine efficient parallel data movement operations, paradigms, and data reduction techniques, with efficient sequential algorithms. The concentration is on problems with applications to robotics and image processing, including those involving connectivity, convexity, proximity, area, intersection, and minimal-area enclosing polygons, to name a few. The experimental component of the research includes the porting, optimization, and evaluation of a large system designed to solve an important problem in x-ray crystallography, over a wide variety of multiprocessor platforms.
