 |
Kissing Numbers
|
|
Kissing Numbers
|
Suppose we surround our game objects by bounding circles (the circle of smallest radius that surrounds the object's sprite) in 2D and bounding spheres (the smallest sphere that surrounds the vertices in the object's mesh) in 3D. It has been shown that every configuration of \(n\) non-overlapping circles and every configuration of \(n\) non-overlapping spheres can have at most \(O(n)\) contact points. This implies that broad-phase collision detection and response need only process \(O(n)\) collisions per animation frame. This is shown in the next two sections by the use of a concept called the kissing number. Section Section 2 proves bounds on 2D kissing numbers, and Section Section 3 proves bounds on 3D kissing numbers.
This section is divided into two subsections. As a starting point, Section 2.1 considers the possible number of contacts between \(n\) circles of the same radius. Section 2.2 extends this result to \(n\) circles that may have different radii.
Consider contacts between circles of equal radius (called congruent circles). Since the centers of three touching circles form an equilateral triangle whose internal angles are all \(60^{\circ}\) (see Fig. 2.1), each circle can contact at most \(360^{\circ}/60^{\circ} = 6\) others (see Fig. 2.2). This is called the 2D congruent kissing number \(k_2 = 6\). Therefore between \(n\) congruent circles there can be at most \(3n\) contacts.
The 2D non-congruent kissing number \(\kappa_2\) is also 6. Suppose that we have \(n\) circles of possibly different radii that have \(m\) contact points. Notice that \(k_2 \leq \kappa_2 \leq 2m/n\). Create a graph on \(n\) vertices by placing a vertex at the center of each circle and connecting each pair of vertices with an edge when the corresponding pair of circles are touching (Fig. 2.3). Each edge is completely contained within the two contacting circles and it crosses the circle boundaries at the contact point (Fig. 2.3, center). This graph is therefore planar and has \(m\) edges. A face in a planar graph is an area bounded by edges. The outside of the graph also counts as a face. Fig. 2.3 (left) shows 8 noncongruent circles with 11 contact points. Fig. 2.3 (right) shows the corresponding planar graph, which has 8 vertices, 11 edges, and 5 faces.
Euler showed that for planar graphs the number of vertices \(n\) plus the number of faces \(f\) minus the number of edges \(m\) is always equal to 2. That is, \(n-m+f=2\), known as the Euler characteristic of a planar graph. Since every face has at least 3 edges and every edge is in at most 2 faces, \(f \leq 2m/3\). Therefore, by the Euler characteristic, \(n-m/3 \geq 2\), that is, \(m \leq 3n - 6\). Hence, \(\kappa_2 = 2m/n \leq 6\). Since \(\kappa_2 \geq k_2\) and \(k_2 = 6\) (see Section 2.1), we can conclude that \(\kappa_2 \geq 6\), completing the proof that \(\kappa_2 = 6\). Therefore between \(n\) non-congruent circles there can be at most \(3n\) contacts.
This section is divided into two subsections. As a starting point, Section 3.1 considers the possible number of contacts between \(n\) spheres of the same radius. Section 3.2 extends this result to \(n\) spheres that may have different radii.
In 3D we can start with a single sphere surrounded by 6 spheres all in a plane, then stack 3 spheres on top and three spheres below in 3 layers as shown in Fig. 3.1. This gives us a 3D kissing number of 12. Or so it seems. It turns out that the spheres don't fit together as tightly in 3D as they did in 2D. Suppose we remove the yellow sphere at the center in Fig. 3.1. If we join the centers of the outside spheres we get an icosahedron, an example of which is shown in Fig. 3.2, left. An icosahedron is made up of 20 equilateral triangles as shown in Fig. 3.2, right.
Let's take the smallest icosahedron that we can make out of 12 unit spheres, that is, one whose edge length is 2. (since then we can fit a unit-radius sphere centered at each end of the edge without them overlapping). Let \(\vec{c}\) be the center of the icosahedron, that is, the point that is equidistant from all vertices. The radius of the icosahedron is the distance from \(\vec{c}\) to any vertex \(\vec{p}\) as show in Fig. 3.3 (left). Examining Fig. 3.3 more closely, we see that \(\vec{c}\) is equidistant from a pair of regular pentagons of side 2 in the horizontal plane. These pentagons are distance \(\sqrt{3}\) apart. To see this, note that the front face of the icosahedron is an equilateral triangle of side 2 in the vertical plane. Therefore, if we draw a vertical line from the lower vertex of that triangle to a point midway along its base as shown in Fig. 3.3 (right) then, by the Theorem of Pythagoras, the height of the front triangle \(h\) satisfies \(h^2 + 1 = 2^2\), that is \(h = \sqrt{3}\).
The center \(\vec{c}\) of the icosahedron aligns vertically with the centers of the two pentagons, as shown in Fig. 3.4. (left). The center of a pentagon divides it into 5 sectors, each of which has two edges of length equal to its radius, the third edge is of course of length 2, and the angle between the two radiuses is \(2 \pi/5\), as shown in Fig. 3.4. (center). The radius \(r_0\) of a regular pentagon of side 2 is therefore given by \(\sin \pi/5 = 1/r_0\) (Fig. 3.4., right). Therefore,
\[ r_0 = \frac{1}{\sin \pi/5} \approx 1.7. \]
The radius \(r\) of an icosahedron of side 2 is the length of the hypotenuse of a right triangle with sides \(r_0\) and \(\sqrt{3}/2\) (see Fig. 3.5). By the Theorem of Pythagoras,
\[ r = \sqrt{r_0^2 + 3/4} \approx 1.91. \]
Therefore the center sphere can have radius at most \(0.91\). In order to fit in a center sphere of unit radius we have to loosen up the enclosing icosahedron slightly, which means that we can move the outside 12 spheres around while still touching the center one.
Mathematician David Gregory (1659–1708) thought he could use that slop to fit in a 13th sphere. Sir Isaac Newton disagreed. Naturally Newton was right and Gregory was wrong, but we had to wait a couple of centuries until Schütte, van der Waerden, and and Leech were able to prove that the 3D congruent kissing number \(k_3 = 12\).
Schütte, K. and van der Waerden, B. L., Das Problem der dreizehn Kugeln, Math. Ann. 125 (1953), 325–334.
Suppose we have \(n\) non-congruent spheres numbered \(S_0, S_1, \ldots, S_{n-1}\) such that their radii are in nondecreasng order, that is, \(S_i\) has radius \(r_i\) and \(r_0 \leq r_1 \leq \cdots \leq r_{n-1}\). Let's try to count the total number of contacts \(m\). For \(0 \leq i < n\), let \(m_i\) be the number of spheres \(S_j\) that are touching \(S_i\) and are either (a) smaller than \(S_j\), or (b) the same size as \(S_j\) and \(i < j\). Then,
\[ m = \sum_{i=0}^{n-1}m_i, \]
noting that each contact is counted once because (b) breaks the tie between congruent spheres.
Consider an individual sphere \(S_i\). For example, Fig. 3.6 (left) shows a sphere \(S_i\) with \(m_i = 6\) since \(S_i\) touches 6 spheres, 2 of which are larger, 3 of which are smaller, and one of which is congruent. Disregard the smaller spheres, as shown in Fig. 3.6 (center). Replace each of the larger spheres with congruent spheres that have the same respective contact points. Note that \(m_i\) is unchanged through all of these steps. For example, \(m_i = 3\) in all three of the configurations shown in Fig. 3.6. \(S_i\) is now surrounded by \(m_i\) congruent spheres. Therefore, \(m_i \leq k_3\), which means that
\[ m = \sum_{i=0}^{n-1}m_i \leq \sum_{i=0}^{n-1} k_3 = nk_3. \]
Hence the total number of contacts \(m \leq 12n\) and the average kissing number \(\kappa_3 = 2m/n \leq 2k_3 = 24\). The above proof is from a paper by Kuperberg and Schramm:
Greg Kuperberg and Oded Schramm, "Average kissing numbers for non-congruent sphere packings", Mathematical Research Letters, pp. 339-344.
They then go on to show using a stronger argument that \(\kappa_3 < 4(2+\sqrt{3}) \approx 14.928\) and \(\kappa_3 \geq 666/53 \approx 12.566\) The best upper bound for \(\kappa_3\) known to the author at present is \(\kappa_3 \leq 13.955\) by Glazyrin:
Alexey Glazyrin, "Contact graphs of ball packings", arXiv preprint arXiv:1707.02526.
The best lower bound for \(\kappa_3\) known to the author at present is \(\kappa_3 \geq 7656/607 \approx 12.613\) by Eppstein, Kuperberg, and Ziegler:
David Eppstein, Greg Kuperberg, and Günter M Ziegler, "Fat 4-polytopes and fatter 3-spheres." Pure and Applied Mathematics, 253 (2003), 239-266.
1.12.0