Published September 13, 2022 | Version v1
Journal article

Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Description

This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the general case. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.

Abstract

International audience

Additional details

Identifiers

URL
https://hal.archives-ouvertes.fr/hal-03870128
URN
urn:oai:HAL:hal-03870128v1