Skip to Main content Skip to Navigation

Meshing submanifolds using Coxeter triangulations

Siargey Kachanovich 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation). We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud. Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal. Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of the quality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space.
Complete list of metadata

Cited literature [103 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Monday, June 8, 2020 - 11:38:09 AM
Last modification on : Tuesday, December 8, 2020 - 10:30:34 AM


Version validated by the jury (STAR)


  • HAL Id : tel-02419148, version 2



Siargey Kachanovich. Meshing submanifolds using Coxeter triangulations. Computational Geometry [cs.CG]. COMUE Université Côte d'Azur (2015 - 2019), 2019. English. ⟨NNT : 2019AZUR4072⟩. ⟨tel-02419148v2⟩



Record views


Files downloads