{"id":225,"date":"2017-04-14T14:11:27","date_gmt":"2017-04-14T22:11:27","guid":{"rendered":"https:\/\/matsguru.com\/?p=225"},"modified":"2017-04-14T14:11:27","modified_gmt":"2017-04-14T22:11:27","slug":"bistellar-simplification","status":"publish","type":"post","link":"https:\/\/matsguru.com\/?p=225","title":{"rendered":"Bistellar simplification"},"content":{"rendered":"

In the late 80s Udo Pachner introduced the idea of a bistellar move<\/a> which can modify the triangulation of an object (simplicial manifold) without changing its fundamental properties (topological type). About a decade later, Frank Lutz implemented bistellar_simplification<\/a> as a tool to classify objects by their topological type using a simulated annealing strategy. Later, Niko Witte wrote a C++ implementation of Frank’s code for polymake<\/a>, which considerably sped up the computation. I, then, spent several (loong) months trying to improve Niko’s code so that it can be used to recognize our\u00a0spheres<\/a>.<\/p>\n

The\u00a02-dimensional version of a bistellar move is well known in the graphics community, though it is usually called\u00a0by a different name: edge flips. It can\u00a0be used to find “nice” triangle meshes of some domain, which may, for example, be applied to finite element-type computations.<\/p>\n

The idea of the bistellar move is simple. We’ll be using some terminology from here<\/a>. Let’s start with\u00a0a simplicial complex [latex]K[\/latex] of dimension [latex]d[\/latex] and a simplex [latex]\\sigma \\in K[\/latex] of dimension [latex]0\\le i \\le d[\/latex]. (Technically, [latex]K[\/latex] should be a closed combinatorial manifold.)<\/p>\n

A bistellar [latex]i[\/latex]-move is [latex]\\Phi_K(\\sigma) = K – \\text{star}(\\sigma,K) + \\tau \\ast \\partial \\sigma[\/latex], where [latex]\\tau[\/latex] is a [latex](d-i)[\/latex]-simplex NOT\u00a0in [latex]K[\/latex] such that [latex]\\partial \\tau = \\text{link}(\\sigma,K)[\/latex]. The move is only valid if a [latex]\\tau[\/latex] satisfying these properties exists.<\/p>\n

The animated gif below shows some bistellar moves in action. You can see why the algorithm is called a bistellar simplification — we can change the triangle mesh to have fewer triangles.<\/p>\n

\"\"<\/p>\n

Consider an abstract graph whose nodes are simplicial complexes\u00a0which are connected by an edge if there exists a single bistellar move to get from one complex to the other. This graph is known as the bistellar flip graph or Pachner graph. The bistellar_simplification algorithm is equivalent to a random walk on this infinite graph which attempts to identify the topological type of the input complex [latex]K[\/latex] by lowering the [latex]f[\/latex]-vector of [latex]K[\/latex].<\/p>\n

Tracking the\u00a0[latex]f[\/latex]-vector is the cheapest way to track our progress of the simplification. In fact, for a 4-dimensional sphere, the number of vertices and edges alone is enough to learn about the entire [latex]f[\/latex]-vector [Klee<\/a>]. So we can actually track the progress of the simplification on a 2 dimensional graph.<\/p>\n

Below is a video tracking the progress of our modified bistellar_simplification on our Akbulut-Kirby 4-sphere AK_I_3<\/a>. Since following a single dot was difficult to see, I am displaying the [latex]f[\/latex]-vector (or, more precisely, just the vertex and edge count) of 1000 consecutive complexes at a time. For each of those 1000 complexes, I counted the number of 0-,1-,2-,3-,4-dimensional bistellar moves were made (red = 4-move grows the [latex]f[\/latex]-vector, green = 0-move makes [latex]f[\/latex]-vector smaller; green = good). The box on the bottom right displays the vertex and edge count of the complex at the specified round.<\/p>\n