Analysis of Topological Persistence in Data Sets
MetadataShow full metadata
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).