DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2020.32

Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Authors: David Cohen-Steiner, André Lieutier, and Julien Vuillamy

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohensteiner_et_al:LIPIcs.SoCG.2020.32,
  author =	{Cohen-Steiner, David and Lieutier, Andr\'{e} and Vuillamy, Julien},
  title =	{{Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.32},
  URN =		{urn:nbn:de:0030-drops-121908},
  doi =		{10.4230/LIPIcs.SoCG.2020.32},
  annote =	{Keywords: OHCP, simplicial homology, triangulation, Delaunay}
}

Search Results

Documents authored by Cohen-Steiner, David

Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Abstract

Cite as

Thanks for your feedback!

Could not send message