Fast Combinatorial Vector Field Topology
2010 (English)In: IEEE Transactions on Visualization and Computer Graphics, ISSN 1077-2626, E-ISSN 1941-0506, Vol. 17, no 10, 1433-1443 p.Article in journal (Refereed) Published
This paper introduces a novel approximation algorithm for the fundamental graph problem of combinatorial vector field topology (CVT). CVT is a combinatorial approach based on a sound theoretical basis given by Forman’s work on a discrete Morse theory for dynamical systems. A computational framework for this mathematical model of vector field topology has been developed recently. The applicability of this framework is however severely limited by the quadratic complexity of its main computational kernel. In this work we present an approximation algorithm for CVT with a significantly lower complexity. This new algorithm reduces the runtime by several orders of magnitude, and maintains the main advantages of CVT over the continuous approach. Due to the simplicity of our algorithm it can be easily parallelized to improve the runtime further.
Place, publisher, year, edition, pages
2010. Vol. 17, no 10, 1433-1443 p.
Computational topology, algorithm, visualization
IdentifiersURN: urn:nbn:se:liu:diva-127681DOI: 10.1109/TVCG.2010.235PubMedID: 21041887OAI: oai:DiVA.org:liu-127681DiVA: diva2:926374