Domain Discretization and Circle Packings

A circle packing is a configuration of circles which are tangent with one another in a prescribed pattern determined by a combinatorial triangulation, where the configuration fills a planar domain or a two-dimensional surface. The vertices in the triangulation correspond to centers of circles, and edges correspond to two circles (having centers corresponding to the endpoints of the edge) being tangent to each other.

This circle packing creates a rigid structure having an underlying geometric triangulation, where the centers of circles again correspond to vertices in the triangulation, and the edges are geodesic segments (Euclidean, hyperbolic, or spherical) connecting centers of circles that are tangent to each other.

Three circles that are mutually tangent form a face of the triangulation. Since circle packing is closely related to triangulation, circle packing methods can be applied to domain discretization problems such as triangulation and unstructured mesh generation techniques. We wish to ask ourselves the question: given a cloud of points in the plane (we restrict ourselves to planar domains), is it possible to construct a circle packing preserving the positions of the vertices? If so, then there exists an underlying triangulation of the domain where the vertices of the triangulation correspond to the centers of the circles.

We also consider the application of circle packings to mesh generation techniques of Jordan domains in the plane. We consider both unconstrained meshes and constrained meshes having predefined vertices as constraints. A standard method of two-dimensional mesh generation involves conformal mapping of the surface or domain to standardized shapes, such as a disk.

Since circle packing is a new technique for constructing discrete conformal mappings, it is possible that circle packing can be applied to such conformal mapping techniques. Sucessful meshing of planar domains can, in the future, be extended to parametric surface meshing and remeshing techniques. Visualizations of these domain discretization techniques will be implemented using MATLAB, and special-purpose programs such as CirclePack, and DesPack.