Tracing Isomanifolds in R^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations - 3IA Côte d’Azur – Interdisciplinary Institute for Artificial Intelligence
Journal Articles SIAM Journal on Computing Year : 2023

Tracing Isomanifolds in R^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations

Abstract

Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of $\mathbb{R}^d$ defined as the zero set of a multivariate multivalued smooth function $f: \mathbb{R}^d\rightarrow \mathbb{R}^{d-n}$, where $n$ is the intrinsic dimension of the manifold and we assume that $0$ is a regular value. A natural way to approximate a smooth isomanifold $\mathcal{M}=f^{-1}(0)$ is to consider its Piecewise-Linear (PL) approximation $\hat{\mathcal{M}}$ based on a triangulation $\mathcal{T}$ of the ambient space $\mathbb{R}^d$, whose longest edge has length $D$. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point {on each connected component}. The algorithm works for arbitrary dimensions $n$ and $d$, and $D$. Our main result is that, when $f$ (or $\mathcal{M}$) has bounded complexity, the complexity of the algorithm is polynomial in $d$ and $\delta=1/D$ (and unavoidably exponential in $n$). Since it is known that for $\delta = \Omega (d^{2.5})$, $\hat{\mathcal{M}}$ is $O(D^2)$-close and isotopic to $\mathcal{M}$, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in $d$. Combining this algorithm with dimensionality reduction techniques, the dependency on $d$ in the size of $\mathcal{M}$ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.
Fichier principal
Vignette du fichier
SIAMAuthor.pdf (10.15 Mo) Télécharger le fichier
Origin Explicit agreement for this submission

Dates and versions

hal-04083489 , version 1 (27-04-2023)

Identifiers

Cite

Jean-Daniel Boissonnat, Siargey Kachanovich, Mathijs Wintraecken. Tracing Isomanifolds in R^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations. SIAM Journal on Computing, 2023, 52, pp.452 - 486. ⟨10.1137/21m1412918⟩. ⟨hal-04083489⟩
64 View
47 Download

Altmetric

Share

More