Name
Abstract | ||
|---|---|---|
We consider maintaining the contour tree $\mathbb{T}$ of a piecewise-linear triangulation $\mathbb{M}$ that is the graph of a time varying height function $h: \mathbb{R}^2 \rightarrow \mathbb{R}$. We carefully describe the combinatorial change in $\mathbb{T}$ that happen as $h$ varies over time and how these changes relate to topological changes in $\mathbb{M}$. We present a kinetic data structure that maintains the contour tree of $h$ over time. Our data structure maintains certificates that fail only when $h(v)=h(u)$ for two adjacent vertices $v$ and $u$ in $\mathbb{M}$, or when two saddle vertices lie on the same contour of $\mathbb{M}$. A certificate failure is handled in $O(\log(n))$ time. We also show how our data structure can be extended to handle a set of general update operations on $\mathbb{M}$ and how it can be applied to maintain topological persistence pairs of time varying functions. |
Year | Venue | Field |
|---|---|---|
2014 | CoRR | Saddle,Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Kinetic data structure,Terrain,Triangulation,Contour tree,Sigma,Mathematics |
DocType | Volume | Citations |
Journal | abs/1406.4005 | 2 |
PageRank | References | Authors |
0.40 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Lars Arge | 2 | 2 | 0.74 |
| Thomas Mølhave | 3 | 136 | 11.85 |
| Morten Revsbæk | 4 | 17 | 3.22 |
| Jungwoo Yang | 5 | 2 | 0.74 |