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.