Data generation for geometric algorithms on non-uniform distributions

We study the geometric properties of point sets that arise in the generatio n 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 n ot 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 di stribution, points placed uniformly and randomly in a fixed dimension, is o ne of the most commonly used classes of data sets in the experimental evalu ation of geometric algorithms and their implementation. However, despite it s importance and interest to computational geometry, the Poisson distributi on fails to be good test data for triangulation algorithms and software for mesh generation. Consequently, many implemented sequential and parallel al gorithms are tuned to work efficiently for the uniform distribution, but fa il to be efficient for nonuniform distributions. Even though the focus of o ur work is on the generation of data for Delaunay-based mesh algorithms, we hope that it will motivate further theoretical investigations on the gener ation of data for other geometric algorithms and software.