DATA GENERATION FOR GEOMETRIC ALGORITHMS ON NON-UNIFORM DISTRIBUTIONS
Gary Lee Miller, Dafna Talmor, Shang‐Hua Teng · International Journal of Computational Geometry & Applications · 1999
We study the geometric properties of point sets that arise in the generation of bounded aspect-ratio meshes and present a constructive formulation to define distributions that allow arbitrary refinements. This formulation can be used to define distributions with one or more singularities, which do not occur in the uniform case but do occur in mesh generation for real-world applications. We give an efficient algorithm for the generation of a point set from these distributions. This work is in part motivated by the following observation: The Poisson distribution, points placed uniformly and randomly in a fixed dimension, is one of the most commonly used classes of data sets in the experimental evaluation of geometric algorithms and their implementation. However, despite its importance and interest to computational geometry, the Poisson distribution fails to be good test data for triangulation algorithms and software for mesh generation. Consequently, many implemented sequential and parallel algorithms are tuned to work efficiently for the uniform distribution, but fail to be efficient for nonuniform distributions. Even though the focus of our work is on the generation of data for Delaunay-based mesh algorithms, we hope that it will motivate further theoretical investigations on the generation of data for other geometric algorithms and software.