Analysis of Topological Persistence in Data Sets
Date
2005-08
Authors
Snyder, David
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The PI and his student assistant chose to develop code in C++, leveraging the open source Computational Geometry Algorithmic Library (CGAL; see http://www.cgal.org/). They installed the CGAL software, including incidental 3-d geometry viewing softwares. CGAL does not have built-in support for either version of the Persistence Homology Algorithm (PHA), as these algorithms are new. Thus the PI and the student implemented these PHAs in the CGAL framework, using the CGAL mailing list for technical support. Two approaches were taken to investigate the efficiency of the PHAs. The first was to build a particularly complex 3-dimensional model of Zeeman's Dunce Cap that has peculiar topological properties suitable for testing PHA performance, resulting in evidence that PHAs perform poorly on certain types of data sets. The second approach taken was a ""needle in the haystack" approach: build a 3-d model of a large triangulated cube with over 100,000 vertices and then randomly search through medium-sized sub-triangulations for objects in 3-space that cause the worst algorithm performance. Even with the size restrictions, the search space is so large that this approach has not yet completed (running 24/7 since August 2005). Preliminary results show PHAs performed rather well on average, using a constant number of steps per vertex. Still, until the search completes in Fall 2006, the worst-case performance is unknown. Some impacts of this REP: one peer-reviewed article accepted, one submitted, and one pending final results in Fall 2006; four NSF proposals, with Snyder as PI, submitted (pending as of 15 June 2006).
Description
Research Enhancement Program Final Report
Keywords
topological persistence, data sets, deometry algorithm
Citation
Snyder, D. (2005). Analysis of topological persistence in data sets. Research Enhancement Program, Texas State University, San Marcos, TX.