Efficient Algorithms and Data Structures in Computer Aided Geometric Design

Research Associates: G. Xu

Research Assistants: F. Bernardini, J. Chen, S. Evans, H.Y. Lee

Sponsor: AFOSR, NSF

The numerous approaches in computational geometry to date have been largely theoretical and dealing with discrete and combinatorial structures such as point sets, lines, polygons, polyhedra, and at most a general arrangement of hyperplanes. Furthermore, the work has dealt with sequential machines and single user interactive environments.

The research here considers:

• The design and implementation of algorithms and data structures for fundamental manipulations on curves, surfaces, and solids bounded by algebraic surface patches. These manipulations include geometric design operations such as intersection, convex hull, offset, convolution, triangulation, decomposition, surface fitting, and polyhedral smoothing [1, 2, 3, 4, 5].

• The design and implementation of efficient parallel algorithms for MIMD shared or distributed memory, tightly coupled multiprocessor machines (e.g., nCube 2, Intel Paragon, IBM SP2).