This week I’ returning to a much more fundamental level and reviewing a paper on Voronoi graphs. These are a method of dividing up a space into triangles and my very early work on this blog was looking at random triangulations. This paper outlines an attempt to compute the curvature of a surface that didn’t work – that’s science, but we can build on that to find a method that does work.
The building blocks of a quantum theory of general relativity are
expected to be discrete structures. Loop quantum gravity is formulated using a basis of spin networks – wave functions over oriented graphs with coloured edges. Semiclassical states should,
however, reproduce the classical smooth geometry in the appropriate limits. The question of how to recover a continuous geometry from these discrete structures is, therefore, relevant in this context. The authors explore this problem from a rather general mathematical perspective using properties of Voronoi graphs to search for their compatible continuous geometries. They test the previously proposed methods for computing the curvature associated to such graphs and analyse the framework in detail in the light of the
General relativity describes the gravitational interaction as a consequence of the curvature of space-time, a 4-dimensional Lorentzian manifold. Given this geometric nature of gravity, it is expected that, when quantizing, a prescription for quantum
geometry would arise based on more fundamental discrete structures, rather than on smooth differential manifolds.
Loop quantum gravity (LQG) is a candidate theory for such a quantization of general relativity. The fundamental objects , thebasis of the kinematical Hilbert space are the so-called spin network states, which are defined as wave functions constructed over oriented coloured graphs. The building blocks of the theory are, therefore, discrete combinatorial structures – graphs. The theory provides quantum operators with a direct geometric interpretation, areas and volumes, which happen to have discrete eigenvalues, reinforcing the idea of a discrete geometry.
This perspective of considering abstract combinatorial structures as the fundamental objects of the theory is also adopted in other approaches to quantum gravity, such as spin-foam models, causal dynamical triangulations and causal sets . Also, the algebraic quantum gravity approach follows the same spirit of constructing a quantum theory of gravity from an abstract combinatorial structure.
Despite the variety of successful results obtained in LQG, the search for a semiclassical sector of the theory that would connect with the classical description given by general relativity in terms of a smooth manifold is still under research. An interesting question for the description of a semiclassical sector, given the combinatorial nature of the building blocks of the theory, would be whether there
is any correspondence between certain types of graphs and the continuous classical geometries. Tentatively, this would allow for the construction of gravitational coherent states corresponding to solutions of Einstein eld equations. While it is certainly true
that spin networks are a particular basis, and coherent states constructed from them might resemble nothing like a graph, some works seem to indicate that these graphs do actually represent the structure of space-time at the fundamental level.
This raises a very interesting question. How does the transition between a fundamental discrete geometry, encoded in a graph structure, and the continuous geometry we experience in every-day life happen? In particular, how does a one- dimensional structure give rise to 3-dimensional smooth space? A step towards answering these questions could be to think of these graphs as embedded in the
corresponding continuous geometries they represent. However, the situation is rather the opposite, being the smooth continuous structure an effective structure, emerging from the more fundamental discrete one, and not the other way around. Therefore,
a very relevant question to ask would be: Is there any information, contained in the abstract structure of a graph, that determine the compatible continuous geometries? Can we determine what types of manifolds a certain graph can be embedded in? One could even go further and ask whether any additional geometric information, like curvature, can be extracted from the very abstract structure of the graph itself. The goal is, therefore, to construct a unique correspondence between the discrete structures given by graphs, which in general do not carry geometric information, and smooth manifolds.
This problem was studied in the context of quantum gravity by Bombelli, Corichi and Winkler, who proposed a statistical method to compute the curvature of the manifold that would be associated to a certain class of graphs, based on Voronoi diagrams, giving a new step towards the semiclassical limit of LQG. Indeed, due to their properties, Voronoi diagrams appear naturally when addressing this kind of problems.They also play an important role in the discrete approach to general relativity provided by Regge calculus.
Voronoi diagrams are generated from a metric manifold and, by construction, contain geometric information from it. What was proposed, however, is to throw away all additional geometric information and to keep only the abstract structure of
the one-dimensional graph that forms the skeleton of the Voronoi diagram. Then, the task is to study if there are any imprints of the original geometry which remain in this abstract graph structure. Although the work is somewhat preliminary and, for the
most part, restricted to 2-dimensional surfacesz, it tackles very interesting questions and explores a novel path towards a semiclassical regime in LQG. The results obtained could also provide a useful tool for the causal dynamical triangulations approach.
Curvature associated to a graph
A Voronoi diagram is constructed in the following way. For a set of points -seeds, on a metric space, each highest-dimensional cell of the Voronoi diagram contains only one seed, and comprises the region of space closer to that one seed than to any of the others. Then, co-dimension n cells are made by sets of points equidistant to n + 1 seeds, e.g., in 2 dimensions, the edges (1-dimensional cells) of the Voronoi diagram are the lines separating two of these regions, and are therefore equidistant to two seeds. In the same way, vertices (0-dimensional cells) are equidistant to three seeds.
Therefore, except in degenerate situations which are avoided by randomly sprinkling the seed, the valence of all vertices in a D-dimensional Voronoi diagram is D + 1. Another interesting property of Voronoi diagrams is that their dual graph is the so- called Delaunay triangulation, whose vertices are the Voronoi seeds. By construction, for a given set of seeds on a metric space the corresponding Voronoi diagram is uniquely defined.
The starting point is to consider a given surface on which we randomly sprinkle a set of points, that will be the seeds
for the Voronoi construction. A Voronoi cell-complex is constructed, containing zero, one, and two-dimensional cells (vertices, edges and faces). We keep, then, the abstract structure of the one-dimensional graph encoded, for instance, in an adjacency matrix. We are, thus, left with an abstract graph.
All vertices of the Voronoi graph are tri-valent. This gives rise
to the following relation between the total number V of vertices in the graph and the total number of edges E:
since every vertex is shared by three edges and every edge contains two vertices. We will also use the definition of the Euler-Poincare characteristic χ in the two-dimensional case
where F is the total number of faces in the graph (that equals the number of seeds). Finally, one can define the number p of sides of a face (its perimeter in the graph). Taking into account that every edge is shared by two faces, the average p over a set of faces satisfies
The following expression for the Euler-Poincare characteristic χ
can be obtained
in terms of the total number of faces F and the average number of sides of the faces p.
On the other hand, if there is a manifold M associated to the Voronoi diagram, this manifold should have the same topology as the diagram. The Gauss-Bonnet theorem can be used then to relate χ with the integral of the curvature over the manifold. If M is a manifold without boundary (like a sphere), the theorem takes the form
where dA is the area measure and R is the Ricci scalar.
Assume that the region of the graph one is looking at is small enough
so that the curvature can be considered constant. In that case
where As is the total surface area of the sphere.
this formula can also be applied to the sphere patch by defining a density of faces ρ= F=As = Fp =Ap , where Fp and Ap are respectively the number of faces and area of the patch.
Implementation and results
Conclusions and outlook
The problem of reconstructing a continuous geometry starting from a discrete, more fundamental combinatorial structure, like a graph, is interesting for a wide range of research fields. In the case of LQG theory whose Hilbert space is constructed using wave functions defined over graphsthe solution to this problem could provide interesting hints on the construction of semiclassical states, moving toward a connection with classical solutions of the Einstein equations.
In this article the authors discussed and implemented the method proposed to compute the curvature of a manifold from an abstract Voronoi graph associated to it. By making use of some topological arguments involving the Gauss-Bonnet theorem, a method to statistically compute the curvature in terms of the average number of sides of the faces in the graph is suggested. They tested this
method for the simplest geometries: the unit sphere – constant positive curvature and the plane – zero curvature. They
found highly unsatisfactory results for the value of the curvature in both cases.