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.

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