# The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition)

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika

Ghosh, André Lieutier, Elizabeth Stephenson, Mathijs Wintraecken

► To cite this version:

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, et al.. The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition). 40th International Symposium on Computational Geometry (SoCG 2024), 2024, Athens, Greece. 10.4230/LIPIcs.SoCG.2024.87 . hal-04628855

HAL Id: hal-04628855

https://hal.science/hal-04628855

Submitted on 28 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition)

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, Mathijs Wintraecken

<figure><img src="image_1.png" /></figure>

## To cite this version:

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, et al.. The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition). SoCG 2024 - 40th International Symposium on Computational Geometry, Jun 2024, Athènes, Greece. pp.87:1-87:6, 10.4230/LIPIcs.SoCG.2024.87 . hal-04628855

HAL Id: hal-04628855

https://hal.science/hal-04628855v1

Submitted on 28 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# The Ultimate Frontier: An Optimality Construction for Homotopy Inference

Dominique Attali

<figure><img src="image_1.png" /></figure>

Université Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, Grenoble, France

Hana Dal Poz Kouřimská

<figure><img src="image_2.png" /></figure>

IST Austria, Klosterneuburg, Austria

Christopher Fillmore

<figure><img src="image_3.png" /></figure>

IST Austria, Klosterneuburg, Austria

Ishika Ghosh

<figure><img src="image_4.png" /></figure>

IST Austria, Klosterneuburg, Austria

Michigan State University, East Lansing, MI, USA

André Lieutier

<figure><img src="image_5.png" /></figure>

Aix-en-Provence, France

Elizabeth Stephenson

<figure><img src="image_6.png" /></figure>

IST Austria, Klosterneuburg, Austria

Mathijs Wintraecken

<figure><img src="image_7.png" /></figure>

Inria Sophia Antipolis, Université Côte d'Azur, Sophia Antipolis, France

## Abstract

In our companion paper “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds” we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample *P* of an input shape *S* (either manifold or general set with positive reach) such that one can infer the homotopy of *S* from the union of balls with some radius centred at *P*, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.

**2012 ACM Subject Classification** Theory of computation → Computational geometry

**Keywords and phrases** Homotopy, Inference, Sets of positive reach

**Digital Object Identifier** 10.4230/LIPIcs.SoCG.2024.87

**Category** Media Exposition

**Related Version** Full description of all topological transitions: https://hal.science/hal-04501285

**Supplementary Material** Audiovisual: https://youtu.be/N8wCCAcLgi8?si=wtdEDIKPNqFP6ne1

**Funding** 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.

**Mathijs Wintraecken:** 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.

**Acknowledgements** We thank Jean-Daniel Boissonnat, Herbert Edelsbrunner, and Mariette Yvinec for discussion.

<figure><img src="image_8.png" /></figure>

© Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken; licensed under Creative Commons License CC-BY 4.0

40th International Symposium on Computational Geometry (SoCG 2024).

Editors: Wolfgang Mulzer and Jeff M. Phillips; Article No. 87; pp. 87:1–87:6

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# The Ultimate Frontier: An Optimality Construction for Homotopy Inference

Dominique Attali

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

Université Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, Grenoble, France

Hana Dal Poz Kouřimská

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

IST Austria, Klosterneuburg, Austria

Christopher Fillmore

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

IST Austria, Klosterneuburg, Austria

Ishika Ghosh

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

IST Austria, Klosterneuburg, Austria

Michigan State University, East Lansing, MI, USA

André Lieutier

<figure><img src="image_11.png" /></figure>

Aix-en-Provence, France

Elizabeth Stephenson

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

IST Austria, Klosterneuburg, Austria

Mathijs Wintraecken

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

Inria Sophia Antipolis, Université Côte d'Azur, Sophia Antipolis, France

## Abstract

In our companion paper “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds” we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample *P* of an input shape *S* (either manifold or general set with positive reach) such that one can infer the homotopy of *S* from the union of balls with some radius centred at *P*, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.

**2012 ACM Subject Classification** Theory of computation → Computational geometry

**Keywords and phrases** Homotopy, Inference, Sets of positive reach

**Digital Object Identifier** 10.4230/LIPIcs.SoCG.2024.87

**Category** Media Exposition

**Related Version** Full description of all topological transitions: https://hal.science/hal-04501285

**Supplementary Material** Audiovisual: https://youtu.be/N8wCCAcLgi8?si=wtdEDIKPNqFP6ne1

**Funding** 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.

**Mathijs Wintraecken:** 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.

**Acknowledgements** We thank Jean-Daniel Boissonnat, Herbert Edelsbrunner, and Mariette Yvinec for discussion.

<figure><img src="image_16.png" /></figure>

© Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken; licensed under Creative Commons License CC-BY 4.0

40th International Symposium on Computational Geometry (SoCG 2024).

Editors: Wolfgang Mulzer and Jeff M. Phillips; Article No. 87; pp. 87:1–87:6

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# 1 Introduction

The medial axis of a set consists of those points in ambient space with no unique closest point on the set, and the reach of a set is the distance between the set and its medial axis. In [6], Niyogi, Smale, and Weinberger showed that, given a $C^2$ manifold of positive reach and a sufficiently dense point sample ($P$) on (or near) the manifold, the union of balls of certain radii centred on the point sample captures the homotopy type of the manifold. Niyogi, Smale, and Weinberger's homotopy reconstruction result has led to generalizations including [3, 4, 5, 7].

In this video and our companion paper [2] we consider both submanifolds ($\mathcal{M}$) and general closed subsets of positive reach ($\mathcal{S}$) in the Euclidean space. While for the media contribution we concentrate on the Euclidean setting due to the ease of visualization, in [2] we also generalize the ambient space to Riemannian manifolds of bounded curvature.

We recall that the one-sided Hausdorff distance from $X$ to $Y$, denoted by $d_H^o(X; Y)$, is the smallest $\rho$ such that the union of balls of radius $\rho$ centred at $X$ covers $Y$. We denote the bound on the one-sided Hausdorff distance from $P$ to $\mathcal{M}$ (resp. $\mathcal{S}$) by $\varepsilon$, and the one-sided Hausdorff distance from $\mathcal{M}$ (resp. $\mathcal{S}$) to $P$ by $\delta$. In [2], we achieved the following conditions on $\varepsilon$ and $\delta$ which, if satisfied, guarantee the existence of a radius $r > 0$ such that the union of balls $\bigcup_{p \in P} B(p, r) = P \oplus B(r)$, with $\oplus$ the Minkowski sum, deformation-retracts onto $\mathcal{M}$ (resp. $\mathcal{S}$): If $\mathcal{S}$ has positive reach ($\mathcal{R}$), the condition is

$$ \varepsilon + \sqrt{2}\delta \le (\sqrt{2} - 1)\mathcal{R}. \qquad (\text{CS}) $$

If, moreover, $\mathcal{S} = \mathcal{M}$ is a manifold and $\delta \le \varepsilon \le \mathcal{R}$, the condition is

$$ (\mathcal{R} - \delta)^2 - \varepsilon^2 \ge (4\sqrt{2} - 5)\mathcal{R}^2. \qquad (\text{CM}) $$

The set of pairs $(\varepsilon, \delta)$ that satisfy these conditions is depicted in Figure 1.

<figure><img src="image_11.png" /><figcaption>■ Figure 1 In blue we depict the region in $(\varepsilon, \delta)$-space for which there exists a radius $r$ such that the union of balls $P \oplus B(r)$ captures the homotopy type of a set of positive reach $\mathcal{R} = 1$. We do the same in yellow for a manifold. We stress that for $\delta \ge \varepsilon$, the fact that a set of positive reach is also a manifold does not lead to better bounds. The black points indicate the bounds that were known to Niyogi, Smale, and Weinberger.</figcaption></figure>

In [2] we proved that the bounds CS and CM are optimal for sets of dimension at least 2 in the following sense: If the conditions are not satisfied, we can construct a set of positive reach $\mathcal{S}$ (resp. manifold $\mathcal{M}$) and a sample $P$, such that the homology of the thickening $P \oplus B(r)$ always differs from the homology of $\mathcal{S}$ (resp. $\mathcal{M}$).

In the following we construct the set $\mathcal{S}$ (resp. the manifold $\mathcal{M}$) and the sample $P$ that show the optimality of our bounds. The main goal of the video is to visualize the construction.
# 1 Introduction

The medial axis of a set consists of those points in ambient space with no unique closest point on the set, and the reach of a set is the distance between the set and its medial axis. In [6], Niyogi, Smale, and Weinberger showed that, given a $C^2$ manifold of positive reach and a sufficiently dense point sample ($P$) on (or near) the manifold, the union of balls of certain radii centred on the point sample captures the homotopy type of the manifold. Niyogi, Smale, and Weinberger's homotopy reconstruction result has led to generalizations including [3, 4, 5, 7].

In this video and our companion paper [2] we consider both submanifolds ($\mathcal{M}$) and general closed subsets of positive reach ($\mathcal{S}$) in the Euclidean space. While for the media contribution we concentrate on the Euclidean setting due to the ease of visualization, in [2] we also generalize the ambient space to Riemannian manifolds of bounded curvature.

We recall that the one-sided Hausdorff distance from $X$ to $Y$, denoted by $d_H^o(X; Y)$, is the smallest $\rho$ such that the union of balls of radius $\rho$ centred at $X$ covers $Y$. We denote the bound on the one-sided Hausdorff distance from $P$ to $\mathcal{M}$ (resp. $\mathcal{S}$) by $\varepsilon$, and the one-sided Hausdorff distance from $\mathcal{M}$ (resp. $\mathcal{S}$) to $P$ by $\delta$. In [2], we achieved the following conditions on $\varepsilon$ and $\delta$ which, if satisfied, guarantee the existence of a radius $r > 0$ such that the union of balls $\bigcup_{p \in P} B(p, r) = P \oplus B(r)$, with $\oplus$ the Minkowski sum, deformation-retracts onto $\mathcal{M}$ (resp. $\mathcal{S}$): If $\mathcal{S}$ has positive reach ($\mathcal{R}$), the condition is

$$ \varepsilon + \sqrt{2}\delta \le (\sqrt{2} - 1)\mathcal{R}. \qquad (\text{CS}) $$

If, moreover, $\mathcal{S} = \mathcal{M}$ is a manifold and $\delta \le \varepsilon \le \mathcal{R}$, the condition is

$$ (\mathcal{R} - \delta)^2 - \varepsilon^2 \ge (4\sqrt{2} - 5)\mathcal{R}^2. \qquad (\text{CM}) $$

The set of pairs $(\varepsilon, \delta)$ that satisfy these conditions is depicted in Figure 1.

<figure><img src="image_19.png" /><figcaption>■ Figure 1 In blue we depict the region in $(\varepsilon, \delta)$-space for which there exists a radius $r$ such that the union of balls $P \oplus B(r)$ captures the homotopy type of a set of positive reach $\mathcal{R} = 1$. We do the same in yellow for a manifold. We stress that for $\delta \ge \varepsilon$, the fact that a set of positive reach is also a manifold does not lead to better bounds. The black points indicate the bounds that were known to Niyogi, Smale, and Weinberger.</figcaption></figure>

In [2] we proved that the bounds CS and CM are optimal for sets of dimension at least 2 in the following sense: If the conditions are not satisfied, we can construct a set of positive reach $\mathcal{S}$ (resp. manifold $\mathcal{M}$) and a sample $P$, such that the homology of the thickening $P \oplus B(r)$ always differs from the homology of $\mathcal{S}$ (resp. $\mathcal{M}$).

In the following we construct the set $\mathcal{S}$ (resp. the manifold $\mathcal{M}$) and the sample $P$ that show the optimality of our bounds. The main goal of the video is to visualize the construction.
2 The Construction

Note that due to rescaling it suffices to construct sets of reach $rch(S) = \mathcal{R} = 1$.

<figure><img src="image_12.png" /><figcaption>(a) For all $r < r_0$, the union of balls $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has three connected components.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) At radius $r_1$, the 1-cycle (created at $r_0$) in the union of balls $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$ at the annulus $A_0$ dies, while a cycle is created in the union of balls $(C_1 \cup \{p_1, \tilde{p}_1\}) \oplus B(r)$ at the annulus $A_1$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(c) At radius $r_2$, the cycle in the union of balls at the annulus $A_1$ dies, while a cycle is created in the union of balls at the annulus $A_2$.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(d) The set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ at radius $r_k = 1 - \delta$. The two “gaps” are identical.</figcaption></figure>

<caption>(e) The two “gaps” of the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ disappear simultaneously.</caption>

■ **Figure 2** The changing homology of the thickening $P \oplus B(r)$ in the annuli $A_0, A_1, A_2$, and $A_k$. The set $S$ is in blue, the sample $P$ in red, and the thickening $P \oplus B(r)$ in pink. The black circles indicate the location of the two isolated sample points of $P$ associated to each annulus.
2 The Construction

Note that due to rescaling it suffices to construct sets of reach $rch(S) = \mathcal{R} = 1$.

<figure><img src="image_20.png" /><figcaption>(a) For all $r < r_0$, the union of balls $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has three connected components.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(b) At radius $r_1$, the 1-cycle (created at $r_0$) in the union of balls $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$ at the annulus $A_0$ dies, while a cycle is created in the union of balls $(C_1 \cup \{p_1, \tilde{p}_1\}) \oplus B(r)$ at the annulus $A_1$.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(c) At radius $r_2$, the cycle in the union of balls at the annulus $A_1$ dies, while a cycle is created in the union of balls at the annulus $A_2$.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(d) The set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ at radius $r_k = 1 - \delta$. The two “gaps” are identical.</figcaption></figure>

<caption>(e) The two “gaps” of the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ disappear simultaneously.</caption>

■ **Figure 2** The changing homology of the thickening $P \oplus B(r)$ in the annuli $A_0, A_1, A_2$, and $A_k$. The set $S$ is in blue, the sample $P$ in red, and the thickening $P \oplus B(r)$ in pink. The black circles indicate the location of the two isolated sample points of $P$ associated to each annulus.
## 2.1 Sets of Positive Reach

The construction for sets of positive reach goes as follows: We define $\mathcal{S}$ to be a union of annuli $A_i$ in $\mathbb{R}^2$, each of which has inner radius 1 and outer radius $1 + 2\epsilon$. We lay the annuli in a row at distance at least 2 away from each other. We number the annuli from $i = 0$.

The sample $P$ consists of circles $C_i$ of radius $1 + \epsilon$ lying in the middle of the annuli ($C_i \subseteq A_i$), and pairs of points $\{p_i, \tilde{p}_i\}$. Each pair $\{p_i, \tilde{p}_i\}$ lies in the disk inside the annulus $A_i$, at a distance $\delta$ from $A_i$, and the two points lie at a distance $2r_i$ from each other. The bisector of $p_i$ and $\tilde{p}_i$ intersects the circle $C_i$ in two points. We let $q_i$ be the intersection point that is closest to $p_i$ (and thus $\tilde{p}_i$). We denote the circumradius of $p_i\tilde{p}_iq_i$ by $R_i$ and note that $R_i \ge r_i$.

<figure><img src="image_16.png" /><figcaption>■ Figure 3 Each annulus $A_i$ is sampled by a circle $C_i$ and a pair of points $\{p_i, \tilde{p}_i\}$. The circumradius is indicated by $R_i$.</figcaption></figure>

We set $r_0 = \frac{\delta+\epsilon}{2}$ and, for $i \ge 0$,

$$r_{i+1} = \begin{cases} R_i, & \text{if } R_i < 1 - \delta, \\ 1 - \delta, & \text{otherwise.} \end{cases}$$

We stop the sequence at the first value of $i = k$ such that $r_k = 1 - \delta$. Our constructed set $\mathcal{S}$ consists of the finitely many annuli $A_0 \cup A_1 \cup \dots \cup A_k$ and our sample $P$ is defined as $\bigcup_{0 \le i \le k} C_i \cup \{p_i, \tilde{p}_i\}$. The topological transitions of the thickening of the sample $(P \oplus B(r))$ are illustrated in Figure 2 and described in the supplementary material [1].

## 2.2 Manifolds

The construction for manifolds goes as follows: We define $\mathcal{M}$ to be a union of tori of revolution $T_i \subseteq \mathbb{R}^3$. Each of these tori is the 1-offset of a circle (in the horizontal plane) of radius 2 in $\mathbb{R}^3$. We number the tori from $i = 0$, and lay them out in a row at a distance at least 2 apart from one another. Due to this assumption, the reach of $\mathcal{M}$ equals 1.

The sample $P$ consists of sets $C_i$ which are tori with a part cut out, and pairs of points $\{p_i, \tilde{p}_i\}$ lying inside the hole of each torus $T_i$. To construct each set $C_i$ we take the $\delta$-offset of $T_i$, keep the part that lies inside the solid torus bounded by $T_i$, and remove an $\epsilon$-neighbourhood of the circle obtained by revolving the point (1, 0, 0) around the $z$-axis; see the red set in Figures 4 and 5.
## 2.1 Sets of Positive Reach

The construction for sets of positive reach goes as follows: We define $\mathcal{S}$ to be a union of annuli $A_i$ in $\mathbb{R}^2$, each of which has inner radius 1 and outer radius $1 + 2\epsilon$. We lay the annuli in a row at distance at least 2 away from each other. We number the annuli from $i = 0$.

The sample $P$ consists of circles $C_i$ of radius $1 + \epsilon$ lying in the middle of the annuli ($C_i \subseteq A_i$), and pairs of points $\{p_i, \tilde{p}_i\}$. Each pair $\{p_i, \tilde{p}_i\}$ lies in the disk inside the annulus $A_i$, at a distance $\delta$ from $A_i$, and the two points lie at a distance $2r_i$ from each other. The bisector of $p_i$ and $\tilde{p}_i$ intersects the circle $C_i$ in two points. We let $q_i$ be the intersection point that is closest to $p_i$ (and thus $\tilde{p}_i$). We denote the circumradius of $p_i\tilde{p}_iq_i$ by $R_i$ and note that $R_i \ge r_i$.

<figure><img src="image_24.png" /><figcaption>■ **Figure 3** Each annulus $A_i$ is sampled by a circle $C_i$ and a pair of points $\{p_i, \tilde{p}_i\}$. The circumradius is indicated by $R_i$.</figcaption></figure>

We set $r_0 = \frac{\delta+\epsilon}{2}$ and, for $i \ge 0$,

$$r_{i+1} = \begin{cases} R_i, & \text{if } R_i < 1 - \delta, \\ 1 - \delta, & \text{otherwise.} \end{cases}$$

We stop the sequence at the first value of $i = k$ such that $r_k = 1 - \delta$. Our constructed set $\mathcal{S}$ consists of the finitely many annuli $A_0 \cup A_1 \cup \dots \cup A_k$ and our sample $P$ is defined as $\bigcup_{0 \le i \le k} C_i \cup \{p_i, \tilde{p}_i\}$. The topological transitions of the thickening of the sample $(P \oplus B(r))$ are illustrated in Figure 2 and described in the supplementary material [1].

## 2.2 Manifolds

The construction for manifolds goes as follows: We define $\mathcal{M}$ to be a union of tori of revolution $T_i \subseteq \mathbb{R}^3$. Each of these tori is the 1-offset of a circle (in the horizontal plane) of radius 2 in $\mathbb{R}^3$. We number the tori from $i = 0$, and lay them out in a row at a distance at least 2 apart from one another. Due to this assumption, the reach of $\mathcal{M}$ equals 1.

The sample $P$ consists of sets $C_i$ which are tori with a part cut out, and pairs of points $\{p_i, \tilde{p}_i\}$ lying inside the hole of each torus $T_i$. To construct each set $C_i$ we take the $\delta$-offset of $T_i$, keep the part that lies inside the solid torus bounded by $T_i$, and remove an $\epsilon$-neighbourhood of the circle obtained by revolving the point (1, 0, 0) around the $z$-axis; see the red set in Figures 4 and 5.
<figure><img src="image_17.png" /><figcaption>Figure 4 The (half of the) torus $T_i$ depicted in blue; the sample – the set $C_i$ and the points $p_i$ and $\tilde{p}_i$ – in red. In black we indicate the circle $C'_i$. The closest point projection of this circle onto $M$ is indicated in blue.</figcaption></figure>

Let $C'_i$ be the circle found by revolving the point $(1 - \delta, 0, 0)$ around the $z$-axis. Each pair of points $p_i$ and $\tilde{p}_i$ lies on $C'_i$ at a distance $2r_i$ from each other. Let $q_i$ and $\tilde{q}_i$ be those two points in the intersection of the bisector of $p_i$ and $\tilde{p}_i$ and the set $C_i$, that lie closest to $p_i$ and $\tilde{p}_i$. Note that $q_i$ and $\tilde{q}_i$ lie on the boundary of $C_i$ (where we think of $C_i$ as a manifold with boundary), and $\{q_i, \tilde{q}_i\} = \pi_{C_i}(\frac{p_i+\tilde{p}_i}{2})$. Denote the circumradius of the simplex $p_i\tilde{p}_i q_i \tilde{q}_i$ by $R_i$.

<figure><img src="image_18.png" /><figcaption>Figure 5 The sets $T_i$, $C_i$ and $C'_i$ are obtained by rotating around the $z$-axis, respectively, the blue circles, the red arcs and the white point.</figcaption></figure>

We define the distance $2r_i$ between each pair of points $p_i$ and $\tilde{p}_i$ inductively. We set the distance $r_0$ such that the balls $B(p_0, r)$ and $B(\tilde{p}_0, r)$ start to intersect at the same value of $r$ as the balls $B(q_0, r)$ and $B(\tilde{q}_0, r)$ start to intersect:

$$r_0 = \frac{1}{2} d(q_0, \tilde{q}_0) = \sqrt{\epsilon^2 - \left(\frac{\epsilon^2 - \delta^2 + 2\delta}{2}\right)^2}.$$

We then define

$$r_{i+1} = \begin{cases} R_i, & \text{if } R_i < 1 - \delta, \\ 1 - \delta, & \text{otherwise.} \end{cases}$$

We stop the sequence at the first value of $i = k$ such that $r_i = 1 - \delta$.
<figure><img src="image_25.png" /><figcaption>Figure 4 The (half of the) torus $T_i$ depicted in blue; the sample – the set $C_i$ and the points $p_i$ and $\tilde{p}_i$ – in red. In black we indicate the circle $C'_i$. The closest point projection of this circle onto $M$ is indicated in blue.</figcaption></figure>

Let $C'_i$ be the circle found by revolving the point $(1 - \delta, 0, 0)$ around the $z$-axis. Each pair of points $p_i$ and $\tilde{p}_i$ lies on $C'_i$ at a distance $2r_i$ from each other. Let $q_i$ and $\tilde{q}_i$ be those two points in the intersection of the bisector of $p_i$ and $\tilde{p}_i$ and the set $C_i$, that lie closest to $p_i$ and $\tilde{p}_i$. Note that $q_i$ and $\tilde{q}_i$ lie on the boundary of $C_i$ (where we think of $C_i$ as a manifold with boundary), and $\{q_i, \tilde{q}_i\} = \pi_{C_i}(\frac{p_i+\tilde{p}_i}{2})$. Denote the circumradius of the simplex $p_i\tilde{p}_i q_i \tilde{q}_i$ by $R_i$.

<figure><img src="image_26.png" /><figcaption>Figure 5 The sets $T_i$, $C_i$ and $C'_i$ are obtained by rotating around the $z$-axis, respectively, the blue circles, the red arcs and the white point.</figcaption></figure>

We define the distance $2r_i$ between each pair of points $p_i$ and $\tilde{p}_i$ inductively. We set the distance $r_0$ such that the balls $B(p_0, r)$ and $B(\tilde{p}_0, r)$ start to intersect at the same value of $r$ as the balls $B(q_0, r)$ and $B(\tilde{q}_0, r)$ start to intersect:

$$r_0 = \frac{1}{2} d(q_0, \tilde{q}_0) = \sqrt{\epsilon^2 - \left(\frac{\epsilon^2 - \delta^2 + 2\delta}{2}\right)^2}.$$

We then define

$$r_{i+1} = \begin{cases} R_i, & \text{if } R_i < 1 - \delta, \\ 1 - \delta, & \text{otherwise.} \end{cases}$$

We stop the sequence at the first value of $i = k$ such that $r_i = 1 - \delta$.
87:6 The Ultimate Frontier: An Optimality Construction for Homotopy Inference

Finally, the manifold $\mathcal{M}$ consists of the finitely many tori $T_0 \cup T_1 \cup \dots \cup T_k$, and the sample $P$ is defined as $\bigcup_{0 \le i \le k} (C_i \cup \{p_i, \tilde{p}_i\})$. The topological transitions of the thickening of the sample $(P \oplus B(r))$ are described in the supplementary material [1].

References

1 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Supplementary material: The ultimate frontier: An optimality construction for homotopy inference. *HAL preprint*, 2024. URL: https://hal.science/hal-04501285.

2 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth 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. *arXiv preprint*, accepted for *SoCG 2024*, 2024. arXiv:2206.10485.

3 Dominique Attali, André Lieutier, and David Salinas. Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes. *Computational Geometry*, 46(4):448–465, 2013. 27th Annual Symposium on Computational Geometry (SoCG 2011). doi:10.1016/j.comgeo.2012.02.009.

4 F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. *Discrete and Computational Geometry*, 41(3):461–479, 2009.

5 Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman. Homotopy Reconstruction via the Czech Complex and the Vietoris-Rips Complex. In Sergio Cabello and Danny Z. Chen, editors, *36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 54:1–54:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2020.54.

6 P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. *Discrete & Computational Geometry*, 39(1-3):419–441, 2008.

7 Yuan Wang and Bei Wang. Topological inference of manifolds with boundary. *Computational Geometry*, 88:101606, 2020. doi:10.1016/j.comgeo.2019.101606.
Finally, the manifold $\mathcal{M}$ consists of the finitely many tori $T_0 \cup T_1 \cup \dots \cup T_k$, and the sample $P$ is defined as $\bigcup_{0 \le i \le k} (C_i \cup \{p_i, \tilde{p}_i\})$. The topological transitions of the thickening of the sample $(P \oplus B(r))$ are described in the supplementary material [1].

References

1 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Supplementary material: The ultimate frontier: An optimality construction for homotopy inference. *HAL preprint*, 2024. URL: https://hal.science/hal-04501285.

2 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth 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. *arXiv preprint*, accepted for *SoCG 2024*, 2024. arXiv:2206.10485.

3 Dominique Attali, André Lieutier, and David Salinas. Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes. *Computational Geometry*, 46(4):448–465, 2013. 27th Annual Symposium on Computational Geometry (SoCG 2011). doi:10.1016/j.comgeo.2012.02.009.

4 F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. *Discrete and Computational Geometry*, 41(3):461–479, 2009.

5 Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman. Homotopy Reconstruction via the Czech Complex and the Vietoris-Rips Complex. In Sergio Cabello and Danny Z. Chen, editors, *36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 54:1–54:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2020.54.

6 P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. *Discrete & Computational Geometry*, 39(1-3):419–441, 2008.

7 Yuan Wang and Bei Wang. Topological inference of manifolds with boundary. *Computational Geometry*, 88:101606, 2020. doi:10.1016/j.comgeo.2019.101606.