Equal Circle Packing
Since coming to GVSU I have been involved in conducting research with undergraduates. I have mentored 15 summer projects resulting in several publications and awards for my students. In 2010 I became the co-director of the Research Experiences for Undergraduates (REU) Site in mathematics at GVSU. This is the latest in a series of such grants for GVSU dating back to 2000. Below is a description of my project for summer 2017. This was also the subject of the summer research with undergraduates in several previous summers.
Suppose you have seven cans of soda pop, what is the smallest box with a square cross section that can hold them standing upright in a single layer? By examining the cross section of the box, you can see that this is equivalent to determining the smallest square that contains seven equal and non-overlapping circles. The optimal solution is the arrangement below. You might think you can rearrange the circles in to a more dense arrangement so that there is no `free` circle (like the one in the upper left corner), but you cannot. This is a result due to J. Schaer and R. Graham from 1965.
Overview and Introduction
Notice how the circles are equal in diameter and non-overlapping and are contained in a square -- that is they form an equal circle packing in a hard-boundary square. Over the summer, we will study an equivalent problem to the soda pop can packing one. We will let the equal circles expand, while fixing the size of the contain. More formally we will seek to determine the largest possible common diameter of a fixed number of circles that form a packing in some kind of container. This is a problem in discrete geometry and, in the case of a hard boundary square, optimal arrangements have been proven for at least 20 circles and there are conjectured optimal arrangements for all n up to over 10000 circles. Packing of equal objects in other hard-boundary containers have also been studied.
This research project examines packings of equal equals in containers other than a hard-boundary square. The main focus of this project will be to consider spaces obtained from square (or more generally parallelograms) where the top and bottom and the left and right sides are identified. One such space is called a square flat torus and is represented by the dark square in the picture below which contains seven circles. Can you count the seven circles?
This is conjectured to be one of three equal density arrangements of seven equal circles on a square flat torus. Included in this picture, in addition to the seven equal circles and the torus, is the packing graph associated to this packing. A packing graph is a graph where the vertices are the centers of the circles and the edges connect tangent circles. This graph comes naturally with an embedding on the torus and its properties are very important in the approach that we will use to study these packing.
In past summer research, we were studied packings on a flat Klein bottles which is a rectangle or square with sides identified in a different way than the torus. Below is an optimally dense packing of three circles on a rectangular Klein bottle with the associated combinatorial packing graph. Can you see the difference between the Klein bottle packing and the flat torus packing?
What Will This Research Involve?
Desirable Experiences For Applicants
What this project is NOT...
How To Apply
Applicants should like to analyze geometric situations -- working with lines, angles and geometric objects will be important to success of this research. The ideal applicant will geometrically inclined. The desirable experiences for applicants to this project are a positive attitude toward geometric ideas and a bit of geometric background. The background could be just that you liked geometric reasoning in the classes you have taken (like calculus or linear algebra) or it could be your enjoyment of any kind of geometry course you have taken.
Applied. Yes, I really DO NOT care about applications of this to packing anything real. I enjoy the mathematical side of this and not anything practical that may come out of this. (There could be applications of this -- I do not know and I’m not looking for them.... If you happen to find some please let me know.)
For application information and instructions, please visit the GVSU Summer Mathematics REU home page.
1) Exploring packings to find candidate optimal arrangements. Some of this might be done using the program that I wrote during my sabbatical at Cornell University.
2) Analyzing geometric situations, like finding the analytic coordinates of the centers of the circles in the packings above.
The goal of the research is to prove that we have all the optimal arrangements for a fixed small number of circles in a container or class of containers. Further we also need to prove that the discovered arrangement are, in fact, optimal. We will begin the summer by reviewing techniques used by previous summer research students (this will take at most a few days).
This summer research will involve formulating and proving theorems about packings. The primary tools/techniques/activities involved in this are the following: