Topology, Geometry and Data Seminar - Tamal Dey

Image
Tamal Dey
January 15, 2019
4:10PM - 5:10PM
Location
Cockins Hall 240

Date Range
Add to Calendar 2019-01-15 16:10:00 2019-01-15 17:10:00 Topology, Geometry and Data Seminar - Tamal Dey Title: Computing Height Persistence and Homology Generators in $R^3$ in $O(n\log n)$ Time Speaker: Tamal Dey (Ohio State University) Abstract: Recently it has been shown that computing the dimension of the first homology group $H_1(K)$ of a simplicial $2$-complex $K$ embedded linearly in $R^4$ is as hard as computing the rank of a sparse $0-1$ matrix. This puts a major roadblock to computing persistence and a homology basis (generators) for complexes embedded in $R^4$ and beyond in less than quadratic or even near-quadratic time. But, what about dimension three? It is known that when $K$ is a graph or a surface with $n$ simplices linearly embedded in $R^3$, the persistence for piecewise linear functions on $K$ can be computed in $O(n\log n)$ time and a set of generators of total size $k$ can be computed in $O(n+k)$ time . However, the question for general simplicial complexes $K$ linearly embedded in $R^3$ is not completely settled. No algorithm with a complexity better than that of the matrix multiplication is known for this important case. We show that the persistence for height functions on such complexes, hence called height persistence, can be computed in $O(n\log n)$ time. This allows us to compute a basis (generators) of $H_i(K)$, $i=1,2$, in $O(n\log n+k)$ time where $k$ is the size of the output. This improves significantly the current best bound of $O(n^{\omega})$, $\omega$ being the exponent of matrix multiplication. We achieve these improved bounds by leveraging recent results on zigzag persistence in computational topology, new observations about Reeb graphs,and some efficient geometric data structures. Seminar URL: https://tgda.osu.edu/ Cockins Hall 240 Department of Mathematics math@osu.edu America/New_York public
Description

Title: Computing Height Persistence and Homology Generators in $R^3$ in $O(n\log n)$ Time

SpeakerTamal Dey (Ohio State University)

Abstract: Recently it has been shown that computing the dimension of the first homology group $H_1(K)$ of a simplicial $2$-complex $K$ embedded linearly in $R^4$ is as hard as computing the rank of a sparse $0-1$ matrix. This puts a major roadblock to computing persistence and a homology basis (generators) for complexes embedded in $R^4$ and beyond in less than quadratic or even near-quadratic time. But, what about dimension three? It is known that when $K$ is a graph or a surface with $n$ simplices linearly embedded in $R^3$, the persistence for piecewise linear functions on $K$ can be computed in $O(n\log n)$ time and a set of generators of total size $k$ can be computed in $O(n+k)$ time . However, the question for general simplicial complexes $K$ linearly embedded in $R^3$ is not completely settled. No algorithm with a complexity better than that of the matrix multiplication is known for this important case. We show that the persistence for height functions on such complexes, hence called height persistence, can be computed in $O(n\log n)$ time. This allows us to compute a basis (generators) of $H_i(K)$, $i=1,2$, in $O(n\log n+k)$ time where $k$ is the size of the output. This improves significantly the current best bound of $O(n^{\omega})$, $\omega$ being the exponent of matrix multiplication. We achieve these improved bounds by leveraging recent results on zigzag persistence in computational topology, new observations about Reeb graphs,and some efficient geometric data structures.

Seminar URLhttps://tgda.osu.edu/

Events Filters: