Voronoi Diagrams and Delaunay Triangulations:

Ubiquitous Siamese Twins

Thomas M. Liebling and Lionel Pournin

2010 Mathematics Subject Classification: 01A65, 49-03, 52C99, 68R99, 90C99, 70-08, 82-08, 92-08 Keywords and Phrases: Voronoi, Delaunay, tesselations, triangulations, flip-graphs

1 Introduction

Concealing their rich structure behind apparent simplicity, Voronoi diagrams and their dual Siamese twins, the Delaunay triangulations constitute remarkably powerful and ubiquitous concepts well beyond the realm of mathematics. This may be why they have been discovered and rediscovered time and again. They were already present in fields as diverse as astronomy and crystallography centuries before the birth of the two Russian mathematicians whose names they carry. In more recent times, they have become cornerstones of modern disciplines such as discrete and computational geometry, algorithm design, scientific computing, and optimization.

To fix ideas, let us define their most familiar manifestations (in the Euclidean plane) before proceeding to a sketch of their history, main properties, and applications, including a glimpse at some of the actors involved.

A Voronoi diagram induced by a finite set A of sites is a decomposition of the plane into possibly unbounded (convex) polygons called Voronoi regions, each consisting of those points at least as close to some particular site as to the others.

The dual Delaunay triangulation associated to the same set A of sites is obtained by drawing a triangle edge between every pair of sites whose corresponding Voronoi regions are themselves adjacent along an edge. Boris Delaunay has equivalently characterized these triangulations via the empty circle property, whereby a triangulation of a set of sites is Delaunay iff the circumcircle of none of its triangles contains sites in its interior.

These definitions are straightforwardly generalizable to three and higher dimensions.

Figure 1: From left to right: Johannes Kepler, René Descartes, Carl Friedrich Gauss, Johann Peter Gustav Lejeune Dirichlet, John Snow, Edmond Laguerre, Georgy Feodosevich Voronoi, and Boris Nikolaevich Delone. The first seven pictures have fallen in the public domain, and the last one was kindly provided by Nikolai Dolbilin.

One may wonder what Voronoi and Delaunay tessellations have to do in this optimization histories book. For one they are themselves solutions of optimization problems. More specifically, for some set of sites A, the associated Delaunay triangulations are made up of the closest to equilateral triangles; they are also the roundest in that that they maximize the sum of radii of inscribed circles to their triangles. Moreover, they provide the means to describe fascinating energy optimization problems that nature itself solves [37, 18]. Furthermore Voronoi diagrams are tools for solving optimal facility location problems or finding the k-nearest and farthest neighbors. Delaunay triangulations are used to find the minimum Euclidean spanning tree of A, the smallest circle enclosing the set, and the two closest points in it. Algorithms to construct Voronoi diagrams and Delaunay triangulations are intimately linked to optimization methods, like the greedy algorithm, flipping and pivoting, divide and conquer [31]. Furthermore the main data structures to implement geometric algorithms were created in conjunction with those for Voronoi and Delaunay tessellations.

Excellent sources on the notions of Voronoi diagrams and Delaunay triangulations, their history, applications, and generalizations are [12, 2, 3, 28].

2 A glance at the past

The oldest documented trace of Voronoi diagrams goes back to two giants of the Renaissance: Johannes Kepler (1571 Weil der Stadt – 1630 Regensburg) and René Descartes (1596 La Haye en Touraine, now Descartes – 1650 Stockholm). The latter used them to verify that the distribution of matter in the universe forms vortices centered at fixed stars (his Voronoi diagram’s sites), see figure 2 [9]. Several decades earlier, Kepler had also introduced Voronoi and Delaunay tessellations generated by integer lattices while studying the shapes of snowflakes and the densest sphere packing problem (that also led to his famous conjecture). Two centuries later, the British physician John Snow (1813 York – 1858 London) once more came up with Voronoi diagrams in yet a totally different context. During the 1854 London cholera outbreak, he superposed the map of cholera cases and the Voronoi diagram induced by the sites of the water Figure 2: Left: a Voronoi diagram drawn by René Descartes [9], and its recalculation displaying yellow Voronoi regions, with the dual Delaunay triangulation in blue. Right: The Voronoi region centered on Broad Street pump, sketched by John Snow [33] using a dotted line.

pumps, see figure 2 [33], thereby identifying the infected pump, thus proving that Voronoi diagrams can even save lives. His diagram is referred to in [26] as the most famous 19th century disease map and Snow as the father of modern epidemiology.

Around the time when John Snow was helping to fight the London cholera epidemic, the eminent mathematician Johann Peter Gustav Lejeune Dirichlet (1805 Düren – 1859 Göttingen) was in Berlin, producing some of his seminal work on quadratic forms. Following earlier ideas by Kepler (see above) and Carl Friedrich Gauss (1777 Braunschweig -1855 Göttingen), he considered Voronoi partitions of space induced by integer lattice points as sites [10]. Therefore, to this day, Voronoi diagrams are also called Dirichlet tesselations. Thirty years later, Georges Voronoi (1868 Zhuravky – 1908 Zhuravky) extended Dirichlet’s study of quadratic forms and the corresponding tessellations to higher dimensions [34]. In the same paper, he also studied the associated dual tessellations that were to be called Delaunay triangulations. Voronoi’s results appeared in Crelle’s journal in 1908, the year of his untimely death at the age of 40. He had been a student of Markov in Saint Petersburg, and spent most of his career at the University of Warsaw where he had become a professor even before completing his PhD thesis. It was there that young Boris Delone – Russian spelling of the original and usual French Delaunay – (1890 Saint Petersburg – 1980 Moscow) got introduced to his father’s colleague Voronoi. The latter made a lasting impression on the teenager, profoundly influencing his subsequent work [11]. This may have prompted the Mathematical Genealogy Project [25] to incorrectly list Voronoi as Delone’s PhD thesis advisor just as they did with Euler and his “student” Lagrange. Actually, Lagrange never obtained a PhD, whereas Delone probably started to work on his thesis, but definitely defended it well after Voronoi’s death. Delone generalized Voronoi diagrams and their duals to the case of irregularly placed sites in d-dimensional space.

He published these results in a paper written in French [7], which he signed Delaunay. During his long life spanning nearly a whole century, he was not only celebrated as a brilliant mathematician, but also as one of Russia’s foremost mountain climbers. Indeed, aside from his triangulations, one of the highest peaks (4300 m) in the Siberian Altai was named after him too. For a detailed account of Boris Delaunay’s life, readers are referred to the beautiful biography written by Nikolai Dolbilin [11]. Delaunay’s characterization of his triangulations via empty circles, respectively empty spheres in higher dimensions later turned out to be an essential ingredient of the efficient construction of these structures (see in section 4 below).

At least half a dozen further discoveries of Voronoi diagrams in such miscellaneous fields as gold mining, crystallography, metallurgy, or meteorology are recorded in [28]. Oddly, some of these seemingly independent rediscoveries actually took place within the same fields of application. In 1933, Eugene Wigner (1902 Budapest – 1995 Princeton) and Frederick Seitz (1911 San Francisco – 2008 New York City) introduced Voronoi diagrams induced by the atoms of a metallic crystal [36]. Previously Paul Niggli (1888 Zofingen - 1953 Zürich) [27] and Delaunay [6] had studied similar arrangements and classified the associated polyhedra. To this day, physicists indifferently call the cells of such Voronoi diagrams Wigner-Seitz zones, Dirichlet zones, or domains of action.

It should be underlined that, over the last decades, Voronoi diagrams and Delaunay triangulations have also made their appearance in the fields of scientific computing and computational geometry where they play a central role. In particular, they are increasingly applied for geometric modeling [4, 24, 1, 32] and as important ingredients of numerical methods for solving partial differential equations.

3 Generalizations and applications

As described by Aurenhammer [3], ordinary Voronoi diagrams can be interpreted as resulting from a crystal growth process as follows: “From several sites fixed in space, crystals start growing at the same rate in all directions and without pushing apart but stopping growth as they come into contact. The crystal emerging from each site in this process is the region of space closer to that site than to all others.”

A generalization in which crystals do not all start their growth simultaneously was proposed independently by Kolmogorov in 1937 and Johnson and Mehl in 1939 [20]. In the planar case, this gives rise to hyperbolic region boundaries.

On the other hand, if the growth processes start simultaneously but progress at different rates, they yield the so-called Apollonius tessellations, with spherical region boundaries, resp. circular in the plane. These patterns can actually be observed in soap foams [35]. Apollonius tesselations are in fact multiplicatively weighted Voronoi diagrams in which weights associated to each site multiply the corresponding distances.

These types of Voronoi diagram patterns are also formed by mycelia as they Figure 3: Simulated hyphal growth. Left: Initially ten numerical spores using self-avoidance grow and occupy the surrounding two-dimensional medium, defining a Voronoi diagram. Right: Hyphal wall growth model using piecewise flat surfaces and Voronoi diagrams thereon.

evolve from single spores and compete for territory (see figure 3). The mycelium is the part of the fungus that develops underground as an arborescence whose successive branches are called hyphae [18]. Certain molds actually exhibit an essentially planar growth. Hyphal growth in its interaction with the surrounding medium can be modeled using the assumption that as they grow, hyphae secrete a substance that diffuses into the medium, whose concentration they can detect and try to avoid, thereby both avoiding each other and also accelerating their own circularization. Thus the relationship to Voronoi diagrams becomes apparent. At a more microscopic level, growth of hyphal walls can be simulated by modeling them as piecewise flat surfaces that evolve according to biologically and mechanically motivated assumptions [18]. Therein, Delaunay triangulations and Voronoi diagrams on piecewise linear surfaces are useful tools.

Laguerre diagrams (or tesselations) are additively weighted Voronoi diagrams already proposed by Dirichlet [10] decades before Edmond Nicolas Laguerre (1834 Bar-le-Duc – 1886 Bar-le-Duc) studied the underlying geometry. In the early nineteen eighties, Franz Aurenhammer, who calls Laguerre diagrams power diagrams, wrote his PhD thesis about them, resulting in the paper [2], which to this date remains an authoritative source on the subject. They had previously also been studied by Laszlò Fejes Toth (1915 Szeged – 2005 Budapest) in the context of packing, covering, and illumination problems with spheres [14, 15].

Power diagrams yield a much richer class of partitions of space into convex cells than ordinary Voronoi diagrams. They are induced by a set of positively weighted sites, the weights being interpreted as the squared radii of spheres centered at the sites. The region induced by some weighted site i.e. sphere consists of those points whose power with respect to that sphere is smaller or equal to that with respect to all others [15, 12, 3]. Note that some spheres may generate an empty region of the power diagram, which has to do with Figure 4: The growth of a polycrystal modeled using dynamic power diagrams. From left to right, larger monocrystalline regions grow, eating up the smaller ones

the fact that the power with respect to a sphere is not a metric since it can be negative. The dual triangulations of power diagrams are called weighted Delaunay triangulations, or regular triangulations. These objects can be defined in Euclidean spaces of arbitrary dimension.

Laguerre tessellations turn out to be very powerful modeling tools for some physical processes, as for instance metal solidification or ceramics sintering. During the production of ceramic materials, a polycrystalline structure forms starting from, say alumina powder (Al_{2}SO_{3}). With the help of time, heat and pressure, the polycristal, which is a conglomerate of unaligned crystalline cells undergoes a process in which larger cells grow at the expense of the smaller ones (see figure 4). It has been shown that at any point in time, three-dimensional Laguerre tessellations are adequate representations of such self-similar evolving polycrystalline structures [37]. Their growth is driven by surface energy minimization, the surface being the total surface between adjacent crystalline regions. Not only is it easy to compute this surface in the case of Laguerre tessellations, but also its gradient when the parameters defining the generating spheres evolve. With the use of the chain rule, it is thus possible to set up motion equations for the generating spheres of the Laguerre tessellation, that reflect the energy minimization. They remain valid as long as there is no topological transformation of this tesselation (such a transformation consisting either in a neighbor exchange or a cell vanishing). Whenever such a transformation takes place, the tessellation and motion equations have to be updated and integrated until detection of the following topological transformation, and so on. This process can go on until the polycrystalline structure becomes a mono-crystal. The growth of foams can be modeled in a similar fashion. All this has been implemented in two and three dimensions for very large cell populations, and periodic boundary conditions. The latter imply a generalization of Laguerre tessellations to flat tori. Such simulations remain the only way to follow the dynamic phenomena taking place in the interior of three-dimensional polycrystals.

Another application, close to that in [15] comes up in the numerical simulation of granular media where the behavior of assemblies of macroscopic grains like sand, corn, rice, coke is studied by replicating trajectories of individual grains. Increased computing power in conjunction with the power supplied by mathematics now allows simulation of processes involving hundreds of thousands of grains. The main challenge involved is threefold:

• realistic modeling of individual grain shapes beyond simple spheres;

• realistic physical modeling of the interaction between contacting bodies;

• efficient contact detection method.

The latter is where Delaunay triangulations are used. Indeed, they yield methods that permit to efficiently test contacts within very large populations of spherical grains. The underlying property being that whenever two spherical grains are in contact, their centers are linked by an edge of the associated regular triangulation. Using this method requires an efficient and numerically stable updating procedure of regular triangulations associated to dynamically evolving sites. Using sphero-polyhedral grains (a sphero-polyhedron is the Minkowski sum of a sphere with a convex polyhedron), this procedure can be straightforwardly generalized to such quite arbitrarily shaped non-spherical grains. With this approach, large-scale simulations of grain crystallization, mixing and unmixing, and compaction processes in nature and technology have been performed (see figure 5).

In principle, Voronoi diagrams can be defined for sets of sites on arbitrary metric spaces, such as giraffe and crocodile skins, turtle shells, or discrete ones such as graphs with positive edge weights satisfying the triangle inequality, giving rise to classical graph optimization problems.

4 Geometry and algorithms

The previously introduced d-dimensional power diagrams and the associated regular triangulation can also be viewed as the projections to ℝ^{d} of the lower boundaries of two convex (d+1)-dimensional polyhedra. In fact, this projective property can be used as a definition. In other words, a subdivision of ℝ^{d} into convex cells is a power diagram if and only if one can define a piecewise-linear convex function from ℝ^{d} to ℝ whose regions of linearity are the cells of the diagram (see [3], and the references therein). The same equivalence is also true for regular triangulations, where the given function is defined only on the convex hull of the sites and has simplicial regions of linearity.

In this light, regular triangulations can be interpreted as a proper subclass of the power diagrams. In other words, they are the power diagrams whose faces are simplices. Note that by far, not every partition of space into convex polyhedral cells can be interpreted as an ordinary Voronoi diagram. As shown by Chandler Davis [5], power diagrams constitute a much richer class of such Figure 5: Granular media simulation using regular triangulations. Left: All the contacts occurring in a set of two-dimensional discs are detected by testing the edges of a regular triangulation. This triangulation is depicted in black and its dual power diagram in light gray. Right: Simulation of the output of a funnel with very low friction, involving about 100 000 spherical particles. Contacts are tested using regular triangulations.

partitions. In fact, in dimension higher than 2, every simple convex partition is a power diagram. In analogy to simple polytopes, simple partitions consist of regions such that no more than d of them are adjacent at any vertex. In this context it is interesting to note that Kalai has shown that the Hasse diagram of a simple polytope can actually be reconstructed from its 1-skeleton [22]. Recall that the 1-skeleton of a polytope is the graph formed by its vertices and edges. Hence the same also holds for simple power diagrams.

An important implication of the projection property is that software for convex hull computation can be directly used to compute power diagrams [16]. Since the nineteen-seventies, many other specialized algorithms have been developed that compute these diagrams. Today, constructing a 2-dimensional Voronoi diagram has become a standatd homework exercise of every basic course in algorithms and data structures. In fact, the optimal divide and conquer algorithm by Shamos can be considered as one of the cornerstones of modern computational geometry (see [31]). In this recursive algorithm of complexity O(n log(n)), the set of n sites is successively partitioned into two smaller ones, whereupon their corresponding Voronoi diagrams are constructed and sewn together. Unfortunately, no generalization of this algorithm to higher dimensions or to power diagrams is known.

Several algorithms that compute regular triangulations are known, though, and by duality, one can easily deduce the power diagram generated by a set of weighted sites from its associated regular triangulation. Note in particular Figure 6: Four types of flips in 2-dimensions (left) and 3-dimensions (right). The flips at the top insert or remove edge {b, d} and the flips at the bottom insert or remove vertex d.

that one obtains the Hasse diagram of a power diagram by turning upside down that of the corresponding regular triangulation.

Plane Delaunay triangulations can be constructed using flip algorithms such as first proposed by Lawson [23]. While their worst-case complexity is O(n^{2}), in practical cases they are not only a lot faster than that, but also have other desirable numerical properties. Consider a triangulation of a set of n points in the plane. Whenever two adjacent triangular cells form a convex quadrilateral, one can find a new triangulation by exchanging the diagonals of this quadrilateral. Such an operation is called an edge flip and the flipped edges are called flippable (see figure 6). A quadrilateral with a flippable edge is called illegal if the circumcircle of one of its triangles also contains the third vertex of the other in its interior. Otherwise, it is legal. It is easy to see that a flip operation on an illegal quadrilateral makes it legal and vice-versa. The simple algorithm that consists in flipping all illegal quadrilaterals to legality, one after the other in any order, always converges to a Delaunay triangulation. Testing the legality of a quadrilateral amounts to checking the sign of a certain determinant. Along with the flip operation, this determinant-test generalizes to higher dimensions [8]. Moreover, the aforementioned flip-algorithm can be generalized to regular triangulations – with weighted sites – by simply introducing an additional type of flip to insert or delete (flip in/flip out) vertices (see figure 6) and testing a slightly modified determinant. Unfortunately, in this case, this algorithm can stall without reaching the desired solution. For rigorous treatment of flips using Radon’s theorem on minimally affinely dependent point sets, see [8].

The incremental flip algorithm [19] for the construction of regular triangulations is a method that always works. Therein, a sequence of regular triangulations is constructed by successively adding the sites in an arbitrary order. An initial triangulation consists of a properly chosen sufficiently large artificial triangle that will contain all given sites in its interior and will be removed once the construction is finished. At any step a new site is flipped in (see figure 6), subdividing its containing triangle into three smaller ones, the new triangulation possibly not being a Delaunay triangulation yet. However, as shown in [19], it is always possible to make it become one by a sequence of flips. This incremental flip algorithm has been generalized in [13] to the construction of regular triangulations in arbitrary dimension.

Any pair of regular triangulations of a given set of sites is connected by a sequence of flips [8]. If at least one of the triangulations is not regular, this need not be the case. This issue gives rise to interesting questions that will be the mentioned in this last paragraph. Consider the graph whose vertices are the triangulations of a finite d-dimensional set of sites A, with an edge between every pair of triangulations that can be obtained from one another by a flip. What Lawson proved [23] is that this graph, called the flip-graph of A, is connected when A is 2-dimensional. The subgraph induced by regular triangulations in the flip-graph of A is also connected (it is actually isomorphic to the 1-skeleton of the so-called secondary polytope [17]). Furthermore, so is the larger subgraph induced in the flip-graph of A by triangulations projected from the boundary complex of (d + 2)-dimensional polytopes [29]. To this date, it is not known whether the flip graphs of 3- or 4-dimensional point sets are connected, and point sets of dimension 5 and 6 were found whose flipgraph is not connected [8] (the latter having a component consisting of a single triangulation!). Finally, it has been shown only recently that the flip-graph of the 4-dimensional cube is connected [30].

5 Conclusion

This chapter has described a few milestones on a journey that started when Kepler and Descartes used what were to become Voronoi diagrams to study the universe from snowflakes to galaxies. These diagrams and their dual Delaunay triangulations have meanwhile become powerful engineering design, modeling, and analysis tools, have given rise to many interesting questions in mathematics and computer science, and have helped solving others (in particular, Kepler’s conjecture! See for instance [21])). The journey is by far not ended and will certainly lead to still other fascinating discoveries.

References

[1] N. Amenta, S. Choi, R. K. Kolluri, The power crust, unions of balls, and the medial axis transform, Comput. Geom. 19, 127–153 (2001)

[2] F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM J. Comput. 16, 1, 78–96 (1987)

[3] F. Aurenhammer, Voronoi diagrams – a survey of a fundamental geometric data structure, ACM Computing Surveys 23, 3, 345–405 (1991)

[4] CGAL, Computational Geometry Algorithms Library, http://www.cgal.

org

[5] C. Davis, The set of non-linearity of a convex piecewise-linear function, Scripta Math. 24, 219–228 (1959)

[6] B.N. Delaunay, Neue Darstellung der geometrischen Kristallographie, Z. Kristallograph. 84, 109–149 (1932)

[7] B. N. Delaunay, Sur la sphère vide, Bull. Acad. Science USSR VII: Class. Sci. Math., 193–800 (1934)

[8] J. A. de Loera, J. Rambau, F. Santos, Triangulations: structures for algorithms and applications, Algorithms and Computation in Mathematics 25, Springer (2010)

[9] R. Descartes, Principia philosophiae (1644)

[10] G. L. Dirichlet, Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40, 209–227 (1850)

[11] N. P. Dolbilin, Boris Nikolaevich Delone (Delaunay): Life and Work, Proceedings of the Steklov Institute of Mathematics 275, 1–14 (2011)

[12] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, Heidelberg (1987)

[13] H. Edelsbrunner, N. R. Shah, Incremental topological flipping works for regular triangulations, Algorithmica 15, 223–241 (1996)

[14] L. Fejes Tóth, Regular figures, Pergamon Press (1964)

[15] L. Fejes Tóth, Illumination of convex discs, Acta Math. Aced. Scient. Hung. 29, 355–360 (1977)

[16] K. Fukuda, Polyhedral Computations, MOS-SIAM Series in Optimization, 2012 (to appear)

[17] I. M. Gel’fand, M. M. Kapranov and A. V. Zelevinsky, Discriminants of polynomials of several variables and triangulations of Newton polyhedra, Leningrad Math. J. 2, 449–505 (1990)

[18] C. Indermitte, Th. M. Liebling, M. Troyanov, H. Clémençon, Voronoi diagrams on piecewise flat surfaces and an application to biological growth, Theoretical Computer Science 263, 263–274 (2001)

[19] B. Joe, Construction of three-dimensional Delaunay triangulations using local trandformations, Comput. Aided Geom. Design 8, 123–142 (1991)

[20] W. A. Johnson, R.F. Mehl, Reaction kinetics in processes of nucleation and growth, Trans. Am. Instit. Mining Metall. A. I. M. M. E. 135, 416–458 (1939)

[21] M. Joswig, From Kepler to Hales, and back to Hilbert, this volume.

[22] G. Kalai, A simple way to tell a simple polytope from its graph, J. Comb. Theor. Ser. A 49, 381–383 (1988)

[23] C. L. Lawson, Transforming triangulations, Discrete Math. 3, 365–372 (1972)

[24] LEDA, Library of Efficient Data Types and Algorithms, http://www.

    algorithmic-solutions.com

[25] The Mathematics Genealogy Project: http://www.genealogy.ams.org

[26] M. S. Meade, Conceptual and Methodological Issues in Medical Geography, Chapel Hill (1980)

[27] R. Niggli, Die topologische Strukturanalyse, Z. Kristallograph. 65 391–415 (1927)

[28] A. Okabe, B. Boots, K. Sugihara,S. N. Chiu, Spatial Tessellations, Wiley (2000)

[29] L. Pournin, A result on flip-graph connectivity, Adv. Geom. 12, 63–82 (2012)

[30] L. Pournin, The flip-graph of the 4-dimensional cube is connected, arXiv:1201.6543v1 [math.MG] (2012)

[31] M. I. Shamos, D. Hoey, Closest-point problems. In Proceedings ot the 16th Annual IEEE Symposium on FOCS, 151–162 (1975)

[32] J. R. Shewchuk, General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties, Discrete Comput. Geom. 39, 580–637 (2008)

[33] J. Snow, Report on the Cholera Outbreak in the Parish of St. James, Westminster, during the Autumn of 1854 (1855)

[34] G. Voronoi, Nouvelles applications des paramètres continus à a théorie des formes quadratiques, J. Reine Angew. Math. 134, 198–287 (1908)

[35] D. Weaire, N. Rivier, Soap, cells, and statistics-random patterns in two dimensions, Contemp. Phys. 25, 59–99 (1984)

[36] E. Wigner, F. Seitz, On the constitution of metallic sodium, Phys. Rev. 43, 804–810 (1933)

[37] X. J. Xue, F. Righetti, H. Telley, Th. M. Liebling, A. Mocellin, The Laguerre model for grain growth in three dimensions, Phil. Mag. B 75 (1997) 567–585.

Thomas M. Liebling EPFL Basic Sciences Mathematics MA A1 417

Station 8 1015 Lausanne Switzerland

thomas.liebling@epfl.ch

Lionel Pournin

EFREI

30–32 avenue de la République 94800 Villejuif France

                                 lionel.pournin@efrei.fr

432

Documenta Mathematica · Extra Volume ISMP (2012)