Search

Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary., LIPIcs, Vol. 164, 36th International Symposium on Computational Geometry (SoCG 2020), pages 20:1-20:18

Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of R d defined as the zero set of some multivariate multivalued smooth function f : R^d → R^{d−m} where m is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation or meshM based on a triangulation T of the ambient space R d. In this paper, we present a simple algorithm to construct such an approximation for arbitrary m and d up to a given precision D. The complexity of our algorithm is polynomial in d and δ, and exponential in m. Since, by previous results,M is O(D 2)-close and isotopic to M when δ = Ω(d 2.5), our algorithm constructs a geometrically close and topologically correct PL-approximation of isomanifolds of low dimensions in polynomial time. The algorithm is practical and can handle cases that are far ahead of the state-of-the-art. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the sizes of the output sample and mesh can be completely removed with high probability. The crux of our algorithm is to use for the ambient triangulation T a regular triangulation from a particular family. This family consists of Freudenthal-Kuhn triangulations and their images through affine mappings. It also includes Coxeter triangulations of typeà d. We introduce an elegant and very compact data structure to implicitly store the full facial structure of such triangulations. This data structure allows to retrieve the faces or the cofaces of a simplex of any dimension in an output sensitive way, which is essential for our application and is of independent interest.

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.