The topological correctness of PL approximations of isomanifolds

DOI10.1007/S10208-021-09520-0MaRDI QIDQ2162117zbMATH OpenOpenAlexWikidataFDO

Authors Jean-Daniel Boissonnat, M. H. M. J. Wintraecken

Publication date 5 August 2022

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10208-021-09520-0

Fréchet distance isomanifold isomanifolds with boundary isotopy nonsmooth analysis piecewise-linear approximation solution manifolds topological correctness

Mathematics Subject Classification ID

Triangulation and topological properties of semi-analytic andsubanalytic sets, and related questions (32B25) Computational methods for problems pertaining to geometry (51-08) Applications of differential geometry to data and computer science (53Z50) Approximations in PL-topology (57Q55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Let \(f\colon\mathbb{R}^d\rightarrow\mathbb{R}^{d-n}\) be a smooth function and assume that \(0 \in \mathbb{R}^{d-n}\) is a regular value of \(f\). Then, according to the implicit function theorem, the zero set \(\mathcal{M} = \{x \in \mathbb{R}^d~|~f(x)=0\}\) is a smooth \(n\)-dimensional submanifold of \(\mathbb{R}^d\) called an \textit{isomanifold}. Isomanifolds naturally appear in various contexts, such as statistics, dynamical systems, econometrics, or mechanics, and \textit{isosurfaces} (zero sets of smooth \(f\colon\mathbb{R}^3\rightarrow\mathbb{R}\) functions) are fundamentally important in medical imaging, computer graphics and geometry processing. In a computational setting, it is imperative to work with discretizations of isomanifolds, and a natural way of doing so is by taking a \textit{piecewise-linear (PL) approximation} of the manifold with respect to a triangulation \(\mathcal{T}\) of its ambient space \(\mathbb{R}^d\). More concretely, for a compact isomanifold defined through a smooth function \(f\colon\mathbb{R}^d\rightarrow\mathbb{R}^{d-n}\) as above, the PL~approximation \(f_{PL}\colon\mathbb{R}^d\rightarrow\mathbb{R}^{d-n}\) of \(f\) with respect to \(\mathcal{T}\) is defined as follows. For a given simplex \(\sigma \in \mathcal{T}\) and a point \(x \in \sigma\), set \[ f_{PL}(x) = \sum_{v \in \sigma}\lambda_v(x)f(v), \] where the \(\lambda_v(x)\) denote the barycentric coordinates of \(x\) with respect to the vertices \(v\) of \(\sigma\). In words, ``the function \(f_{PL}\) is the linear interpolation of the values of \(f\) at the vertices if restricted to a single simplex \(\sigma \in \mathcal{T}\) (p.~971). \textbf{The main results} The quality of the above PL approximation (which fundamentally depends on the chosen triangulation \(\mathcal{T}\) of \(\mathbb{R}^d\)) can be assessed according to several criteria. In the present paper three such criteria are considered: \begin{itemize} \item[1.] topological correctness by means of \textit{ambient isotopies} (*) (a qualitative criterion), \item[2.] \textit{Fréchet distance} (a quantitative criterion), and \item[3.] the difference between gradients (a quantitative criterion). \end{itemize} (*) Informally, two submanifolds \(X\) and \(Y\) of \(\mathbb{R}^d\) are \textit{ambient isotopic}, if they can be turned into one another by a continuous, reversible deformation of the ambient space \(\mathbb{R}^d\). The authors establish the following main results: \textbf{Theorem 25} (Ambient isotopy). The zero set of \(f_{PL}\) is a manifold that is ambient isotopic to the zero set of \(f\), provided that the triangulation \(\mathcal{T}\) is sufficiently fine and thick. (An analogous result is established for isomanifolds with non-empty boundary as well, cf. \textbf{Theorem 48}.) \textbf{Corollary 27} (Bound on the Fréchet distance). The Fréchet distance between \(f_{PL}\) and \(f\) is of the order of \(D^2\), where \(D\) is the longest edge length of \(T\). \textbf{Proposition 10.} The difference between the gradient of \(f\) and the gradient of its piecewise-linear approximation is of order \(dD\) inside each simplex of \(\mathcal{T}\) (cf. [\textit{E. L. Allgower} and \textit{K. Georg}, Appl. Math. Lett. 2, No. 2, 111--115 (1989; Zbl 0715.41016]). According to the authors: ``An important aspect of these results is that they hold under mild conditions: they simply ask for a sufficiently fine and thick triangulation \(\mathcal{T}.\) In contrast to previous results on the triangulation of manifolds, no perturbations are needed to guarantee topological correctness. Our method provides guarantees on the piecewise-linear (PL) approximation of isomanifolds, regarding the topology, the Fréchet distance and the approximation of the gradients (the latter was already known to Allgower and Georg [loc. cit.]). (p.~970). The paper is well-structured and a number of references are provided for context and further reading. While some of the proofs are necessarily quite technical, the explicit and careful calculations will certainly be appreciated by the interested reader.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: The topological correctness of PL approximations of isomanifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2162117)