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.
