This page explains in detail how the Penrose tiling, and other related quasiperiodic tilings drawn by the deBruijn applet, are constructed from a hypercubic lattice
in *R*^{n}. It also discusses the generalisation of these methods to higher dimensional tilings, and to other lattices (including the *A*_{n} lattice used by the Tübingen applet).

- Quasiperiodic tilings of the plane from the hypercubic lattice
- Higher-dimensional tilings
- Other lattices
- The lattice
*A*_{n} - References

We define the points of the lattice *Z*^{n} to be those (*x*_{1}, …, *x*_{n}) in *R*^{n} where all the *x*_{i} have integer
values. These points comprise the vertices of an infinite number of unit hypercubes packed together to fill *R*^{n}, so we will refer to this as the “hypercubic lattice”.

Suppose we choose an affine plane *P* in *R*^{n} parallel to the two-dimensional subspace spanned by the two vectors:

= (1, –cos(π/xn), cos(2π/n), …, (–1)^{(n–1)}cos((n–1)π/n))

= (0, –sin(π/yn), sin(2π/n), …, (–1)^{(n–1)}sin((n–1)π/n))

These are not unit vectors; if we want to normalise them we need to divide by √(*n*/2).

The projections of the *n* coordinate axes and their opposites onto *P* form a symmetrical 2*n*-pointed star.
Note that for odd values of *n*, *P* is orthogonal to one of the hypercubic lattice diagonals, (1,1,1,1,…,1), but this is not the case for even *n*;
if it were, the projections of the 2*n* vectors would overlap each other to form an *n*-pointed star.

We are interested in identifying squares within the lattice that “approximate” the plane *P*, in the sense that all four of these squares’ vertices can fit simultaneously within
a unit-side-length hypercube whose centre lies somewhere on *P* and which is oriented parallel to the hypercubes of the lattice itself.
Because the lattice has
a spacing of 1, and the hypercube whose centre lies on the plane has a side length of 1, if a whole square from the lattice ever lies inside the hypercube
then the hypercube’s centre must have the two coordinates corresponding to the square’s edge directions equal to those of the centre of the square itself.
In other words, those coordinates will have odd-half-integer values, midway between the integer values of the lattice points.

If we define *n* families of hyperplanes in *R*^{n} by fixing each of the coordinates *x*_{i} at odd-half-integer values, then the intersections of *P*
with these families of hyperplanes will be sets of parallel lines in *P*. Wherever two of these lines intersect at a point *Q*, a unit hypercube centred at *Q* will contain a complete square from the lattice.

Another way to think about this is to consider the lines to be dividing *P* into regions which are its intersections with the **dual fundamental domains** of the lattice:
unit hypercubes centred on all the points of the lattice. (The hyperplanes *x*_{i} = odd-half-integer all lie on the boundaries of these dual fundamental domains.)
If we place the centre of a unit hypercube anywhere in the interior of one of those regions of *P* — that is, at a point on *P* that is enclosed by the hypercube centred on some lattice point *L* —
then that hypercube will, in turn, enclose the associated lattice point *L*.
If we put the centre of our hypercube on the border between two regions — i.e. on one of our lines — it will simultaneously enclose *two* adjacent lattice points. And
if we put the centre on a point where four regions meet — i.e. at the intersection of two of our lines — then it will simultaneously enclose a square of *four* lattice points.

Exactly how the lattice square fits within the hypercube in the *other* (*n*–2) dimensions will vary, but if we find the integer values closest to *Q*'*s* coordinates in those
dimensions — integer values which are no more than 1/2 away from the hypercube’s centre at *Q* — that will identify a particular lattice square:
one which is *exactly* centred on *Q* in two of the *n* dimensions, and whose centre is as close as possible to *Q* in the other (*n*–2) dimensions.

Projecting these lattice squares onto *P* gives us our tiles. A few examples are shown below, for *n*=5. The shape and orientation of the tile is determined by the particular pair of dimensions
associated with the intersecting lines.
The edges of the tiles are projections of the basis vectors *e*_{i} onto *P*. We can split each basis vector into its projection onto *P* and a part that is
orthogonal to *P*, i.e. *e*_{i} = *e*_{proj, i} + *e*_{orth, i}.
Since the families of lines lie within *P*, they are orthogonal to *e*_{orth, i}, and since they lie within the hyperplanes *x*_{i} = odd-half-integer they are also orthogonal
to *e*_{i}; this means their dot product with *e*_{proj, i} must also be zero.
So the edges of the tiles are orthogonal to the associated lines on *P*.

Note that there is no fixed relationship between the point *Q* and the *location* of the tile, because the lattice
square is free to sit within the hypercube centred at *Q* in various ways in (*n*–2) dimensions.

If we project *all* the lattice squares selected by this process, they fit together nicely:

We’ll now derive an explicit formula for the points *Q* where our families of lines intersect. If we choose the vector ** a** in

b^{j,k}+xcos(kπ/n) +ysin(kπ/n) = 0

Here *x* and *y* are coordinates on *P* with respect to our chosen basis, and we’ve defined the abbreviation:

b^{j,k}= (–1)^{k}(a^{k+1}–j– 1/2) √(n/2) .

The * k*th family of lines will be orthogonal to the vector (cos(

The point where the (*j*,*k*) line intersects the (*r*,*s*) line will have coordinates:

x= [b^{j,k}sin(sπ/n) –b^{r,s}sin(kπ/n)] / sin((k–s)π/n)

y= [–b^{j,k}cos(sπ/n) +b^{r,s}cos(kπ/n)] / sin((k–s)π/n)

If we wish to avoid **degenerate points**, where more than two lines intersect, we need to be careful with our choice of the offset vector ** a**. For example, if we
choose

If we assume that the solution we found above for the intersection of the (*j*,*k*) and (*r*,*s*) lines also lies on the (*u*,*v*) line, we find that for a degenerate point we’d need to have:

b^{u,v}sin((k–s)π/n) +b^{j,k}sin((s–v)π/n) +b^{r,s}sin((v–k)π/n) = 0

If none of the coordinates of ** a** is an odd half-integer, then none of the

In general, avoiding odd half-integers for ** a** and values contrived to solve the equation above
will be enough to prevent degenerate points from arising in the tiling.

We won’t analyse the statistical properties of these tilings: their quasi-periodicity and rotational quasi-symmetries. However, in some cases
the tilings will have *exact* rotational symmetries about one point.
In analysing these exact symmetries, there are three maps of *R*^{n} that are of interest to us:

The map *C*, where we cycle all the coordinates of *R*^{n}:

C: (x_{1},x_{2}, …,x_{n}) → (x_{n},x_{1}, …,x_{n–1})

the map *D*, where we cycle the coordinates and then change the sign of the new first coordinate:

D: (x_{1},x_{2}, …,x_{n}) → (–x_{n},x_{1}, …,x_{n–1})

and the map *E* = –*C*, where we cycle the coordinates and change the sign of every coordinate:

E: (x_{1},x_{2}, …,x_{n}) → (–x_{n}, –x_{1}, …, –x_{n–1})

All three are symmetries of the hypercubic lattice: they preserve distances, and map all lattice points to other lattice points. The map *C* has order *n*, i.e. *C*^{n} is
the identity map, and *C* has a 1-dimensional subspace of invariant vectors: *C*(*a*, *a*, …, *a*) = (*a*, *a*, …, *a*). The map *D* has order 2*n*, and no invariant vectors.
The map *E* has order *n* if *n* is even, and order 2*n* if *n* is odd. If *n* is even, *E* has a 1-dimensional subspace of invariant vectors: *E*(*a*, –*a*, …, *a*, –*a*) = (*a*, –*a*, …, *a*, –*a*);
if *n* is odd, *E* has no invariant vectors.

If *n* is odd and we apply *C* to the vectors ** x** and

C= (cos((xn–1)π/n), 1, –cos(π/n), cos(2π/n) …, (–1)^{(n–2)}cos((n–2)π/n)) = –cos(π/n)– sin(π/xn)y

C= (sin((yn–1)π/n), 0, –sin(π/n), sin(2π/n) …, (–1)^{(n–2)}sin((n–2)π/n)) = sin(π/n)– cos(π/xn)y

So *C* acts on the subspace as a rotation by an angle of π/*n*
followed by a negation, which is the same as a net rotation by (*n*+1)π/*n*.
If *n* is even, the map *D* has the same effect:

D= (cos((xn–1)π/n), 1, –cos(π/n), cos(2π/n) …, (–1)^{(n–2)}cos((n–2)π/n)) = –cos(π/n)– sin(π/xn)y

D= (sin((yn–1)π/n), 0, –sin(π/n), sin(2π/n) …, (–1)^{(n–2)}sin((n–2)π/n)) = sin(π/n)– cos(π/xn)y

If *n* is even, the map *C* doesn’t preserve the subspace spanned by ** x** and

Since the map *E* is just –*C*, if *n* is even it also won’t preserve the subspace, but if *n* is odd it will, and it will undo the negation we mentioned *C* producing,
leaving just a rotation by an angle of π/*n*.

By considering the orders of these maps and their effects on both the subspace parallel to our chosen plane *P* and the offset vector ** a** that we’ve chosen for

n=5, =(0,0,0,0,0)a | n=5, =(1/5, 1/5, 1/5, 1/5, 1/5)a |
---|

In **the image above left**, we’ve used *n*=5, ** a**=(0,0,0,0,0). The map

In **the image above right**, we’ve used *n*=5, ** a**=(1/5, 1/5, 1/5, 1/5, 1/5). The map

The difference between the two cases shows up in the positioning of the five families of lines in *P*. In the ** a**=(0,0,0,0,0) case (

n=5, =(0,0,0,0,0)a | n=5, =(1/5, 1/5, 1/5, 1/5, 1/5)a |
---|

n=6, =(0,0,0,0,0,0)a | n=6, =(1/6, 1/6, 1/6, 1/6, 1/6, 1/6)a |
---|

In **the image above left**, we’ve used *n*=6, ** a**=(0,0,0,0,0,0). The map

In **the image above right**, we’ve used *n*=6, ** a**=(1/6, 1/6, 1/6, 1/6, 1/6, 1/6). The map

What’s happening in the plane *P*? For the ** a**=(0,0,0,0,0,0) case (

n=6, =(0,0,0,0,0,0)a | n=6, =(1/6, 1/6, 1/6, 1/6, 1/6, 1/6)a |
---|

Instead of projecting onto a plane, we can project onto subspaces of three or more dimensions. The most interesting case involves
choosing a three-dimensional subspace of *R*^{6} such that the projections of the six coordinate axes and their opposites give the twelve vertices of an icosahedron.
The resulting quasicrystal has an icosahedral symmetry that is impossible in a normal, periodic crystal, just as the five-fold symmetry of the Penrose tiling is impossible in a periodic two-dimensional tiling.

To choose a suitable three-dimensional subspace of *R*^{6}, we pick any regular icosahedron in *R*^{3} and locate the six axes that join its twelve vertices in pairs. We choose a unit
vector that lies on each of these axes. If *u*_{j}, *j*=1, …, 6, are the six unit vectors, and *u*_{j}^{i} their coordinates in an orthonormal basis of *R*^{3}, then
the same *u*_{j}^{i} give us, for *i*=1,2,3, the coordinates in *R*^{6} of three vectors which comprise an orthogonal basis of a three-dimensional subspace, *P*,
such that the coordinate axes project onto *P* along the six icosahedral axes we started with.

How do we know that this procedure will give us an orthogonal basis? It is a result in group representation theory ^{[2]} that if you take any linear operator, *S*_{0}, on a vector space *V*,
and an irreducible representation *R* on *V* of a finite group *G*, then if you sum the conjugation of *S*_{0} by *R*(*g*) for all *g* in *G*:

S= Σ_{g ∈ G}R(g)S_{0}R(g)^{–1}

the sum *S* will be a multiple of the identity operator I. Take *S*_{0} to be the projection onto the
axis through one vertex pair, say *S*_{0}^{ik} = *u*_{1}^{i}*u*_{1}^{k},
then choose *G* to be the 60-element group of the rotational symmetries of the icosahedron, with *R* the fundamental representation of this group as rotations in *R*^{3}.
Conjugation with *R*(*g*) will simply transform *S*_{0} into a projection onto the various axes through
the vertices, with each of the six axes appearing ten times.
So *S* will be ten times the sum of projectors onto all six vertex pairs:

S^{ik}= 10 Σ_{j=1, …, 6}u_{j}^{i}u_{j}^{k}

That the matrix for *S* is a multiple of the identity matrix then implies that the three 6-dimensional vectors with coordinates *u*_{j}^{i} are orthogonal to each other. Note that
we could also use this approach to find projections from spaces of dimension 10, 15, or 30 by choosing a face or edge centre of the icosahedron, or a generic point, as our starting vector.
(The icosahedron has 20 faces and 30 edges, whose centres lie on 10 and 15 axes respectively. A generic point will have a 60-point / 30-axis orbit under the symmetry group.)

Having specified *P*, we then have six families of planes where *P* intersects the hyperplanes *x*_{i} = odd-half-integer. These planes will be orthogonal to the projections of the
coordinate axes, and since those projections are aligned with the vertices of an icosahedron, the orthogonal planes will be parallel to the faces of the icosahedron’s dual, a dodecahedron.
Wherever three of these planes intersect, we have a point
where we can place the centre of a 6-cube such that it will simultaneously enclose eight lattice points in a cubic configuration. We project those cubes onto *P* to find the rhomboid-shaped
tiles of the quasiperiodic tiling.

The animation below shows a piece of a quasicrystal with icosahedral symmetry; rather than drawing the rhomboids we have drawn small spheres where the centre of each tile would be, with a colour determined by the shape of the tile.

We’ve chosen to have the subspace *P* pass through the origin, in order to give perfect icosahedral symmetry around one point, but there’s a small hitch that
arises from doing this; it leads to there being some points in *P* where a 6-cube encloses more than the eight lattice points of a 3-cube, and takes in either a full 4-cube or a full 5-cube.

We won’t calculate the coordinates of these degenerate points, but the existence of one set isn’t hard to picture. We’ve already mentioned that the families of planes in *P* are parallel to the faces
of a regular dodecahedron. The image on the **top left** shows how five such planes, if equidistant from the origin, can meet at a single point, through the extension of five faces
of the dodecahedron into the sides of a pentagonal pyramid.

The image on the **bottom left** shows how four planes which come from two *different-sized* dodecahedra with parallel faces can intersect in a single point. Note that the ratio of the sizes
doesn’t need to take on any special value; the four planes will still meet at one point, regardless.

This situation could be finessed in various ways, but for the animation above we’ve just projected down multiple 3-cubes from within the higher dimensional cubes and drawn a sphere at the centre of each.
So as the price of its perfect symmetry, this crystal has some “crowded” sites. The problem vanishes if *P* is given a generic irrational offset from the origin in *R*^{6}.

We can generalise the method we’ve described to apply to other lattices in *R*^{n}
besides the hypercubic lattice ^{[3]}. First, we consider the Voronoi cells
associated with each point ** p** in the lattice: these are the subsets of

The Voronoi cells of a lattice in *R*^{n} are all congruent *n*-dimensional polytopes that pack together to fill *R*^{n}. Dual to this packing we can also
consider the Delaunay cells, which are the convex hulls of the sets of lattice points whose Voronoi cells
share a vertex in common; we say the Delaunay cell is **dual to** that Voronoi cell vertex.
Unlike the Voronoi cells, the Delaunay cells need not all be congruent. (Note that “Delaunay” is sometimes spelled “Delone” ^{[4]}.)

We can extend the notion of the Delaunay cell dual to the vertex of a Voronoi cell by noting that for
each integer *m*=0, …, *n*–1, the Voronoi cells will have various “*m*-boundaries” of dimension *m* (i.e. vertices, edges, 2-faces, …, (*n*–1)-faces) which will
be shared by certain sets of adjoining Voronoi cells.
We define the corresponding “dual (*n*–*m*)-boundaries” of the Delaunay cells to be the convex hulls of those lattice points whose Voronoi cells intersect at the
*m*-boundaries. For example, in *Z*^{3} the Voronoi cells are cubes of unit side length centred on each lattice point. Each face of one of these cubes is a Voronoi 2-boundary;
dual to it is a Delaunay 1-boundary, or edge, consisting of a line segment joining the two lattice points whose Voronoi cells share the face in question.

If our projection space *P* has dimension *m*, we can choose to project selected *m*-boundaries of *either* the Voronoi cells or the Delaunay cells associated with the lattice.
If we want to project *m*-boundaries of the Voronoi cells, we think of *P* as being divided into regions that intersect different *Delaunay* cells. The corners of these regions,
where multiple Delaunay cells intersect *P*, will actually be the points of intersection of *P* with certain (*n*–*m*)-boundaries of the Delaunay cells; we then project the Voronoi cell *m*-boundaries dual to those
Delaunay cell (*n*–*m*)-boundaries.

If instead we want to project the *m*-boundaries of the Delaunay cells, we reverse the roles of Delaunay and Voronoi cells in this procedure, and project the Delaunay cell *m*-boundaries dual to those
Voronoi cell (*n*–*m*)-boundaries that intersect *P*.

For a hypercubic lattice, the Voronoi cells and Delaunay cells are both hypercubes packed into *R*^{n} in identical ways, so there is no real distinction between the two choices.

One of the simplest examples where the Voronoi and Delaunay cells are different is the family of lattices known as *A*_{n}.
The *n*-dimensional lattice *A*_{n} consists of those points of the (*n*+1)-dimensional hypercubic lattice *Z*^{n+1} that lie in the subspace satisfying *x*_{1} + *x*_{2} + … + *x*_{n+1}=0.
Part of the lattice *A*_{2} embedded in *Z*^{3} is shown below; the purple spheres are in *A*_{2}.

Rather than choosing a basis for this subspace and working in *n* dimensions, it will make our calculations simpler if we keep working in (*n*+1) dimensions.
We just have to remember that we’re imposing the condition *x*_{1} + *x*_{2} + … + *x*_{n+1}=0 on everything.

The origin of *R*^{n+1} lies in *A*_{n}, and its nearest neighbours in *A*_{n} will be all the points that lie a distance of √2
away and whose coordinates still sum to zero. These will take the form (1, –1, 0, 0, …), (1, 0, –1, 0, …), etc., where we choose any two of the *n*+1 coordinates to be non-zero,
and then make either the first one +1 and the second one –1 or vice versa. That means there are a total of *n*(*n*+1) nearest neighbours to every lattice point.
Every Voronoi cell in *A*_{n} will have a hyperface, or (*n*–1)-boundary, that it shares with each of its nearest neighbours. These hyperfaces will lie in the hyperplanes that orthogonally bisect lines joining the
lattice point to its neighbours. The Voronoi cells in *A*_{2} are the hexagons in the image below; the Delaunay cells are the dashed triangles.

What can we say about the vertices of the Voronoi cell around the origin? Each vertex will belong to at least *n* hyperfaces with linearly independent normals,
since each hyperface imposes a single linear equation, and we
need *n* independent equations to pin down a single point in our *n*-dimensional subpace. This means the vertex’s dot product with (at least)
*n* distinct vectors with 1 and –1 as their only non-zero coordinates must equal 1 (the norm of such vectors is √2,
and the bisected distance to each nearest neighbour is 1/√2, so in the dot product these factors cancel to give 1).
Also, to lie within the bounds of the Voronoi cell, the vertex’s dot product with *any* vector of that form cannot exceed 1.

Consider the point *v*_{1}=(*n*/(*n*+1), –1/(*n*+1), –1/(*n*+1), …, –1/(*n*+1)). Clearly this lies in our subpace, since the coordinates sum to zero.
If we consider the *n* neighbours of the origin (1, –1, 0, 0, …), (1, 0, –1, 0, …), and so on,
each one will have a dot product with *v*_{1} of exactly 1. And if we take the dot product of *v*_{1} with *any* vector with 1 and –1
as its only non-zero coordinates, the result can only be 0, 1, or –1. So *v*_{1} will be a vertex of the Voronoi cell, as will all *n*+1 similar vectors where
we choose different coordinates to take the value *n*/(*n*+1).

To generalise this, suppose ** v**=(1–

If we try to vary this construction by introducing a third coordinate value, it becomes impossible to obtain the dot product of 1 with a *linearly independent* set of *n* hyperface normals.
So these are all the vertices of the Voronoi cell around the origin.

The count of 2^{n+1}–2 should ring a bell; this is the number of vertices in an (*n*+1)-dimensional hypercube, minus two! Why minus two? If we project all the vertices
in a unit-side-length (*n*+1)-cube centred on the origin into our subspace, exactly two vertices, (1/2, 1/2, 1/2, …, 1/2) and
(–1/2, –1/2, –1/2, …, –1/2), will be projected onto the origin. The remaining 2^{n+1}–2 points will be precisely the vertices of the Voronoi cell
of the origin in *A*_{n}. If we take any vertex (±1/2, ±1/2, ±1/2, …, ±1/2) of the (*n*+1)-cube with *q* positive coordinates,
and project it into our subspace
(which amounts to subtracting off its projection onto the unit vector (1, 1, 1, … 1) / √[*n*+1], or equivalently summing the coordinates, dividing
the sum by *n*+1, then subtracting the result from each coordinate), we get one of the *A*_{n} Voronoi vertices previously described, with *q* coordinates of the form 1–*q*/(*n*+1).

We can enumerate the *m*-boundaries of the *A*_{n} Voronoi cell simply by excluding the *m*-boundaries of the (*n*+1)-cube that contain the two
vertices that project to the origin; we exclude those *m*-boundaries because they project into the *interior* of the *A*_{n} Voronoi cell. The full count of *m*-boundaries
of an (*n*+1)-cube is 2^{n+1–m} (*n*+1)!/[*m*!(*n*+1–*m*)!] (derived here). Omitting those that contain the two excluded vertices,
we get:

Number of= (2m-boundaries for theA_{n}Voronoi cell^{n+1–m}–2) (n+1)!/[m!(n+1–m)!]

Now, as we’ve noted, the vertices of the Voronoi cells each have associated with them a number *q*, which for the Voronoi cell around the origin is a count of the number of coordinates
whose value is 1–*s* (where *s*=*q*/(*n*+1)). This is also the number of coordinates whose value is +1/2 in the (*n*+1)-cube vertex that we projected down to get the Voronoi cell vertex.
This vertex will be shared between the Voronoi cell at the origin and those of *q*(*n*+1–*q*) nearest neighbours, because
we have *q* choices for where we put the 1 in a nearest-neighbour vector so it lines up with one of the coordinates whose value is 1–*s*,
and (*n*+1–*q*) choices for putting a –1 that lines
up with one of the coordinates whose value is –*s*, in order to get the required dot product of 1. So the vertex will lie at the intersection of *q*(*n*+1–*q*) hyperfaces,
each of which will be shared with a nearest-neighbour lattice point.

However, a Voronoi cell vertex can also be shared between two lattice points that *aren’t nearest neighbours*; in that case
the Voronoi cells of the two lattice points don’t have a shared hyperface. For example, the vertex ** v**=(1/2, 1/2, –1/2, –1/2) of the Voronoi cell of the origin in

In general, suppose ** v**=(1–

Σ_{k}q! (n+1–q)! / [(k!)^{2}(q–k)! (n+1–q–k)!]

= (n+1)! / [q! (n+1–q)!]

The Delaunay cell dual to each vertex of the Voronoi cell is the convex hull of the lattice points whose Voronoi cells intersect at that vertex, so we can see that the Delaunay cell will have
a different shape depending on the *q* value for the vertex; in fact, the number of lattice points in the Delaunay cell dual to a vertex with a given *q* value turns out to be equal to the number of
Voronoi cell vertices with that *q* value. (This is not a coincidence, as we’ll see shortly.)
For example, in *A*_{3}, there are 4, 6 and 4 vertices for *q*=1,2,3 respectively, and the total number of lattice points
in the Delaunay cells dual to those vertices are 4, 6 and 4.
The Delaunay cells are tetrahedra and octahedra; there are eight tetrahedral Delaunay cells with the origin as a vertex,
and six octahedra. In the image below, we only show the Delaunay cell faces that intersect the origin. The Voronoi cell for
the origin is the blue polyhedron with 12 rhombic faces in the centre.

Now, the vertices of the Delaunay cells that include the origin all have integer coordinates that are either 0, 1 or –1. This means that they are a subset of the vertices of the
2^{n+1} unit hypercubes in *Z*^{n+1} that have the origin as one of their vertices. More precisely, it turns out that each particular one of the 2^{n+1}–2
Delaunay cells that include the origin (one dual to each vertex of the origin’s Voronoi cell) is simply the intersection with the subspace *S* of one of those hypercubes!
Each vertex ** v** of the origin’s Voronoi cell is found by projecting a point of the form

This shows us exactly where the “coincidence” between the count of Voronoi vertices with a given *q* value and the number of lattice points in the Delaunay cell dual to one of
those Voronoi vertices comes from. The sum of the coordinates of one of our points ** c** has a simple relationship to the

Each *m*-boundary of the Voronoi cell will contain 2^{m} vertices, being a projection of an *m*-boundary of an (*n*+1)-cube. For this set of vertices, *n*+1–*m* of their coordinates
will have a fixed form (always being either 1–*s* or –*s*, though the actual value of *s*=*q*/(*n*+1) will vary),
and the other *m* will take all 2^{m} possible choices between the two forms 1–*s* and –*s*.
As a result, the *q* value of the vertices in the *m*-boundary will range from some mimimum *q*_{0}, that must be at least 1 and at
most *n*–*m*, up to *q*_{0}+*m*.

The Delaunay cell (*n*–*m*)-boundary dual to a given Voronoi cell *m*-boundary will be the convex hull of all the lattice points whose Voronoi cells intersect
to give the *m*-boundary. This will be the intersection with the subspace *S* of the
Delaunay (*n*+1–*m*)-boundary in *Z*^{n+1} dual to the Voronoi *m*-boundary in *Z*^{n+1} that projects to our chosen Voronoi *m*-boundary in *A*_{n}.
More directly, the set of lattice points comprising the vertices of the Delaunay (*n*–*m*)-boundary will be the intersection of the sets of lattice points dual to each vertex in the Voronoi *m*-boundary.
Because of the way lattice points sharing a vertex are constructed, this set will be determined solely by the part of the vertex coordinates that is *fixed* across the whole Voronoi *m*-boundary,
and its size will be given by the sum, where *k* ranges from 0 to max(*q*_{0}, *n*+1–*m*–*q*_{0}):

Σ_{k}q_{0}! (n+1–m–q_{0})! / [(k!)^{2}(q_{0}–k)! (n+1–m–q_{0}–k)!]

= (n+1–m)! / [q_{0}! (n+1–m–q_{0})!]

For example, suppose *n*=4, *m*=2. The Voronoi cell will have (2^{3}–2) 5!/[2!3!] = 60 2-boundaries, all with four vertices.
Each 2-boundary will have a *q*_{0} ranging from 1 to 2, yielding lattice point counts of 3 and 3 respectively.
So the dual 2-boundaries of the Delaunay cells will be the convex hulls of three lattice points; in other words, they will be triangles.

In fact, for any value of *n*, the Delaunay 2-boundaries (which are dual to Voronoi (*n*–2)-boundaries) will be triangles; for *m*=*n*–2, we will always have
*q*_{0} ranging from 1 to 2, yielding lattice point counts of 3 and 3.

If we have a plane *P* that lies in *A*_{n}, we can choose to project either the triangular 2-boundaries of the Delaunay cells or the quadrilateral 2-boundaries of the
Voronoi cells onto *P*. In the first case, we project those Delaunay 2-boundaries dual to Voronoi (*n*–2)-boundaries that intersect *P*; in the second case, we
project those Voronoi 2-boundaries dual to Delaunay (*n*–2)-boundaries that intersect *P*.

Let’s look at the case where we project the triangular 2-boundaries of the Delaunay cells in more detail. We’ve described the mathematics on a conceptual level, but how can we perform these calculations in practice?

For the hypercubic lattice, we made use of the fact that all the Voronoi cell (*n*–1)-boundaries lay on hyperplanes of the form *x*_{i} = *j* + 1/2, where *i* indexed the *n* coordinates
and *j* was any integer. These *n* families of hyperplanes intersected our plane *P* as *n* families of parallel lines, and the intersections between the lines from different families gave us
the intersections of the Voronoi (*n*–2)-boundaries with *P*.

To find the points where the Voronoi (*n*–2)-boundaries in *A*_{n} intersect *P*, we note that once again the Voronoi (*n*–1)-boundaries will lie on certain hyperplanes.
If we take *n*(*n*+1)/2 vectors such as (1,–1,0,0,…) which lie on the rays joining the lattice point at the origin with its nearest neighbours, all the
Voronoi (*n*–1)-boundaries will lie on hyperplanes where the dot product with one of these vectors is an integer. Unlike the case with the hypercubic lattice, however, portions of
these hyperplanes will *not* lie on the boundaries of the Voronoi cells. A glance at the hexagonal Voronoi cells in *A*_{2} should make this clear: unlike the case with a square grid,
extending the border of any cell beyond its endpoints (the dashed lines in the image below) gives you a line that travels into the *interior* of the neighbouring cell rather than
consisting solely of cell borders. So we need to be prepared to throw out some “false positives”: some points on *P* where the lines from these hyperplanes intersect but which do
not lie on the boundary of any Voronoi cell.

Another subtlety we need to account for is that every point where two of the lines intersect will also have a third line passing through it; again the case of *A*_{2}, where
the Voronoi cells’ corners all lie on three lines, makes this clear. For the hypercubic lattice, we looked at *every* intersection between *every pair* of hyperplanes chosen from *n* different
families; for the *A*_{n} lattice, looking at every pairing between our *n*(*n*+1)/2 families of hyperplanes would be overkill.
Instead, we note that every (*n*–2)-boundary lies on the intersection of three hyperplanes that bear a particular relationship to each
other, and we can single out the intersection by referring to just *two* of the hyperplanes. What’s more, we can enumerate a particular subset of suitable pairs to use, as follows.

Recall that the (*n*–2)-boundaries of the Voronoi cell of the origin in *A*_{n} are
projections of (*n*–2)-boundaries of the unit hypercube centred on the origin in *Z*^{n+1}; associated with each (*n*–2)-cube in *Z*^{n} is a choice
of three coordinates from the total of *n*+1 which defines the 3-space orthogonal to that (*n*–2)-cube. There are (*n*+1)*n*(*n*–1)/6 such choices. Given a specific choice of three coordinates,
*i*_{1} < *i*_{2} < *i*_{3}, we pick the pair of vectors *n*_{1} = *e*_{i1}– *e*_{i2}
and *n*_{2} = *e*_{i1}– *e*_{i3}, where the *e*_{i} are standard basis vectors in *R*^{n+1}.
For the Voronoi cell of the origin, the vertices of each particular (*n*–2)-boundary associated with this choice of *i*_{1}, *i*_{2}, and *i*_{3} will be
2^{n–2} points that
take all possible choices for the forms 1–*s* and –*s* for the remaining *n*–2 coordinates, while having one particular choice of those forms for the
*i*_{1}, *i*_{2}, and *i*_{3} coordinates.
The details of the six possibilities are as follows:

The six Voronoi (n–2)-boundaries for a given coordinate triple i_{1}, i_{2}, i_{3} | ||||||
---|---|---|---|---|---|---|

x_{i1} | x_{i2} | x_{i3} |
n_{1} · xn_{1} = e_{i1}– e_{i2} |
n_{2} · xn_{2} = e_{i1}– e_{i3} | Two vectors that give a dot product of 1 | |

n_{A} | n_{B} | |||||

1–s | 1–s | –s | 0 | 1 | n_{2} | n_{2} – n_{1} |

1–s | –s | 1–s | 1 | 0 | n_{1} | n_{1} – n_{2} |

–s | 1–s | 1–s | –1 | –1 | –n_{1} | –n_{2} |

1–s | –s | –s | 1 | 1 | n_{1} | n_{2} |

–s | 1–s | –s | –1 | 0 | –n_{1} | n_{2} – n_{1} |

–s | –s | 1–s | 0 | –1 | –n_{2} | n_{1} – n_{2} |

Why only six possibilities, not eight? We need to exclude vertices that are all 1–*s* or all –*s*, because the requirement for the coordinates to sum to zero would
force any such point to lie at the origin, not on the cell’s boundary.

The dot products in this table are for the Voronoi cell of the origin, but displacing the cell away from the origin can only add integers to the result. So we look for candidate points to be intersections of *P*
with Voronoi (*n*–2)-boundaries in general by examining the intersections of pairs of lines on *P* for which *n*_{1} and *n*_{2} respectively have integer dot products.

Now, if a point has an integer dot product with both *n*_{1} and
*n*_{2}, it will also have an integer dot product with *n*_{3} = *n*_{2} – *n*_{1} =
*e*_{i2}– *e*_{i3}. But we don’t need to look for intersections between the lines associated with *n*_{3} and those associated with
*n*_{1} or *n*_{2}, because we know that they will already be covered by the *n*_{1}, *n*_{2} intersections.
The (*n*+1)*n*(*n*–1)/6 pairs of hyperplane families that we generate from the (*n*+1)*n*(*n*–1)/6 choices of coordinate triples covers everything.

Given a point that lies on the intersection of our plane *P* with one of the pairs of hyperplanes described above, how can we tell whether it’s a “false positive”
or a point on a Voronoi (*n*–2)-boundary? And if it does lie on a Voronoi (*n*–2)-boundary, what are the coordinates of the three lattice points whose Voronoi cells share that
(*n*–2)-boundary?

For any given coordinate triple and associated pair of hyperplane families, and for each of the six possibilities in our table above, we can construct a set of *n*+1 linearly independent
vectors as follows. First, we include the two vectors from the last two columns in our table, both of which are guaranteed to have a dot product of exactly 1 with every point in our chosen
(*n*–2)-boundary of the Voronoi cell of the origin. Call these {*n*_{A}, *n*_{B}}.
Then we add *n*–2 vectors that all have a coordinate of 1 for the first of *i*_{1}, *i*_{2}, or *i*_{3} that takes the form 1–*s*,
0 for the other coordinates in the triple, and –1 in exactly one of the *n*–2 remaining coordinates. Call these vectors {*p*_{1}, … *p*_{n–2}}. Each of the
*p*_{j} will have a dot product of 1 with exactly half the vertices in our chosen (*n*–2)-boundary of the Voronoi cell of the origin: those who have a –*s* in the same
place as its –1; with the other vertices, the same vector will have a dot product of 0. What’s more, for *any* point on the chosen (*n*–2)-boundary the dot product with *all*
the *p*_{j} will lie between 0 and 1.
Finally, we throw in the diagonal vector ** d** = (1,1,…,1), which is orthogonal to everything in the lattice.

Given some candidate point ** x** that we found at the intersection of two of our lines on

We also have 0 ≤ (** x** –

The dot product of *L* with ** d** is zero, of course. Having specified the dot product of

But what if the first of our six possible choices was the wrong one? Or what if the point ** x** isn’t really on the boundary of any Voronoi cell?
It turns out that in either case, we get non-integer coordinates for our putative

The images below show projections of the triangular Delaunay 2-boundaries onto planes in *A*_{4}, *A*_{6}, *A*_{8} and *A*_{10}.
These tilings are known as “Tübingen triangular tilings” ^{[3]}.
For even *n*, we can use the planes previously described for
projections onto the hypercubic lattice one dimension higher.
The projections of the coordinates axes of *R*^{n+1}and their opposites form a 2(*n*+1)-pointed star in which positive
and negative axes alternate; the directions
of the edges of the Delaunay 2-boundaries, which are always a difference between coordinate vectors, project down to a 2(*n*+1)-pointed star that bisects the angles of the
coordinate-axes star, and so the tile edges lie on a set of *n*+1 distinct rays.

Delaunay 2-boundaries from A_{4} | Delaunay 2-boundaries from A_{6} |
---|---|

Delaunay 2-boundaries from A_{8} | Delaunay 2-boundaries from A_{10} |

If we wish to use an odd value for *n* we need to choose a different plane, because the plane we project onto for the hypercubic lattice doesn’t lie in the subspace that contains *A*_{n}.
A suitable choice is the plane spanned by:

= (1, cos(2π/(xn+1)), cos(4π/(n+1)), …, cos(2nπ/(n+1)))

= (0, sin(2π/(yn+1)), sin(4π/(n+1)), …, sin(2nπ/(n+1)))

The images below show projections of the Delaunay 2-boundaries onto this plane in *A*_{5}, *A*_{7}, *A*_{9} and *A*_{11}. [Note that the
*A*_{5} projection is exactly periodic, but the precise pattern will vary depending on the offset chosen for the affine plane.]
The projections of the coordinate axes of *R*^{n+1}and their opposites form an (*n*+1)-pointed star, with the projections
of the negative axes overlapping with the those of the positive axes. The projections of the edges of the Delaunay 2-boundaries form a 2(*n*+1)-pointed star, comprising both the
coordinate-axes star and bisectors of its angles, and so the tile edges again lie on *n*+1 distinct rays.

Delaunay 2-boundaries from A_{5} | Delaunay 2-boundaries from A_{7} |
---|---|

Delaunay 2-boundaries from A_{9} | Delaunay 2-boundaries from A_{11} |

What kind of tiling do we get from the *A*_{n} lattice if we choose to project the Voronoi 2-boundaries, rather than the Delaunay 2-boundaries, onto our plane *P*?
The Voronoi 2-boundaries in *A*_{n} are rhombuses found by projecting 2-faces of the hypercubic Voronoi cells of *Z*^{n+1} onto our subspace *S* of points whose coordinates sum to zero.
So long as the plane *P* lies in *S*, projecting those 2-boundaries from *A*_{n}
down to *P* will be the same as projecting the original hypercube 2-faces from *Z*^{n+1} down to *P*. For even *n* — and hence odd *n*+1 — and an offset of zero, the plane *P* we used for the
original deBruijn method
*does* lie in *S*, and it turns out that the tilings produced from *A*_{n} will be identical to those produced from *Z*^{n+1}.

Given that every Voronoi 2-boundary, *F*, in *A*_{n} is a projection onto *S* of *some* Voronoi 2-face, *F**, in *Z*^{n+1}, that claim probably isn’t too surprising,
but to see that the tilings really are exactly the same, we need to show that the detailed selection process, not just the set of available tiles, is identical.
This follows from the fact that we select Voronoi 2-boundaries in *A*_{n} to project on the condition that their dual Delaunay (*n*–2)-boundary intersects *P*.
Each Delaunay (*n*–2)-boundary, *D*, in *A*_{n} is itself the intersection of the subspace *S* with a Delaunay (*n*–1)-face, *D**, in *Z*^{n+1}, which in turn is
dual to a 2-face, *F**, in *Z*^{n+1} whose projection onto *S*, *F*, is the dual in *A*_{n} of *D*. So it makes no difference whether the duality operation is performed in
*Z*^{n+1} or *A*_{n}, and the criterion for selecting tiles works out identically, regardless.

rhombicFtiles project ontoF*PVoronoi project ontoSVoronoi onP←······················· 2-boundaries inA_{n}←······················· 2-faces inZ^{n+1}↑ ↑ | | | | | find dual | find dual | | | | selection ↓ ↓ points Delaunay Delaunay onP←······················· (n–2)-boundaries inA_{n}←····················· (n–1)-faces inZ^{n+1}intersect withPintersect withDSD*

For odd *n*, we can’t use the original choice of *P* since it doesn’t lie in *S*, but if we use the same plane as for the projection of the Delaunay 2-boundaries for odd *n*,
the result will be a rhombic tiling with half the order of rotational symmetry as the tiling obtained from the hypercube projection.

[1] N.G. deBruijn, “Algebraic theory of Penrose’s nonperiodic tilings of the plane, I, II”, *Nederl. Akad. Wetensch. Indag. Math.* **43** (1981) 39–52, 53–66. (Available online as a PDF.) I learnt about this method from the documentation for Eugenio Durand’s program Quasitiler, which generates the same kind of tilings interactively via forms submitted to a server.

[2] S. Steinberg, *Group Theory and Physics*, Cambridge University Press, 1994. Proposition 3.1, section 2.3.

[3] Peter Kramer, “Dual Canonical Projections”.

[4] Wikipedia article on the mathematician Boris Delaunay.

Greg Egan
science fiction writer

Applets Gallery / deBruijn (Technical Notes) / created Monday, 13 October 2008 / revised Wednesday, 24 December 2008