Examples of parallelohedra typically arise in Voronoï tilings of lattices. The Voronoï cell of a lattice point is the set of all points that are at least as close to any other lattice point as to this given lattice point. These cells form a tiling (even more: a lattice tiling) with translates of space. The figure illustrates the two (combinatorial) types of two-dimensional Voronoï-cells in their lattice tilings.

Fedorov was the first to succeed in classifying the parallelohedra in 3-space. These are convex bodies which allow tilings of Euclidian space (of a given dimension) by translations only. (In this case, even a face-to-face tiling by lattice vectors can be realized, see below.)


Basic concepts and results of the classification

Already in antiquity it was known that in the plane the only polygons satisfying the about conditon are parallelograms and centrally symmetric hexagons. For a long time it has been a hard and interesting research problem to find the analogous statement in higher dimensions. However, only little progress has been achieved in arbitrary dimension.

two polytopes combinatorially equivalent to the cube

In dimensions 3 and 4 we have a complete picture: By the work of the two Russian mathematicians Fedorov and Delone, the combinatorial types of parallelohedra are completely classified. By "combinatorial" is meant that all metric data of the polytope are omitted, only the information which k-(dimensional) face is contained in which (k+1)-faces is retained. This reduction is formalized in the face lattice of the polytope.

name	f0	f1	f2	2-subdiv.	belts
truncated octahedron	24	36	14	68 46	66
hexarhombic dodecahedron	18	28	12	64 48	64 41
rhombic dodecahedron	14	24	12	412	64
hexagonal prism	12	18	8	62 46	61 43
cube	8	12	6	46	43
Besides the f-vector (i.e. the number of vertices f0, of edges f1 and of the faces f2), the 2-subdivision (64 48 stands for 4 hexagons and 8 quadrilaterals) and the number of belts are given above: the latter are families of (4 or 6) parallel edges; the subscripts indicate the size of the corresponding family.

The Characterization of Venkov and McMullen

It is not hard to show that for parallelohedra the following holds:

Belts are maximal families of parallel (d-2)-faces (also called ridges or subfacets), where d denotes the dimension of the parallelohedron. The projection of the polytope to the 2-dimensional subspace orthogonal to one of the ridges is obviously again a parallelohedron, hence a rhombus or a hexagon according to the remarks in the beginning (this proves property (P3)).

Now it is quite surprising that the converse also holds: every polytope satisfying properties (P1), (P2) and (P3) is a parallelohedron, moreover, we can achieve that the translation tiling is face-to-face and thus a lattice tiling. In other words, every polytope that tiles space by translations admits such a tiling even by translations with lattice vectors. This result is often attributed to P. McMullen (1971) and was considered before to be an open problem, but in fact it had been proved almost 30 years earlier by B. A. Venkov ([8], [11]).

How can we find parallelohedra? As the illustration above indicates, lattices in Euclidian space give rise to various examples of Voronoï cells.

By the Voronoï cell (or Dirichlet cell, honeycomb etc.) of an element of a discrete point set we understand the set of all space points whose distance to the given point is not larger than to any other point of the discrete set. The set of schools in a town provides a typical example from everyday life, the Voronoï cells being the school districts.

In general, the Voronoï cells generated by a discrete point set are completely different from one another. At least they always form a face-to-face tiling of the space. As to lattices, all Voronoï cells are congruent and are translates of each other by lattice vectors. So it is justified to speak about the Voronoï cell of a lattice (illustration above).

Accordingly, Voronoï cells of lattices are always parallelohedra and thus satisfy the properties (P1) to (P3); this can be shown independently of Venkov's and McMullen's characterization. In addition, another property holds and is not hard to prove:

(P4) does not hold for arbitrary parallelohedra, as a non-orthogonal rhombus shows. However, this seems to be the only restriction to prevent parallelohedra from being Voronoï cells. Indeed, in 1908 Voronoï conjectured the following:

So far, the conjecture has been proved only in special cases and is still open in general!

Voronoï himself established it for primitive parallelohedra [12]. One can generalize the concept of primitivity as follows. Given a face-to-face tiling in d-space, recall that primitive simply means that each vertex of a tile is also the vertex of exactly d other tiles. The parallelohedron is called k-primitive if each k-face is a k-face of exactly d-k other parallelohedra. Hence 0-primitivity is equivalent to primitivity and for k=d-1 there is no restriction. It can be seen that k-primitivity implies (k-1)-primitivity.

In 1929 Zitomirskij [13] extended Voronoï's result to (d-2)-primitive parallelohedra. It follows that the conjecture is true for all parallelohedra with belts of length 6 only (in dimension 4, no less than 17 out of 52 have this property).

By oral communication we know from B. B. Venkov (the son) that his father showed that for a given parallelohedron, the conjecture follows from the vanishing of a certain cohomology group assigned to this polytope. By this, he was able to prove the conjecture for all polytopes with no more than one belt of length 4. B. B. Venkov believes that the vanishing of the cohomology group in question is also necessary for Voronoiï's conjecture (for a parallelohedron). All these statements are unpublished and rely on Venkov's memory and my talking to him a few years ago.

The classification results of Fedorov [6] and Delone [2] and those in dimensions 1 and 2 imply the correctness of the conjecture for dimensions d up to 4.

During the last years it could also be proved for zonotopal parallelohedra (projections of (higher-dimensional) cubes) by R. Erdahl [5] and independently by F. Vallentin in his diploma thesis [10].


References

[1]	Conway, J.H., Sloane, N.J.A., Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices., Proc. R. Soc. Lond. A 436 (1992), 55-68.
[2]	Delone, B.N., Geometry of positive quadratic forms, Usp. Mat. Nauk 3 (1937), 16-62, Usp. Mat. Nauk 4 (1938), 102-164. (In Russian.)
[3]	Dienst, Th., On zone-reductions in Voronoi-cells of lattices of the first kind, preprint, 1999.
[4]	Engel, P., Geometric crystallography, D. Reidel Publishing Company, 1986.
[5]	Erdahl, R.M., Zonotopes, dicings, and Voronoi's conjecture on parallelohedra, Eur. J. Comb. 20 (1999), 527-549.
[6]	Fedorov, E.S., The symmetry of regular systems of figures, Zap. Miner. Obshch. 21 (1885), 1-279. (In Russian.)
[7]	Janzen, S., Voronoi-Zellen von Gittern erster Art, Diplomarbeit, Universität Dortmund, 1998.
[8]	McMullen, P., Convex bodies which tile space by translation, Mathematika 27 (1980), 113-121. Acknowledgement of priority, Mathematika 28 (1981), 191.
[9]	Rybnikov, K., On the State of Voronoi's Conjecture on Parallelohedra, preliminary report.
[10]	Vallentin, F., Über die Paralleloeder-Vermutung von Voronoi, Diplomarbeit, Universität Dortmund, 2000.
[11]	Venkov, B. A., On a class of euclidian polytopes, Vestnik Leningrad Univ. (Ser. Mat. Fiz. Him.) 9 (1954), 11 -31. (In Russian.)
[12]	Voronoï, G., Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxieme mémoire. Recherche sur les paralléloèdres primitifs I, J. reine angew. Math. 134 (1908), 198-287.
[13]	Zitomirskij, O. K., Verschärfung eines Satzes von Woronoi, Z. Leningrad. Fiz.-Mat. Obsc. 2 (1929), 131-151 (1931).