9623585 Chen This project will study the design, analysis, and implementation of algorithmic techniques for solving geometric shortest path problems, their generalizations, and applications. Of interest are not only theoretically efficient algorithms, but also practically efficient ones. The research has three main interests: (a) Develop efficient algorithmic solutions for several fundamental geometric shortest path problems that are still outstanding (e.g., geometric shortest path queries), (b) investigate new approaches to computing approximate geometric shortest paths, and (c) design effective and practically efficient paradigms for planning robotic shortest paths in the plane and in higher dimensional spaces. Several general frameworks for processing exact and approximate geometric shortest path queries will be investigated. These frameworks offer the promise of achieving new efficient algorithmic techniques and data structures for geometric shortest path queries and for other related problems. Also, a paradigm is being studied for obtaining practical solutions to planning shortest obstacle-avoiding paths for robot motion in planar and higher dimensional environments. This paradigm is based on new data structures called framed-quadtrees and framed-octrees, and has led to new practical robotic path planning algorithms. In addition, algorithmic solutions for shortest paths and their generalizations are applied to practical applications such as data compression, computer vision, image processing, and VLSI design. New approaches for solving application problems based on algorithms for shortest path problems and their generalizations are studied. The possibility of finding new methods for geometric shortest paths that yield efficient implementation performance on existing Massively Parallel Processing (MPP) systems is also explored. The research also includes an important experimental component. The education plan is to develop a new environment for t eaching and experimenting with Massively Parallel Processing (MPP) systems by utilizing the new EXECUBE-based MPP architectures. The goal is to develop an inexpensive, but very robust, MPP system for upper level undergraduate and entry level graduate students to study and gain "hands on" experience with parallelism. The curriculum materials to be developed include concise programming tutorials, lecture notes, sample programs, and projects with sample solutions. This work could provide an integral part of not just electives in parallelism, but virtually of all the upper level computer science and engineering curriculum, and could even provide a basis to spill over into other engineering and scientific disciplines. ***
