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.