Geometric Tools and Applications

本研究的目标是设计、分析和实现一组几何计算工具的算法和数据结构。选择这些工具直接解决应用领域中存在的计算问题，包括数据压缩、分子生物学、地理信息系统和计算流体动力学。特别要考虑以下几个方面。(1)高维最近邻搜索的实用算法和数据结构，以及在数据压缩问题中的应用。(2)检测交叉点和模拟一组运动物体在二维和三维空间中的运动的算法和数据结构。(3)构建和维护具有特定形状要求的三角测量，并将其应用于地理信息系统和计算流体动力学中的网格生成。重点是对这些问题的实践性、可实施性，并对其表现进行理论和实证分析。

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.