Barycentric subdivision

Barycentric subdivision of the 2-simplex or triangle

The barycentric subdivision (henceforth BCS) of an ${\displaystyle n}$-dimensional simplex ${\displaystyle S}$ consists of (n + 1)! ${\displaystyle n}$-dimensional simplices. Each piece, with vertices ${\displaystyle v_{0},v_{1},\dots ,v_{n}}$, can be associated with a permutation ${\displaystyle p_{0},p_{1},\dots ,p_{n}}$ of the vertices of ${\displaystyle S}$, in such a way that each vertex ${\displaystyle v_{i}}$ is the barycenter of the points ${\displaystyle p_{0},p_{1},\dots ,p_{i}}$.

4 stages of barycentric subdivision

In particular, the BCS of a single point (a 0-dimensional simplex) consists of that point itself. The BCS of a line segment (1-simplex) ${\displaystyle S}$ consists of two smaller segments, each connecting one endpoint (0-dimensional face) of ${\displaystyle S}$ to the midpoint of ${\displaystyle S}$ itself (1-dimensional face).

The BCS of a triangle ${\displaystyle S}$ divides it into six triangles; each part has one vertex ${\displaystyle v_{2}}$ at the barycenter of ${\displaystyle S}$, another one ${\displaystyle v_{1}}$ at the midpoint of some side, and the last one ${\displaystyle v_{0}}$ at one of the original vertices.

The BCS of a tetrahedron ${\displaystyle S}$ divides it into 24 tetrahedra; each part has one vertex at the center of ${\displaystyle S}$, one on some face, one along some edge, and the last one at some vertex of ${\displaystyle S}$.

An important feature of BCS is the fact that the maximal diameter of an ${\displaystyle n}$-dimensional simplex shrinks at least by the factor ${\displaystyle {\frac {n}{n+1}}}$.[1]

Another way of defining the BCS of a simplex ${\displaystyle S}$ is to associate each part to a sequence ${\displaystyle F_{0},F_{1},\dots ,F_{n}}$ of faces of ${\displaystyle S}$, with increasing dimensions, such that ${\displaystyle F_{i}}$ is a facet of ${\displaystyle F_{i+1}}$, for ${\displaystyle i}$ from 0 to ${\displaystyle n-1}$. Then each vertex ${\displaystyle v_{i}}$ of the corresponding piece is the barycenter of face ${\displaystyle F_{i}}$.

This alternative definition can be extended to the BCS of an arbitrary ${\displaystyle n}$-dimensional convex polytope into a number of ${\displaystyle n}$-simplices. Thus the BCS of a pentagon ${\displaystyle P}$, for example, has 10 triangles: each triangle is associated to three elements ${\displaystyle F_{0},F_{1},F_{2}}$ of ${\displaystyle P}$ — respectively, a corner of ${\displaystyle P}$, a side of ${\displaystyle P}$ incident to that corner, and ${\displaystyle P}$ itself.

Similarly the BCS of a cube consists of 48 tetrahedra, each of them associated to a sequence ${\displaystyle F_{0},F_{1},F_{2},F_{3}}$ of nested elements — a vertex, an edge, a face, and the whole cube. Note that there are 8 choices for ${\displaystyle F_{0}}$, 3 for ${\displaystyle F_{1}}$ (given ${\displaystyle F_{0}}$), and 2 for ${\displaystyle F_{2}}$ (given ${\displaystyle F_{0},F_{1}}$).

Barycentric subdivision is an important tool in simplicial homology theory, where it is used as a means of obtaining finer simplicial complexes (containing the original ones, i.e. with more simplices). This in turn is crucial to the simplicial approximation theorem, which roughly states that one can approximate any continuous function between polyhedra by a (finite) simplicial map, given a sufficient amount of subdivision of the respective simplicial complexes whom they realize. Ultimately, this approximation technique is a standard ingredient in the proof that simplicial homology groups are topological invariants.[1][2]

A generalization of barycentric subdivision can also be defined for a cell complex. Informally, such an object can be thought of as an assemblage of one or more chunks of rubber (cells), each shaped like a convex polytope, which are glued to each other by their facets — possibly with much stretching and twisting.

The topological version of BCS replaces each cell by an assemblage of rubber simplices, likewise glued together by their facets and possibly deformed. The procedure is (1) select for each cell a deformation map that converts it into a geometric convex polytope, preserving its incidence and topological connections; (2) perform the geometric BCS on this polytope; and, then (3) map the resulting subdivision back to the original cells.

The result of barycentric subdivision, when viewed as an abstract simplicial complex, is an example of a flag complex. It has one vertex for every cell of the original cell complex and one maximal-dimensional cell for every flag (a collection of cells of different dimensions, all related to each other by inclusion) of the original cell complex.

The barycentric subdivision is chiefly used to replace an arbitrarily complicated convex polytope or topological cell complex by an assemblage of pieces, all of them of bounded complexity (simplices, in fact). A typical application is modeling the shape of a car body by a spline — a piecewise-defined polynomial function. The algebra of such functions becomes much simpler and easier to program if each "piece" is a "topological triangle", i.e. is attached to exactly three other pieces. However, a human user may find it more natural to design the shape by joining patches with more liberal shapes and topologies. Barycentric subdivision is a convenient way to convert that "user-friendly" model into a "computer-friendly" one.

When approximating a mathematical function or a surface by a spline, the accuracy of the approximation is usually determined by the piece size — the bigger the pieces, the larger the error. Thus it is often necessary to split large pieces into smaller ones, in order to achieve a prescribed accuracy.

In theory, BCS could be used for that purpose, since it has the property that the longest edge of any piece is smaller than the longest edge of the original polytope by a factor less than ${\displaystyle n/(n+1)}$. Therefore, by applying BCS sufficiently many times, the largest edge can be made as small as desired.

However, in practice BCS is not well-suited for that purpose. For one thing, each application after the first one multiplies the number of simplices by ${\displaystyle (n+1)!}$. BCS also multiplies the degree of each original vertex by ${\displaystyle n!}$, and the degree of each edge by ${\displaystyle (n-1)!}$. Moreover, the BCS will split all simplices, even those that are already small enough. Finally, each BCS stage also makes the simplices not only smaller but "skinnier", i.e. it tends to increase their aspect ratio (the ratio between the longest and shortest edge). For all these reasons, in practice one rarely applies more than one round of BCS, and other subdivision schemes are used instead.

For simplicial complexes ${\displaystyle L\subset K}$ one defines the relative barycentric subdivision ${\displaystyle K^{*}}$ of ${\displaystyle K}$ modulo ${\displaystyle L}$ that consists of those simplexes with vertices ${\displaystyle v_{0}\dots v_{k}B(S'_{1})\dots B(S'_{l})}$ associated to a sequence ${\displaystyle S_{0}<\cdots <S_{k}}$ of proper faces of ${\displaystyle L}$ and barycenters ${\displaystyle B(S'_{i})}$ of simplexes in ${\displaystyle K\setminus L}$.

Clearly, ${\displaystyle L}$ remains a subcomplex of ${\displaystyle K^{*}}$. Only the simplexes away from ${\displaystyle L}$ shrink.

• Apollonian network
• Cell complex
• Finite element method
• Mesh generation
• Polytope
• Spline