The Topology of Minecraft: Persistent Homology and Barcodes - Nathan Fieldsteel

Preliminaries
In algebraic topology there are many tools which assign simple, easy to understand algebraic objects (think: numbers, vector spaces, groups) to complicated, difficult to understand topological objects (think: weird, complicated shapes). These algebraic objects have a variety of uses, one of which is indicating shape features of the topological object. For example, a topological space X has homology groups Hi(X). One can think of H0(X) as telling you the number of components of X, which H1(X) tells you the number of holes in X. Here are three examples of topological spaces, along with their first two homology groups:

H0(X) = Z1  H1(X) = Z1

 H0(Y) = Z2   H1(Y) = Z2 

H0(Z) = Z1 H1(Z) = Z2

The space X is a circle. It has one component and one hole. The space Y is two disjoint circles, it has two components and two holes. The space Z is a figure eight, it has one component and two holes. The homology groups tell you exactly this information. But sometimes, in the real world, you don’t actually have an entire topological space. You just have a point cloud (like P1 or P2 shown below) that sort of looks like a space.

H0(P1) = Z100 H0(P2) = Z100

H1(P1) = 0 H1(P2) = 0

Homology thinks these two spaces are the same. It sees them both as 100 disjoint points, and it can’t tell that P1 looks like a circle, while P2 looks like a figure eight. Luckily, there’s a more sophisticated tool specifically for this problem, called persistent homology, It works as follows: Choose a distance δ ∈ R0. Now, for any two points in your cloud that are within δ of each other, connect them with and edge. If any three edges form a triangle, fill in that triangle. Call the resulting space Xδ and take the homology of Xδ. If you do this many times for many different values of δ, you can get some information about the underlying space. Roughly speaking, homology that persists for many values of δ is probably the homology of the underlying space that the point cloud came from. Homology that was only present for a narrow interval ofδ values is probably noise in the data. You can encode all the different homology groups parametrized byδ, into a single picture, called the persistence diagram or barcode of the point cloud. If homology showed up at the parameter value δ1 and went away at δ2, we plot the point (δ1,δ2). The more persistent the homology, the further the symbols are from the line y = x. Using dots for H0 and diamonds for H1, we have persistence diagrams corresponding to the above point clouds:

 Persistence diagram for P1.

Persistence diagram for P2.

The persistence diagram for P1 indicates one persistent component and one persistent hole. The persistence diagram for P2 indicates one persistent component, two persistent holes, and one hole that only existed for a very narrow range of the parameter δ and is probably not a true feature of the space.

The Plan
Think of a Minecraft map as a point cloud P ⊆ R3 in the following way: if the block at position (a, b, c) is present, then (a, b, c) ∈ P . If the block is not present, then (a, b, c) is not in P . Once we’ve encoded a map as a point cloud, we can use persistent homology to try to get information about the topology of the map we started with.

Project Goals and Questions

1. Learn the foundations of homology of simplicial complexes and persistent homology of point clouds. 
2. Find and use open-source software for performing computations in persistent homology.
3. Can the persistent homology of P tell you anything about the topology (cave systems) in Minecraft? 
4. Can we gather enough data to make statistical statements about Minecraft maps in general?