next up previous
Next: Parallel Application and Up: Mathematical Software for Previous: Numerical Software for

Development of Computational Geometry Algorithms

Javier Bernal and Christoph Witzgall ACMD

The purpose of this work is to develop, implement, and test algorithms and associated data structures in the field of Computational Geometry with emphasis on Voronoi diagrams and Delaunay triangulations. This area of research has applications in spatial data manipulation, cluster analysis, pattern recognition, and locational optimization.

Early applications at NIST were in the area of Crystallography where 3-D Voronoi diagrams assisted in the classification of materials. The research supports the current ACMD work on terrain modeling and the probabilistic computation of flow velocity fields in 2-D cross sections.

Software is being developed for computing regular tetrahedralizations based on incremental topological flipping. A regular tetrahedralization for a finite set of points in 3-dimensional space is essentially a Delaunay tetrahedralization for the set taking into account weights that have been assigned to the points in the set. Only within the last couple of years it was established that if the points for which a regular tetrahedralization is desired are added one by one then flipping in a topological order will succeed in constructing this type of tetrahedralization. Part of the strategy of computing regular tetrahedralizations in this manner consists of constructing first an artificial perfect cube so that the points are well-contained within it. The eight corners of the cube can be considered as artificial points chosen at infinity, thus requiring that they be handled lexicographically. Each of the situations involving artificial points that can occur during the computation of a regular tetrahedralization have been identified. This software eventually will be used for the probabilistic computation of flow velocity fields in 3-dimensional cross sections.

In a separate development, C. Witzgall found a novel characterization of Delaunay triangulations based on the sum of radii of inscribed circles. This result was presented at a lecture at Clemson University in October, 1995.

The development of software for computing regular tetrahedralizations will continue. This includes creating code for handling artificial points lexicographically.



next up previous
Next: Parallel Application and Up: Mathematical Software for Previous: Numerical Software for



Generated by boisvert@nist.gov on Mon Aug 19 10:08:42 EDT 1996