---
res:
bibo_abstract:
- "Isomanifolds are the generalization of isosurfaces to arbitrary dimension and
codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate
multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension
of the manifold. A natural way to approximate a smooth isomanifold M is to consider
its Piecewise-Linear (PL) approximation M̂ based on a triangulation \U0001D4AF
of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace
isomanifolds from a given starting point. The algorithm works for arbitrary dimensions
n and d, and any precision D. Our main result is that, when f (or M) has bounded
complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and
unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂
is O(D²)-close and isotopic to 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 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. @eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Jean-Daniel
foaf_name: Boissonnat, Jean-Daniel
foaf_surname: Boissonnat
- foaf_Person:
foaf_givenName: Siargey
foaf_name: Kachanovich, Siargey
foaf_surname: Kachanovich
- foaf_Person:
foaf_givenName: Mathijs
foaf_name: Wintraecken, Mathijs
foaf_surname: Wintraecken
foaf_workInfoHomepage: http://www.librecat.org/personId=307CFBC8-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-7472-2220
bibo_doi: 10.4230/LIPIcs.SoCG.2021.17
bibo_volume: 189
dct_date: 2021^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/978-3-95977-184-9
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn
triangulations@
...