Generalized Wigner-Seitz Cells (February 2002)
This is less of a well-defined problem than other months have been. I've been playing with packing of circles in circles and circles on a sphere. Packing will be a topic on this site sometime in the next few months. In the meantime, there are some useful formulas to derive, and introducing Wigner-Seitz cells seems like a good way to lay the foundations.
Let's say that this was not a wildly popular topic. I'm not sure if it was considered too easy or too hard or just not that exciting. The hard part of this problem involves moving from a concept to an algorithm. I found some interesting stuff en route that I think I'll save for another month.
In crystallography, a lattice is an infinite collection of points characterized by a constant offset in each of three axes of the lattice. Many properties of real crystals are modeled very well by describing the crystal as a lattice. When considering a crystal composed of a single element, such as gold or graphite (but not diamond), lattice points are normally taken to represent the center of each atom (thermally averaged, of course). For ionic crystals or molecular solids, the lattice points represent the smallest repeated unit. In ordinary table salt (NaCl), for example, one lattice point represents a sodium ion and a chlorine ion.
In analyzing the properties of the crystal, it is often desirable to divide space into identical cells, such that all space can be filled with these identical cells with same offset as the lattice. Of course, there are an infinite number of ways to do this. One standard method is to define a Wigner-Seitz cell around the lattice point. The Wigner-Seitz cell is the region around any lattice point, which is closer to that point than to any other.
This is convenient, primarily because it uniquely defines a cell for every lattice. In my case, I'm more interested in collections of points which are not lattices. I've had many occasions where I wanted to divide a space into regions around each point, but I didn't have a good algorithm for doing it. Usually I just wanted to enhance a display like the solution to November's problem. In this case, I'm actually interested in the (generalized) Wigner-Seitz cells themselves.
I'm looking at a broad case of packing problems where you are trying to determine the largest sized circle, such that you can put n circles into a particular two-dimensional space. (I'm most interested in circles in the unit circle and circles on the unit sphere.) Every solution to this type of packing problem will have the following property: If you remove any circle and determine the generalized Wigner-Seitz cells around the remaining circles, then the location of the removed circle will be a vertex of the resulting graph, or it will be an appropriate point on the container boundary.
For circles on the unit sphere, there is no boundary. For circles inside the unit circle, it is convenient to pack points inside a circle, maximizing the minimum distance between any two points. Any solution to this problem can be converted to a packing of circles inside a circle by increasing the radius of the outer circle by an amount equal to half the distance between points.
If we adopt this convention, then for n > 7, every removed point is on a vertex of the Wigner-Seitz cell boundaries, either where three or more cells come together or where two or more cells meet the boundary. For n < 7, it is possible to have the removed point be on the outer boundary, inside one of the Wigner-Seitz cells, such that the line from the point defining that cell to removed point is perpendicular to the boundary. That is, the circle is trapped between another circle and the outer wall. For n >7, the curvature of the outer boundary is not high enough.
So here are some specific questions:
I made extensive use of vector notation when I worked on this problem. You may want to look at my summary of vector operations.
This is by no means an exhaustive list of interesting topics in this area. Generalized Wigner-Seitz cells in three, or even in n dimensions are interesting. This is a good launch into lattices, if you haven't studied them or played with them. The polyhedra that are formed by Wigner-Seitz cells of lattices are fun, too. I'd love to hear some suggestions for new topics that you find.
Send all responses to .