Computational Topology at Multiple ResolutionsPhD thesis by Vanessa Robins, June 2000.Supervised by Jim Meiss and Liz Bradley in the Department of Applied Mathematics at the University of Colorado, Boulder. Abstract Extracting qualitative information from data is a central goal of experimental science. In dynamical systems, for example, the data typically approximate an attractor or other invariant set and knowledge of the structure of these sets increases our understanding of the dynamics. The most qualitative description of an object is in terms of its topology --- whether or not it is connected, and how many and what type of holes it has, for example. This thesis examines the degree to which such topological information can be extracted from a finite point-set approximation to a compact space. We consider both theoretical and computational aspects for the case of homology. Any attempt to extract topological information from a finite set of points involves coarse-graining the data. We do this at multiple resolutions by forming a sequence of epsilon-neighborhoods with epsilon tending to zero. Our goal is to extrapolate the underlying topology from this sequence of epsilon-neighborhoods. There is some subtlety to the extrapolation, however, since coarse-graining can create spurious holes --- a fact that has been overlooked in previous work on computational topology. We resolve this problem using an inverse system approach from shape theory. The numerical implementations involve constructions from computational geometry. We present a new algorithm based on the minimal spanning tree that successfully determines the apparent connectedness or disconnectedness of point-set data in any dimension. For higher-order homology, we use existing algorithms that employ Delaunay triangulations and alpha shapes. We evaluate these techniques by comparing numerical results with the known topological structure of some examples from discrete dynamical systems. Most of the objects we study have fractal structure. Fractals often exhibit growth in the number of connected components or holes as epsilon goes to zero. We show that the growth rates can distinguish between sets with the same Hausdorff dimension and different homology. Relationships between these growth rates and various definitions of fractal dimension are derived. Overall, the thesis clarifies the complementary role of geometry and topology and shows that it is possible to compute accurate information about the topology of a space from a finite approximation to it. An informal overview online. A gzipped postscript file of the whole thesis (2.2M). Individual chapters in pdf format... Back to my research page. |