Neighbourly Polyhedra

k4In the plane, it is relatively easy to find four convex polygons which pairwise share an edge and are otherwise disjoint. Can you find five polygons in the plane with these properties? How about polyhedra? How many polyhedra can you find such that any pair of them share a face and are otherwise disjoint?
For me, this is an example where my three-dimensional imagination fails utterly. If you have never thought about this before, I suggest to try finding as many such polyhedra as possible (why not start with seven?) before reading on.

First of all, we cannot find five polygons in the plane with the required properties. Assume we have found such a constellation. Take its dual graph, i.e., a graph with one vertex per polygon. Whenever two polygons touch, there is an edge between the respective vertices. This yields a planar drawing of K_5, the complete graph on five vertices. However, K_5 is not planar and hence no such configuration can exist.

A first hint that the situation in three-dimensional space is quite different comes from the fact that any graph can be embedded in \mathbb{R}^3 without crossings.

The question for polyhedra is known as Crum’s problem and an early solution is due to Besicovitch. I first met the problem in Béla Bollobás’s book The Art of Mathematics – Coffee Time in Memphis. It provides a dense collection of highly captivating problems, hints, and solutions.

The result in Coffee Time came as quite a surprise to me: pick any number of points on the curve x\mapsto (x,x^2,x^3). If the points n_i are sufficiently sparse on the curve, e.g., n_i:=10^{2^i}, then it is fairly easy to show that their three-dimensional Voronoi diagram is such that any two of its cells share a face.

Still, my three-dimensional imagination was asking for visualisation, needing to see in order to understand. However, the solution above is not very handy for visualisation because it quickly leads to very large numbers in the coordinates of the points. Luckily, there is a very similar family of points whose Voronoi diagram also yields a solution. It is given in Jack Erickson’s and Scott Kim’s paper Arbitrarily Large Neighborly Families of Congruent Symmetric Convex 3-Polytopes. This family is given by points on the curve t\mapsto (t,\cos t, \sin t)=:h(t). Now, for any integer n, the Voronoi regions of any n+1 consecutive points in the sequence (h(2\pi t/n)_{t\in\mathbb{Z}}) pairwise share a face. By clever cropping of the Voronoi regions, we get a solution with pairwise congruent polyhedra.

Now these Voroi regions can be easily computed with tools like Voro++. This is what I did (Thanks go to the author Chris Rycroft who quickly helped me with a stupid question on Voro++). Here is a visualisation for eight regions.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s