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

Source: [Computing Height Persistence and Homology Generators in $\\mathbb{R}^3$ Efficiently](<https://www.sota2.com/research/paper/68fa65861e209131cea0acfe>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T05:57:48.173Z

Authors: Tamal K. Dey

Published: 2018-07-10T14:02:35.000Z

## 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 $\\mathbb{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 $\\mathbb{R}^4$ and beyond in less than quadratic or even near-quadratic time. But, what about dimension three? It is known 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 total size $k$ can be computed in $O(n+k)$ time when $K$ is a graph or a surface linearly embedded in $\\mathbb{R}^3$. But, the question for general simplicial complexes $K$ linearly embedded in $\\mathbb{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 {\\em height functions} on such complexes, hence called {\\em 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 matrix multiplication exponent. 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1807.03655>)

[PDF](<https://arxiv.org/pdf/1807.03655.pdf>)
