---
_id: '17170'
abstract:
- lang: eng
  text: "In this article we extend and strengthen the seminal work by Niyogi, Smale,
    and Weinberger on the learning of the homotopy type from a sample of an underlying
    space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds
    with positive reach embedded in ℝ^d. We extend their results in the following
    ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with
    lower bounded sectional curvature. - In both types of ambient spaces, we study
    sets of positive reach - a significantly more general setting than C² manifolds
    - as well as general manifolds of positive reach. - The sample P of a set (or
    a manifold) \U0001D4AE of positive reach may be noisy. We work with two one-sided
    Hausdorff distances - ε and δ - between P and \U0001D4AE. We provide tight bounds
    in terms of ε and δ, that guarantee that there exists a parameter r such that
    the union of balls of radius r centred at the sample P deformation-retracts to
    \U0001D4AE. We exhibit their tightness by an explicit construction. We carefully
    distinguish the roles of δ and ε. This is not only essential to achieve tight
    bounds, but also sensible in practical situations, since it allows one to adapt
    the bound according to sample density and the amount of noise present in the sample
    separately."
acknowledgement: "This research has been supported by the European Research Council
  (ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF),
  grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian
  Science Fund (FWF), grant No. I 02979-N35.\r\nWintraecken, Mathijs: Supported by
  the European Union’s Horizon 2020 research and innovation programme under the Marie
  Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant
  No. M-3073, and the welcome package from IDEX of the Université Côte d'Azur."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Dominique
  full_name: Attali, Dominique
  last_name: Attali
- first_name: Hana
  full_name: Kourimska, Hana
  id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E
  last_name: Kourimska
  orcid: 0000-0001-7841-0091
- first_name: Christopher D
  full_name: Fillmore, Christopher D
  id: 35638A5C-AAC7-11E9-B0BF-5503E6697425
  last_name: Fillmore
- first_name: Ishika
  full_name: Ghosh, Ishika
  id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff
  last_name: Ghosh
- first_name: André
  full_name: Lieutier, André
  last_name: Lieutier
- first_name: Elizabeth R
  full_name: Stephenson, Elizabeth R
  id: 2D04F932-F248-11E8-B48F-1D18A9856A87
  last_name: Stephenson
  orcid: 0000-0002-6862-208X
- first_name: Mathijs
  full_name: Wintraecken, Mathijs
  id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
  last_name: Wintraecken
  orcid: 0000-0002-7472-2220
citation:
  ama: 'Attali D, Kourimska H, Fillmore CD, et al. Tight bounds for the learning of
    homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and
    of Riemannian manifolds. In: <i>40th International Symposium on Computational
    Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.11">10.4230/LIPIcs.SoCG.2024.11</a>'
  apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson,
    E. R., &#38; Wintraecken, M. (2024). Tight bounds for the learning of homotopy
    à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian
    manifolds. In <i>40th International Symposium on Computational Geometry</i> (Vol.
    293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.11">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>'
  chicago: Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh,
    André Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “Tight Bounds
    for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of
    Euclidean Spaces and of Riemannian Manifolds.” In <i>40th International Symposium
    on Computational Geometry</i>, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2024. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.11">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>.
  ieee: D. Attali <i>et al.</i>, “Tight bounds for the learning of homotopy à la Niyogi,
    Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,”
    in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece,
    2024, vol. 293, p. 11:1-11:19.
  ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken
    M. 2024. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
    for subsets of euclidean spaces and of Riemannian manifolds. 40th International
    Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
    LIPIcs, vol. 293, 11:1-11:19.'
  mla: Attali, Dominique, et al. “Tight Bounds for the Learning of Homotopy à La Niyogi,
    Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.”
    <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2024.11">10.4230/LIPIcs.SoCG.2024.11</a>.
  short: D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson,
    M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19.
conference:
  end_date: 2024-06-14
  location: Athens, Greece
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2024-06-11
date_created: 2024-06-25T11:45:58Z
date_published: 2024-06-06T00:00:00Z
date_updated: 2025-04-15T07:16:57Z
day: '06'
ddc:
- '516'
department:
- _id: GradSch
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2024.11
ec_funded: 1
external_id:
  arxiv:
  - '2206.10485'
file:
- access_level: open_access
  checksum: 6a2ddc8b51aa58f197a8b294750f1f8d
  content_type: application/pdf
  creator: cfillmor
  date_created: 2024-06-25T11:47:26Z
  date_updated: 2024-06-25T11:47:26Z
  file_id: '17171'
  file_name: LIPIcs.SoCG.2024.11.pdf
  file_size: 20886142
  relation: main_file
  success: 1
file_date_updated: 2024-06-25T11:47:26Z
has_accepted_license: '1'
intvolume: '       293'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 11:1-11:19
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I02979-N35
  name: Persistence and stability of geometric complexes
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
  grant_number: M03073
  name: Learning and triangulating manifolds via collapses
publication: 40th International Symposium on Computational Geometry
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773164'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger
  for subsets of euclidean spaces and of Riemannian manifolds
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...