English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently it has been shown that computing the dimension of the first homologygroup $H_1(K)$ of a simplicial $2$-complex $K$ embedded linearly in$\mathbb{R}^4$ is as hard as computing the rank of a sparse $0-1$ matrix. Thisputs a major roadblock to computing persistence and a homology basis(generators) for complexes embedded in $\mathbb{R}^4$ and beyond in less thanquadratic or even near-quadratic time. But, what about dimension three? It isknown that persistence for piecewise linear functions on a complex $K$ with $n$simplices can be computed in $O(n\log n)$ time and a set of generators of totalsize $k$ can be computed in $O(n+k)$ time when $K$ is a graph or a surfacelinearly embedded in $\mathbb{R}^3$. But, the question for general simplicialcomplexes $K$ linearly embedded in $\mathbb{R}^3$ is not completely settled. Noalgorithm with a complexity better than that of the matrix multiplication isknown for this important case. We show that the persistence for {\em heightfunctions} on such complexes, hence called {\em height persistence}, can becomputed 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 theoutput. This improves significantly the current best bound of $O(n^{\omega})$,$\omega$ being the matrix multiplication exponent. We achieve these improvedbounds by leveraging recent results on zigzag persistence in computationaltopology, new observations about Reeb graphs, and some efficient geometric datastructures.

Computing Height Persistence and Homology Generators in $\mathbb{R}^3$ Efficiently