This thesis presents a general background on discrete Morse theory, as developed by Robin Forman, as well as an introduction to computability and computational complexity. Since general point-set data equipped with a smooth structure can admit a triangulation, discrete Morse theory finds numerous applications in data analysis which can range from traffic control to geographical interpretation. Currently, there are various methods which convert point-set data to simplicial complexes or piecewise-smooth manifolds; however, this is not the focus of the thesis. Instead, this thesis will show that the Morse homology of such data is computable in the classical sense of Turing decidability, bound the complexity of finding the Morse homology of a given simplicial complex, and provide a measure for when this is more efficient than simplicial homology. / Master of Science / With the growing prevalence of data in the technological world, there is an emerging need to identify geometric properties (such as holes and boundaries) to data sets. However, it is often fruitless to employ an algorithm if it is known to be too computationally expensive (or even worse, not computable in the traditional sense). However, discrete Morse theory was originally formulated to provide a simplified manner of calculating these geometric properties on discrete sets. Therefore, this thesis outlines the general background of Discrete Morse theory and formulates the computational cost of computing specific geometric algorithms from the Discrete Morse perspective.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/90397 |
| Date | 21 June 2019 |
| Creators | Dare, Christopher Edward |
| Contributors | Mathematics, Floyd, William J., Mihalcea, Constantin Leonardo, Kay, Leslie D., Haskell, Peter E. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.002 seconds