# Is there a dual graph of a 3D tessellation suitable for modeling packed cells in a biological tissue?

I'm a postdoc at Princeton university, working on a mathematical description and informatics of developing tissues based on microscopy images. In the 2D sense, a tissue looks like in vertex models or like some tessellation / a honeycomb, in which each polygon is a single biological cell (no spaces between cells, they're all touching each other). One of the things I'm trying to do is to study the adjacency relations between the cells by calculating the dual graph of the tessellation and running analyses on the induced adjacency matrix (in which each vertex is a cell and an edge exists between two neighboring cells). My assumption is that in the 2D case the graph is planar.

My difficulty is in the 3D case, which is composed of many finite volumes (like in FEM I guess?). In this case "my intuitive understanding" of the 'dual' is a graph in which each vertex corresponds to a single volume (i.e. a biological cell), an edge between two vertices in the dual graph represents a shared wall/surface (a biological membrane) in the original graph, and a face in the dual graph will exist between vertices if the corresponding volumes/cells meet in a certain point. Similarly to a planar graph in which no two edges can cross each other, here - in the 3D case - no two surfaces can cross each other.

The problem is that I wasn't able to find mathematical formulation for this kind of 'dual'... can you please address me to such literature / related keywords / algorithms?

Many thanks! Tomer

• – user133281 Aug 11 '17 at 20:03
• These kinds of dual meshes are well studied in the context of Voronoi diagrams and Delaunay triangulations, see e.g. voronoi.com/wiki/… – user856 Aug 11 '17 at 20:06
• Thanks @Rahul for the reply, but Voronoi diagrams are good if you want the algorithm to produce the partitioning of the 3D space based on a set of points, which gives convex shapes... here I already have the meshes - I extracted them from the images + they're not necessarily convex... – Tomer Aug 11 '17 at 20:12
• @Tomer: Voronoi diagram of a set of points is dual to the Delaunay triangulation of those points. Essentially, you can consider each cell to be represented by a point. The edges in the Voronoi diagram of those points correspond to cells sharing a cell wall, while the Delaunay triangulation corresponds to the vertices of the cell walls (if approximated as planes). – Nominal Animal Aug 11 '17 at 22:20
• What I meant is that there is a standard notion of a dual mesh obtained by creating vertices for each cell and vice versa. Applied to a Voronoi diagram (which is the context in which this is most often studied) this gives you the Delaunay triangulation, but you can also define the dual mesh for any reasonable tessellation of space, and it corresponds to the concept you want. Note that in 3D this is typically a tetrahedral mesh rather than just a graph (i.e. you care about triangles and tetrahedra, not just edges). – user856 Aug 11 '17 at 23:45

You can find quite a bit of a discussion and references in answers to this Mathoverflow question. However, that question only deals with dual complexes to triangulations, while you are interested in more general structures.

Here is a definition in the degree of generality you are interested in.

First one needs to a define a 3-dimensional tessellation. Start with a collection ${\mathcal D}$ of (bounded) 3-dimensional convex polyhedra ${\mathbb D}_k, k\in K$, where $K$ is an index set (possibly infinite). Each polyhedron in this collection has faces of various dimensions (for me, a face need not be 2-dimensional, for instance, vertices are 0-dimensional faces, edges are 1-dimensional faces, etc.).

A tessellation $T$ of a 3-dimensional manifold $M$ (just think of the 3-dimensional Euclidean space) modeled on ${\mathcal D}$, is a covering of $M$ by a union of (homeomorphic) copies $D_i$ (called "tiles") of the polyhedra ${\mathbb D}_k\in {\mathcal D}$ such that the following conditions are met:

1. For every two tiles $D_i, D_j$, their intersection is either empty or is a face (of some dimension $\le 3$) of both $D_i$ and $D_j$.

2. Each point in $M$ is covered only by finitely many tiles. (Edit: More precisely, each compact subset in $M$ intersects only finitely many tiles.)

Note. Sometimes, one imposes further restrictions on $T$, for instance a uniform upper bound on the number of tiles covering points in $M$, finiteness of the set of model tiles ${\mathcal D}$, etc.

Now, let's talk about the dual complex $T^*$ of $T$. This complex will be again a tessellation of $M$, but by copies of a different family of model polyhedral tiles.

a. The vertices of $T^*$ are the 3-dimensional faces of $T$. Less formally, you can think of placing one point $v_i= D_i^*$ in the interior of every tile $D_i$.

b. The edges of $T^*$ are the 2-dimensional faces of $T$. Less formally, you connect two (distinct) vertices $v_i, v_j\in T^*$ an edge whenever $D_i\cap D_j$ is a 2-dimensional face. (Note that this face is unique, see Condition 1.) Thus, every 2-dimensional face $F$ of $T$ results in an edge $F^*$ of of $T^*$.

c. Each edge $E$ of $T$ corresponds to a 2-dimensional face $E^*$ of $T^*$ defined as follows. Note that $E$ defines a 1-dimensional dual cycle (of the combinatorial length $n=n(E)$) in the dual graph that we constructed so far. The vertices of this cycle are the tiles in $T$ containing $E$. Now, you attach a 2-dimensional $n$-gon to each dual cycle as above. The result is a 2-dimensional complex, the union of faces of dimension $\le 2$ of $T^*$.

d. Lastly, one can define 3-dimensional faces $V^*$ of $T^*$ dual to the vertices $V$ of $T$. This takes a bit of work, as you need to verify that each $V$ determines a 2-dimensional sphere (equipped with its own tessellation) in $T^*$ (defined so far): The vertices of this tessellated sphere are the tiles of $T$ containing $V$, the edges of this sphere are the 2-dimensional faces of $T$ containing $V$, etc. One needs to check that this complex is indeed a 2-dimensional sphere and that, moreover, it can be realized as the boundary of some convex 3-dimensional polyhedron (the latter is the content of the Steinitzâ€™ Theorem). Furthermore, one needs to prove that the resulting polyhedral complex is a tessellation of the original manifold $M$. I will not do any this since, most likely, you do not care and it takes some effort.

Example. If $T$ is a Voronoi tiling, the dual complex $T^*$ is the Delanay "triangulation" (not really a triangulation, but a polyhedral complex, of course).

• Dear @Moishe, many thanks for the detailed formulation, this indeed goes exactly to where I wanted and I'll have to read in the coming days from the reference you sent me and about the Steinitz Theorem in order to see where I'm standing. I still have two issues to solve: 1. My shapes are not necessarily convex. Is there any generalization of what you wrote to general tiling? 2. In section 'c', why the union of faces is of dimension <=2 and not 2? Do you know of any implementations of this? e.g. an algorithm that constructs the dual for me? Many thanks, Tomer – Tomer Aug 14 '17 at 21:28
• @Tomer: 1. Nonconvexity of your model tiles does not matter much, as long as they are reasonable (nonconvex polyhedra in $R^3$ homeomorphic to the standard ball), you can prove that they are combinatorially equivalent to convex polyhedra (this is a corollary of the Steinitz Theorem). 2. Yes, you can say $=2$, it is not hard to check that there are no "naked" edges. Implementation - I do not know, you may have to write one yourself. Constructing the dial graph is easy algorithmically. – Moishe Kohan Aug 14 '17 at 21:45
• ...For the dual 2-faces, you basically solve the same problem in 1 dimension lower by drawing a small normal plane to an edge and observing its tiling by polygons. – Moishe Kohan Aug 14 '17 at 21:45
• Excellent, many thanks @Moishe, you helped me very much! – Tomer Aug 14 '17 at 22:05