Fat Voronoi Diagrams

Voronoi refinement is a powerful tool for efficiently generating meshes for finite element simulation. The classic definition of quality in a mesh can be achieved by bounding the aspect ratio of the Voronoi cells measured as the ratio of the circumscribing and inscribing radii as measured from the site. There are tight upper and lower bounds on the number of extra points needed to achieve such a Voronoi diagram. The use of good aspect ratio Voronoi diagrams is central to both quadtree methods [1] and Voronoi refinement algorithms [3]. Unfortunately, bounding the aspect ratio in this way is often an overkill, with lower bounds on the size and runtime that depend on the spread of the input set, a geometric quantity that may be unbounded in n. In this paper, we give a relaxed definition of Voronoi cell quality called fatness that captures many of the nice properties of the old definition without being subject to the lower bounds on the size. We give upper and lower bounds on the complexity of such Voronoi diagrams and provide an algorithm to generate such a Voronoi diagram with only a linear number of extra points. In future work we hope to understand fat Voronoi diagrams well enough to design the next generation meshing algorithm with them. The first and simplest question that arises in this area is whether or not a cell in a fat Voronoi diagram can have an unbounded number of neighbors. We prove that this is not possible for fat Voronoi diagrams in the plane and conjecture that similar bounds hold in higher dimensions. As Figure 1 demonstrates, this is a property peculiar to fat Voronoi diagrams; it holds neither for general fat complexes nor for weighted Voronoi diagrams.