License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.8
URN: urn:nbn:de:0030-drops-160162
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16016/
Go to the corresponding LIPIcs Volume Portal

Attali, Dominique ; Lieutier, André

Delaunay-Like Triangulation of Smooth Orientable Submanifolds by ?₁-Norm Minimization

pdf-format:
LIPIcs-SoCG-2022-8.pdf (0.8 MB)

Abstract

In this paper, we focus on one particular instance of the shape reconstruction problem, in which the shape we wish to reconstruct is an orientable smooth submanifold of the Euclidean space. Assuming we have as input a simplicial complex K that approximates the submanifold (such as the Čech complex or the Rips complex), we recast the reconstruction problem as a ?₁-norm minimization problem in which the optimization variable is a chain of K. Providing that K satisfies certain reasonable conditions, we prove that the considered minimization problem has a unique solution which triangulates the submanifold and coincides with the flat Delaunay complex introduced and studied in a companion paper [D. Attali and A. Lieutier, 2022]. Since the objective is a weighted ?₁-norm and the contraints are linear, the triangulation process can thus be implemented by linear programming.

BibTeX - Entry

@InProceedings{attali_et_al:LIPIcs.SoCG.2022.8,
  author =	{Attali, Dominique and Lieutier, Andr\'{e}},
  title =	{{Delaunay-Like Triangulation of Smooth Orientable Submanifolds by ?₁-Norm Minimization}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16016},
  URN =		{urn:nbn:de:0030-drops-160162},
  doi =		{10.4230/LIPIcs.SoCG.2022.8},
  annote =	{Keywords: manifold reconstruction, Delaunay complex, triangulation, sampling conditions, optimization, ?₁-norm minimization, simplicial complex, chain, fundamental class}
}

Keywords: manifold reconstruction, Delaunay complex, triangulation, sampling conditions, optimization, ?₁-norm minimization, simplicial complex, chain, fundamental class
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI