Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Efficient open surface reconstruction from lexicographic optimal chains and critical bases

David Cohen-Steiner 1, 2 André Lieutier 3 Julien Vuillamy 3, 2, 4 
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
4 TITANE - Geometric Modeling of 3D Environments
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Previous works on lexicographic optimal chains have shown that they provide meaningful geometric homology representatives while being easier to compute than their l 1-norm optimal counterparts. This work presents a novel algorithm to efficiently compute lexicographic optimal chains with a given boundary in a triangulation of 3-space, by leveraging Lefschetz duality and an augmented version of the disjoint-set data structure. Furthermore, by observing that lexicographic minimization is a linear operation, we define a canonical basis of lexicographic optimal chains, called critical basis, and show how to compute it. In applications, the presented algorithms offer new promising ways of efficiently reconstructing open surfaces in difficult acquisition scenarios.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Julien Vuillamy Connect in order to contact the contributor
Submitted on : Friday, December 3, 2021 - 9:15:56 AM
Last modification on : Friday, February 11, 2022 - 2:56:01 PM


Files produced by the author(s)


  • HAL Id : hal-03456390, version 2


David Cohen-Steiner, André Lieutier, Julien Vuillamy. Efficient open surface reconstruction from lexicographic optimal chains and critical bases. 2021. ⟨hal-03456390v2⟩



Record views


Files downloads