A Study on Fat Voronoi Diagrams

Many geometric search data structures employ decompositions of space into fat cells to achieve faster search, better approximation for proximity queries, and lower total complexity (as measured by the number of faces) when compared to their non-fat alternatives. In this chapter, we explore the special case of fat Voronoi diagrams with a particular emphasis on bounding the complexity of the cells locally and understanding the dependence of the dimension, providing both upper and lower bounds. We prove that no cell in a fat planar Voronoi diagram has more than O(1) neighbors. We also prove a bound in higher dimensions on the local complexity that depends on a geometric property of the cells. These general upper bounds are complemented by a nontrivial lower bound on the complexity of fat Voronoi diagrams. Let M be a set of n points in Rd. Recall that the Voronoi cell of a point v E M is the set of all points of Rd that have v as a nearest neighbor in M. The in-ball of Vor(v) is the largest ball contained in Vor(v). It is denoted by and its radius is rv. The out-ball of Vor(v) is its smallest enclosing ball. It is denoted Bv and its radius is Rv. We say that Vor(v) is β-fat if Rv/rv & β. We say that a Voronoi diagram is β-fat if every cell is β-fat. Recall that the definition of aspect ratio is similar to fatness with the added constraint that the in-ball and out-ball are centered at v. Although bounded aspect ratio implies fatness, the converse does not hold . It is known that for all fat complexes, the number of neighbors of a cell is O(1) on average. However, it is possible to improve these bounds to worst-case guarantees when the complex is a Voronoi diagram. The total complexity of a β-fat Voronoi diagram is O(n) and then generalize this to a bound on the complexity of the cells in any dimension, where the bound depends on the log of the aspect ratio of the cells. This generalizes the bounds for the complexity of bounded aspect ratio Voronoi diagrams used in mesh generation. The cell on the left has good aspect ratio. The cell on the right is fat but it does not have good aspect ratio. For the case of planar Voronoi diagrams, we prove a stronger bound, showing that no cell has more than a constant number of neighbors. Such a result does not hold for general planar Voronoi diagrams or for general fat complexes. There even exist simple examples where weighted fat Voronoi diagrams have cells with O(n) neighbors , so the result is not at all obvious. The proof method here is novel in that it exploits a tradeoff between angles in the Voronoi cell It is observed that when β is a constant, the complexity of a cell in a fat Voronoi diagram is at least 2Ω(d log d). Although an integer lattice gives rise to Voronoi cells with only 2O(d) faces, the fatness of the cubical cells is only √d. This lower bound shows exactly the tradeoff between the fatness and the best-case complexity. Thus, fat Voronoi diagrams are bounded away from both the best-case and the worst-case complexity of Voronoi diagrams in general. Figure: Right : A fat Voronoi cell can have arbitrarily many neighbours but at least some of them must be ‘skinny’. Left: If weights are allowed on the vertices, the corresponding weighted Voronoi diagram can be fat and yet have unbounded maximum degree.

The notion of fat objects is quite common in computational geometry. Though several different definitions exist in the literature, the differences are small (mostly just constant factors) for convex polytopes as in the case of Voronoi cells. These definitions arise naturally in settings where the bounds depend on packing arguments. In many cases, fatness is a convenience that permits better analyses, such as in the case of range searching and point location. Fatness has also been considered for robot motion planning and ray shooting . The problem of explicitly computing fat partitions of space was considered by Damian-Iordache. Fatness is also a virtue when the complexes are used for point location and proximity search problems. Erickson gives a thorough analysis of the blowup in Voronoi diagram complexity in low dimensions building on the classical results showing that Voronoi diagrams can have complexity Ω(n)d/2) by Klee and Seidel. Researchers have also looked at the complexity of Voronoi diagrams of random points, showing that this worst case complexity is not the norm. For example, Dwyer proved that n independent and identically distributed points sampled uniformly from a ball have a Voronoi diagram with O(n) complexity. This result was later extended by Bienkowski et al. to random samples from a cube. The linear complexity of Voronoi diagrams with bounded aspect ratio (a subset of fat Voronoi diagrams) is exploited in mesh generation and is a primary motivation for the current research. The total complexity of a complex of fat objects has been studied in the context of robot motion planning. The trick to bounding the complexity is to bound the number of larger neighbors of any cell by volume packing arguments. As shown in the recent paper by Gray, this trick is directly applicable to the case of fat Voronoi diagrams. Thus, the number of (d−1)- dimensional faces of the Voronoi diagram is 2O(d)n and the total complexity is 2O(d2) n counting faces of all dimensions. We begin by ordering the vertices of M by the radius of their in-balls, so u , v when ru < rv, and ties are broken arbitrarily. Figure 3: The ball at w is contained in Vv and has radius rv

We have presented a theory of fat Voronoi diagrams with an emphasis on bounding their complexity. The original motivation for this work was for problems in mesh generation, and indeed this is an area of ongoing work. However, we contend that bounding the complexity of these fat Voronoi diagram is interesting on its own both as a special case of classic problems of bounding polytope complexity and for its relation to fat complexes used in geometric search problems. We have given a proof of the constant local complexity of fat Voronoi diagrams in the plane, a parameterized bound in higher dimensions, and a nontrivial lower bound.

• Gary L. Miller, Todd Phillips, and Donald R. Sheehy. Linear-size meshes. In CCCG: Canadian Conference in Computational Geometry, pages 175–178, 2008.

 Gary L. Miller, Dafna Talmor, Shang-Hua Teng, and Noel Walkington. A Delaunay based numerical method for three dimensions: generation, formulation, and partition. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 683–692.

edge condition in the control volume method. SIAM J. on Numerical Analysis, 36(6):1690–1708.

• Scott A. Mitchell and Stephen A. Vavasis. Quality mesh generation in higher dimensions. SIAM J. Comput., 29(4):1334–1370 (electronic), 2000.

• Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39(1-3):419–441, 2008.

• Partha Niyogi, Stephen Smale, and Shmuel Weinberger. A topological view of unsupervised learning from noisy data. .

• Mark H. Overmars and A. Frank van der Stappen. Range searching and point location among fat objects. J. Algorithms, 21:629–656.

• Todd Phillips. Efficient Mesh Generation for Piecewise Linear Complexes. PhD thesis, Carnegie Mellon University, 2009.

• Steven E. Pav and Noel J. Walkington. Robust Three Dimensional Delaunay Refinement. In Thirteenth International Meshing Roundtable, pages 145–156,Williamsburg, Virginia, September 2004. Sandia National Laboratories.

• Sam T. Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326.

• Jim Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms, 18(3):548–585.

• Alexander Rand and Noel Walkington. 3d Delaunay refinement of sharp domains without a local feature size oracle. In 17th International Meshing Roundtable., 2008.