Tracing isomanifolds in \(\mathbb{R}^d\) in time polynomial in \(d\) using Coxeter-Freudenthal-Kuhn triangulations (Q7234073)

This interesting paper studies the tracing of isomanifolds in \(\mathbb{R}^d\) in time, polynomial in \(d\), using Coxeter-Freudenthal-Kuhn triangulations. To set the scene, suppose that we are given a surface in \(\mathbb{R}^3\) which is the zero set of a function say \(g: \mathbb{R}^3\to \mathbb{R}\). The underlying idea of isosurfacing is to construct piecewise linear approximations of the surface. One can extend this idea to working with instead isomanifolds of higher dimensions and codimensions defined as zero sets of multivariate multivalued smooth functions say \(g:\mathbb{R}^d\to \mathbb{R}^{d-n}\). Here \(n\) is the intrinsic dimension of the manifold. Isosurfaces and isomanifolds have numerous applications for example to medical imaging, computer graphics, geometry processing, statistics, dynamical systems, econometrics, mechanics and many others. The authors are interested to approximate a smooth isomanifold by a piecewise-linear approximation based on a triangulation of the ambient space \(\mathbb{R}^d\). The authors construct an algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary \(n\), \(d\) and any precision. One of the main results is that when the function \(g\) or the isomanifold has bounded complexity, the complexity of the algorithm is polynomial in \(d\) and exponential in \(n\). \N\NThe paper is well written with a good set of references.\N\NFor the entire collection see [Zbl 1465.68012].