The goal of this research is the design, analysis, and implementation of algorithms and data structures for a collection of geometric computational tools. These tools are chosen to directly address existing computational problems in application areas including data compression, molecular biology, geographic information systems, and computational fluid dynamics. In particular the following areas are considered. (1) Practical algorithms and data structures for nearest neighbor searching in high dimensions, and applications to problems in data compression. (2) Algorithms and data structures for detecting intersections and simulating the motion of a set of moving objects in two and three dimensional space. (3) Construction and maintenance of triangulations with specified shape requirements and applications to geographic information systems and mesh generation in computational fluid dynamics. Emphasis is on practical, implementable to these problems, and both theoretical and empirical analyses of their performance.
