A Study on Fat Voronoi Diagrams |

ABSTRACT:

A Voronoi diagram is ß-fat if every cell C is containedin a ball at most ß times larger than a ball that it contains. We explore thecomplexity of cells in fat Voronoi diagrams in Rd with care tounderstand the dependence on d. Using standard methods, we prove that theaverage number of neighbors of any cell is (4ß)d. We then generalizethis approach to give a worst case bound of (4ß)d log λ neighbors,where ' is the aspect ratio of the Voronoi cell as defined in the VoronoiRefinement meshing literature. Note that all of these bounds are independent ofthe number of input points. We prove a stronger result in the plane, namely,that no cell in a fat planar Voronoi diagram has more than 6π/ arcsin 1/ 4βneighbors. This is in marked contrast to the situation for general planarVoronoi diagrams or even general fat complexes, both of which may have cells oflinear complexity. These general upper bounds are complemented by a lower boundon the complexity of fat Voronoi diagrams in Rd, which says that thetotal number of faces in the diagram is 2Ω(d) (d/β)d.Interestingly, this shows that although the worst-case complexity of Voronoidiagrams is avoided by fat Voronoi diagrams, so too is the best case.