Barycentric subdivision


Barycentric subdivision

In geometry, the barycentric subdivision is a standard way of dividing an arbitrary convex polygon into triangles, a convex polyhedron into tetrahedra, or, in general, a convex polytope into simplices with the same dimension, by connecting the barycenters of their faces in a specific way.

The name is also used in topology for a similar operation on cell complexes. The result is topologically equivalent to that of the geometric operation, but the parts have arbitrary shape and size.

Both operations have a number of applications in mathematics and in geometric modeling, especially whenever some function or shape needs to be approximated piecewise, e.g. by a spline.

Barycentric subdivision of a simplex

The barycentric subdivision (henceforth "BCS") of an n-dimensional simplex S consists of ("n" + 1)! simplices. Each piece, with vertices v_0,v_1,dots,v_n, can be associated with a permutation p_0,p_1,dots,p_n of the vertices of S, in such a way that each vertex v_i is the barycenter of the points p_0,p_1,dots,p_i.

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) S consists of two smaller segments, each connecting one endpoint (0-dimensional face) of S to the midpoint of S itself (1-dimensional face).

The BCS of a triangle S divides it into six triangles; each part has one vertex v_2 at the barycenter of S, another one v_1 at the midpoint of some side, and the last one v_0 at one of the original vertices.

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

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

Barycentric subdivision of a convex polytope

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

This alternative definition can be extended to the BCS of an arbitrary n-dimensional convex polytope into a number of n-simplices. Thus the BCS of a pentagon P, for example, has 10 triangles: each triangle is associated to three elements F_0,F_1,F_2 of P — respectively, a corner of P, a side of P incident to that corner, and P itself.

Similarly the BCS of a cube consists of 48 tetrahedra, each of them associated to a sequence 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 F_0, 3 for F_1 (given F_0), and 2 for F_2 (given F_0,F_1).

Barycentric subdivision in topology

In topology, the barycentric subdivision is defined for a cell complex. Informally, such object can be thought of 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.

Applications

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.

Repeated barycentric subdivision

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 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 (n+1)!. BCS also multiplies the degree of each original vertex by n!, and the degree of each edge by (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.

Relative barycentric subdivision

For simplicial complexes Lsubset K one defines the relative barycentric subdivision K^* of K "modulo" L that consists of those simplixes with vertices v_0dots v_kB(S'_1)dots B(S'_l) associated to a sequence S_0 < cdots < S_k of proper faces of L and barycenters B(S'_i) of simplexes in Ksetminus L.

Clearly, L remains a subcomplex of K^*. Only the simplexes away from L shrink.

False barycentric subdivision

Sometimes the term "barycentric subdivision" is improperly used for any subdivision of a polytope P into simplices that have one vertex at the centroid of P, and the opposite facet on the boundary of P. While this property holds for the true barycentric subdivision, it also holds for other subdivisions which are not the BCS.

For example, if one makes a straight cut from the barycenter of a triangle to each of its three corners, one obtains a subdivision into three triangles. Generalizing this idea, one obtains a schema for subdividing an n-dimensional simplex into n+1 simplices. However, this subdivision is not the BCS.

ee also

*Polytope
*Cell complex
*spline
*Mesh generation
*Finite element method


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Barycentric — can refer to:In astronomy, * Barycentric coordinates (astronomy) are coordinates defined by the common center of mass of two or more bodies * Barycentric Dynamical Time was a time standard in the Solar system * Barycentric Coordinate Time is a… …   Wikipedia

  • Orbifold — This terminology should not be blamed on me. It was obtained by a democratic process in my course of 1976 77. An orbifold is something with many folds; unfortunately, the word “manifold” already has a different definition. I tried “foldamani”,… …   Wikipedia

  • Homeomorphism (graph theory) — In graph theory, two graphs G and G are homeomorphic if there is an isomorphism from some subdivision of G to some subdivision of G . If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted… …   Wikipedia

  • Clique complex — “Whitney complex” redirects here. For the Mississippi sports facility, see Davey Whitney Complex. Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Nerve (category theory) — In category theory, the nerve N(C) of a small category C is a simplicial set constructed from the objects and morphisms of C. The geometric realization of this simplicial set is a topological space, called the classifying space of the category C …   Wikipedia

  • Simplicial complex — In mathematics, a simplicial complex is a topological space of a particular kind, constructed by gluing together points, line segments, triangles, and their n dimensional counterparts (see illustration). Simplicial complexes should not be… …   Wikipedia

  • Cover (topology) — In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset. Formally, if is an indexed family of sets Uα, then C is a cover of X if Contents 1 Cover in t …   Wikipedia

  • List of algebraic topology topics — This is a list of algebraic topology topics, by Wikipedia page. See also: topology glossary List of topology topics List of general topology topics List of geometric topology topics Publications in topology Topological property Contents 1… …   Wikipedia

  • List of general topology topics — This is a list of general topology topics, by Wikipedia page. Contents 1 Basic concepts 2 Limits 3 Topological properties 3.1 Compactness and countability …   Wikipedia