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

Sampling and Meshing Submanifolds in High Dimension

Abstract : This paper presents a rather simple tracing algorithm to sample and mesh an m-dimensional sub-manifold of Rd for arbitrary m and d. We extend the work of Dobkin et al. to submanifolds of arbitrary dimension and codimension. The algorithm is practical and has been thoroughly investigated from both theoretical and experimental perspectives. The paper provides a full description and analysis of the data structure and of the tracing algorithm. The main contributions are : 1. We unify and complement the knowledge about Coxeter and Freudenthal-Kuhn triangulations. 2. We introduce an elegant and compact data structure to store Coxeter or Freudenthal-Kuhn triangulations and describe output sensitive algorithms to compute faces and cofaces or any simplex in the triangulation. 3. We present a manifold tracing algorithm based on the above data structure. We provide a detailled complexity analysis along with experimental results that show that the algorithm can handle cases that are far ahead of the state-of-the-art.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Friday, November 29, 2019 - 2:14:38 PM
Last modification on : Friday, April 30, 2021 - 10:00:43 AM


Files produced by the author(s)


  • HAL Id : hal-02386169, version 2


Jean-Daniel Boissonnat, Siargey Kachanovich, Mathijs Wintraecken. Sampling and Meshing Submanifolds in High Dimension. 2019. ⟨hal-02386169v2⟩



Record views


Files downloads