Fractal Dimension and Random Minimum Spanning Trees (Benjamin Schweinhart - Ohio State)

Recently, there has been a surge of interest in applications of persistent homology, including dimension estimation. We prove that the fractal dimension of an Ahlfors regular metric measure space can be recovered from the asymptotic properties of random minimum spanning trees (0-dimensional persistent homology). In particular, the length of a minimum spanning tree on n i.i.d. points is, when rescaled appropriately, bounded between two constants with high probability as n goes to infinity. This is a generalization of a result of Steele (1988) from the non-singular case to the fractal setting, though the corresponding strong law of large numbers is false. We also show analogous results for higher dimensional persistent homology. In addition, computational studies (joint with J. Jaquette) indicate that a minimum spanning tree-based dimension estimation algorithm performs as well or better than classical fractal dimension estimation techniques.

NIS