Topological persistence on a Jordan curve

Published

Journal Article

Topological persistence measures the resilience of extrema of a function to perturbations, and has received increasing attention in computer graphics, visualization and computer vision. While the notion of topological persistence for piece-wise linear functions defined on a simplicial complex has been well studied, the time complexity of all the known algorithms are super-linear (e.g. O(n log n)) in the size n of the complex. We give an O(n) algorithm to compute topological persistence for a function defined on a Jordan curve. To the best of our knowledge, our algorithm is the first to attain linear asymptotic complexity, and is asymptotically optimal. We demonstrate the usefulness of persistence in shape abstraction and compression. © 2012 IEEE.

Full Text

Duke Authors

Cited Authors

  • Zheng, Y; Gu, S; Tomasi, C

Published Date

  • October 23, 2012

Published In

Start / End Page

  • 3693 - 3696

International Standard Serial Number (ISSN)

  • 1520-6149

Digital Object Identifier (DOI)

  • 10.1109/ICASSP.2012.6288718

Citation Source

  • Scopus