Ball Packings and Fat Voronoi Diagrams
Sep 15, 2009
Here's a toy problem: What is the SMALLEST number of unit balls you can fit in a box such that no more will fit? In this talk, I will show how just thinking about a naive greedy approach to this problem leads to a simple derivation of several of the most important theoretical results in the field of mesh generation. We'll prove classic upper and lower bounds on both the number of balls and the complexity of their interrelationships.
Then, we'll relate this problem to a similar one called the Fat Voronoi Problem, in which we try to find point sets such that every Voronoi cell is fat (the ratio of the radii of the largest contained to smallest containing ball is bounded). This problem has tremendous promise in the future of mesh generation as it can circumvent the classic lowerbounds presented in the first half of the talk. Unfortunately the simple approach no longer works. In the end we will show that the number of neighbors of any cell in a Fat Voronoi Diagram in the plane is bounded by a constant (if you think that's obvious, spend a minute to try to prove it). We'll also talk a little about the higher dimensional version of the problem and its wide range of applications.