Geometric Algorithm Design and Implementation

该项目旨在为数据结构和算法的发展进行基础研究，以执行涉及几何对象集合的计算，如直线、平面、多边形、曲线和球体。这些主题在计算机辅助设计、物理建模、软件工程、信息可视化和机器人技术中都有应用。本课题的重点是：1)几何形状分析和容差算法；2)有效几何数据组织的数据结构；3)图形可视化的组合和算法复杂性；4)几何计算的数值稳定性和软件可靠性；5)几何算法实现的面向对象设计模式。这项工作的主要目标是开发用于设计几何数据结构和算法的通用方法，以及将它们整合到面向对象的几何软件库中。这项工作对科学和工程领域的新能力有潜在的影响，这些领域对物理对象进行建模，或者使用几何图形进行信息可视化。此外，这项工作的一个关键组成部分涉及几何软件和互联网技术的发展，用于计算机科学教育。

This project is directed at basic research for the development of data structures and algorithms for performing computations involving collections of geometric objects, such as lines, planes, polygons, curves, and spheres. These topics have applications in computer-aided design, physical modeling, software engineering, information visualization, and robotics. Specific focus in this project is given to: 1) algorithms for performing geometric shape analysis and tolerancing, 2) data structures for efficient geometric data organization, 3) the combinatorial and algorithmic complexity of graph visualization, 4) numerical stability and software reliability for geometric computing, 5) object-oriented design patterns for geometric algorithm implementation. The main objective of this work is the development of general methodologies for the design of geometric data structures and algorithms, as well as their incorporation into object-oriented geometric software libraries. This work has potential impacts in enabling new capabilities in areas of science and engineering that model physical objects or that use geometry for information visualization. In addition, a key component of this work involves the development of geometric software and Internet technology for use in computer science education.