---
_id: '9441'
abstract:
- lang: eng
  text: "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. "
acknowledgement: We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent
  Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge
  the reviewers.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Jean-Daniel
  full_name: Boissonnat, Jean-Daniel
  last_name: Boissonnat
- first_name: Siargey
  full_name: Kachanovich, Siargey
  last_name: Kachanovich
- first_name: Mathijs
  full_name: Wintraecken, Mathijs
  id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
  last_name: Wintraecken
  orcid: 0000-0002-7472-2220
citation:
  ama: 'Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in
    time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: <i>37th
    International Symposium on Computational Geometry (SoCG 2021)</i>. Vol 189. Leibniz
    International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.17">10.4230/LIPIcs.SoCG.2021.17</a>'
  apa: 'Boissonnat, J.-D., Kachanovich, S., &#38; Wintraecken, M. (2021). Tracing
    isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations.
    In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i> (Vol.
    189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.17">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>'
  chicago: 'Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken.
    “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn
    Triangulations.” In <i>37th International Symposium on Computational Geometry
    (SoCG 2021)</i>, 189:17:1-17:16. Leibniz International Proceedings in Informatics
    (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2021. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.17">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>.'
  ieee: J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds
    in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,”
    in <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>,
    Virtual, 2021, vol. 189, p. 17:1-17:16.
  ista: 'Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds
    in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th
    International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium
    on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs),
    LIPIcs, vol. 189, 17:1-17:16.'
  mla: Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial
    in d Using Coxeter-Freudenthal-Kuhn Triangulations.” <i>37th International Symposium
    on Computational Geometry (SoCG 2021)</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2021, p. 17:1-17:16, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2021.17">10.4230/LIPIcs.SoCG.2021.17</a>.
  short: J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International
    Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, Dagstuhl, Germany, 2021, p. 17:1-17:16.
conference:
  end_date: 2021-06-11
  location: Virtual
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2021-06-07
date_created: 2021-06-02T10:10:55Z
date_published: 2021-06-02T00:00:00Z
date_updated: 2023-10-10T07:34:34Z
day: '02'
ddc:
- '005'
- '516'
- '514'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2021.17
ec_funded: 1
file:
- access_level: open_access
  checksum: c322aa48d5d35a35877896cc565705b6
  content_type: application/pdf
  creator: mwintrae
  date_created: 2021-06-02T10:22:33Z
  date_updated: 2021-06-02T10:22:33Z
  file_id: '9442'
  file_name: LIPIcs-SoCG-2021-17.pdf
  file_size: 1972902
  relation: main_file
  success: 1
file_date_updated: 2021-06-02T10:22:33Z
has_accepted_license: '1'
intvolume: '       189'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 17:1-17:16
place: Dagstuhl, Germany
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 37th International Symposium on Computational Geometry (SoCG 2021)
publication_identifier:
  isbn:
  - 978-3-95977-184-9
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '12960'
    relation: later_version
    status: public
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn
  triangulations
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 189
year: '2021'
...