License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.57
URN: urn:nbn:de:0030-drops-59490
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5949/
Raichel, Benjamin ;
Seshadhri, C.
Avoiding the Global Sort: A Faster Contour Tree Algorithm
Abstract
We revisit the classical problem of computing the contour tree of a scalar field f:M to R, where M is a triangulated simplicial mesh in R^d. The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization.
All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) Omega(n log n) time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. If C denotes the set of critical points in M, the running time is roughly O(sum_{v in C} log l_v), where l_v is the depth of v in the contour tree. This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in M or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm.
Our algorithm requires several novel ideas: partitioning M in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.
BibTeX - Entry
@InProceedings{raichel_et_al:LIPIcs:2016:5949,
author = {Benjamin Raichel and C. Seshadhri},
title = {{Avoiding the Global Sort: A Faster Contour Tree Algorithm}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {57:1--57:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5949},
URN = {urn:nbn:de:0030-drops-59490},
doi = {10.4230/LIPIcs.SoCG.2016.57},
annote = {Keywords: contour trees, computational topology, computational geometry}
}
|
Keywords: |
|
contour trees, computational topology, computational geometry |
|
Collection: |
|
32nd International Symposium on Computational Geometry (SoCG 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.06.2016 |
