# Supplementary material: The ultimate frontier: An optimality construction for homotopy inference

**Dominique Attali** [CV]

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

**Hana Dal Poz Kouřimská** [CV]

IST Austria
[Klosterneuburg, Austria]

**Christopher Fillmore** [CV]

IST Austria
[Klosterneuburg, Austria]

**Ishika Ghosh** [CV]

IST Austria
[Klosterneuburg, Austria]
Michigan State University
[East Lansing, USA]

**André Lieutier** [CV]

No affiliation
[Aix-en-Provence, France]

**Elizabeth Stephenson** [CV]

IST Austria
[Klosterneuburg, Austria]

**Mathijs Wintraecken** [CV]

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

## Abstract

In the supplementary material for the media contribution we focus on the topological transitions of the thickening of the samples we consider. To improve readability we include the description of the construction, which can also be found in the main submission.

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

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

**Digital Object Identifier** 10.4230/LIPICs...

**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_1.png" /></figure>

<figure><img src="image_2.png" /></figure>
# 1 The construction

We construct the set $\mathcal{S}$ (or the manifold $\mathcal{M}$) and the sample $\mathcal{P}$ that prove the optimality of our bounds. The video visualizes the construction. Note that due to rescaling it suffices to construct sets of reach equal to 1.

## 1.1 Sets of positive reach

The construction of a set $\mathcal{S}$ that illustrates the tightness of our bound 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\varepsilon$. We lay the annuli in a row at distance at least 2 away from each other and number them from $i = 0$.

The sample $\mathcal{P}$ consists of circles $C_i$ of radius $1 + \varepsilon$ 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$. Similarly, we let $q'_i$ be the intersection point that is furthest<fnref n="1" /> from $p_i$ (and thus $\tilde{p}_i$). We denote the circumradius of $p_i\tilde{p}_iq'_i$ by $R'_i$.

<figure><img src="image_3.png" /><figcaption>■ Figure 1 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+\varepsilon}{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 $\mathcal{P}$ is defined as $\bigcup_{0 \le i \le k} C_i \cup \{p_i, \tilde{p}_i\}$.

<footnote n="1">¹ If both intersection points are equidistant (as will be the case for $i = k$) we choose arbitrarily.</footnote>
<figure><img src="image_4.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_5.png" /><figcaption>(b) At radius $r_1$, the cycle 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_6.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_7.png" /><figcaption>■ **Figure 2** The changing homology of the set $P \oplus B(r)$ in the annuli $A_0, A_1, A_2$, and $A_k$.</figcaption></figure>

For every $r \ge 0$, the union of balls $P \oplus B(r)$ has different homology than the set $S$, where we use $\oplus$ to denote the Minkowski sum. We describe the development of the topology of the sets $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ as $r$ increases:

- For $r \in [0, r_0)$, each set $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has three connected components, as illustrated in Figure 2a. The three components merge into one at $r = r_0$, as the two balls $\{p_i\} \oplus B(r)$ and $\{\tilde{p}_i\} \oplus B(r)$ intersect the set $C_i \oplus B(r)$.

- For $r \in [r_i, r_{i+1})$, the set $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has the homotopy type of two circles that share a point (also known as a wedge of two circles or a bouquet), as illustrated in
**XX:4 Supplementary material: The ultimate frontier: Optimal homotopy inference**

Figures 2b and 2c. The smaller ‘hole’ creating the additional cycle appears when $r = r_i$. The hole persists until $r = R_i = r_{i+1}$. All sets $(C_j \cup \{p_j, \tilde{p}_j\}) \oplus B(r)$ with $j \neq i$ have the homotopy type of a circle.

- At $r = r_k = 1 - \delta$, all sets $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ have the homotopy type of a circle but the last one, $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$, which has the homotopy type of two circles that share a point (see Figure 2d). Unlike the other cases, however, the ‘holes’ in the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ are identical, and disappear simultaneously at $r = R_k$ (Figure 2e). For every larger $r$, the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ is contractible.

- Recall that $R'_i$ denotes the circumradius of the triangle $p_i \tilde{p}_i q'_i$. For $i < k$, $R'_k < R'_i < 1 + \varepsilon$, and each set $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ becomes contractible at $R'_i$.

- At $r = 1 + \varepsilon$ the connected components of $P \oplus B(r)$ merge.

## 1.2 Manifolds

The construction of the set $\mathcal{M}$ that illustrates the tightness of our bound for manifolds goes as follows: We define $\mathcal{M}$ to be a union of tori of revolution $T_i$ in $\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 $\varepsilon$-neighbourhood of the circle obtained by revolving the point (1, 0, 0) around the $z$-axis; see the red set in Figures 3 and 4.

<figure><img src="image_8.png" /><figcaption>■ **Figure 3** 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 $\mathcal{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 the 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<fnref n="2" /> of $C_i$, and $\{q_i, \tilde{q}_i\} = \pi_{C_i} (\frac{p_i+\tilde{p}_i}{2})$, where $\pi_{C_i}$ denotes the closest point projection on $C_i$. Denote the circumradius of the simplex $p_i \tilde{p}_i q_i \tilde{q}_i$ by $R_i$; see Figure 5.

We denote the mirror images of $q_i$ and $\tilde{q}_i$ in the $yz$ plane of Figure 4 by $q'_i$ and $\tilde{q}'_i$. Similarly, we write $R'_i$ for the circumradius of $p_i \tilde{p}_i q'_i \tilde{q}'_i$.

<footnote n="2">² Here we think of $C_i$ as a manifold with boundary.</footnote>
<figure><img src="image_9.png" /><figcaption>■ **Figure 4** 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>

<figure><img src="image_10.png" /><figcaption>■ **Figure 5** The torus $T_i$ (in blue), the sample $C_i \cup \{p_i, \tilde{p}_i\}$ (in red), the points $q_i, \tilde{q}_i$ (in red), and the circumsphere of $p_i \tilde{p}_i q_i \tilde{q}_i$ (in light grey below).</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$. In [1] we show that such a value indeed exists.

The manifold $\mathcal{M}$ thus 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\})$.
<figure><img src="image_11.png" /><figcaption>■ **Figure 6** The situation at $r_0$. The sample $P$ in red and its thickening $P \oplus B(r)$ (or boundary of the thickening) in purple. The balls $B(p_0, r_0)$ and $B(\tilde{p}_0, r_0)$ touch and the thickened torus $C_0 \oplus B(r_0)$ 'closes up' and generates 2-homology.</figcaption></figure>

For every $r \ge 0$, the union of balls $P \oplus B(r)$ has different homology than the set $\mathcal{M}$. We describe the development of the topology of the sets $\bigcup_{i=0}^k (C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r) = P \oplus B(r)$ as $r$ increases. For this we need to introduce some notation: We denote half the distance from $p_i$ to $C_i$ by $\mathbf{r}$. That is,

$$2\mathbf{r} = \sqrt{|\delta^2 + \varepsilon^2 + \delta(\varepsilon^2 - \delta^2 + 2\delta)|} = \sqrt{|\varepsilon^2(1 + \delta) + \delta^2(3 - \delta)|}.$$

Write $s$ and $s'$ for the points on $C_0$ that are closest to $p_0$ and write $\tilde{s}$ and $\tilde{s}'$ for the points on $C_0$ that are closest to $\tilde{p}_0$.

■ For $r \in [0, \min(\mathbf{r}, r_0))$ each set $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has three connected components. It has the homotopy type of a circle and two points.

<figure><img src="image_12.png" /><figcaption>■ **Figure 7** The two balls $\{p_0, \tilde{p}_0\} \oplus B(r)$ start touching $C_0 \oplus B(r)$. For these particular parameters $\mathbf{r} < r_0$, which means that the set directly after this point has the homotopy type of a bouquet of circles.</figcaption></figure>

■ For $r \in [\min(\mathbf{r}, r_0), \max(\mathbf{r}, r_0))$ there are two possibilities depending on whether $\mathbf{r} < r_0$ or $\mathbf{r} > r_0$. In the first case the set $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$ is homotopic to three topological circles that have a single point in common (also called a bouquet of three circles), see
Figure 7. If $r_0 < r$ the set $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$ will have the homotopy type of a torus and two points.

<figure><img src="image_13.png" /><figcaption>■ **Figure 8** The 2-cycle of the torus is being created in $C_0 \oplus B(r)$. At this point, also the two balls $\{p_0, \tilde{p}_0\} \oplus B(r)$ start touching.</figcaption></figure>

- For $r \in [\max(\mathfrak{t}, r_0), r_1)$ there are again a number of possibilities. Before we distinguish the cases we make some observations. We note that by assumption (on $r$) the line segments $p_0\tilde{p}_0$, $p_0s$, $p_0s'$, $\tilde{p}_0\tilde{s}$, and $\tilde{p}_0\tilde{s}'$ are contained in $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$. The points $s, s', \tilde{s}$, and $\tilde{s}'$ all lie on a 2-cycle (slightly deformed torus) that is contained in $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$, see Figure 8. The circumcentre of the simplex $p_0\tilde{p}_0q_0\tilde{q}_0$ is not contained in $(C_0 \cup \{p_0, \tilde{p}_0\}) \oplus B(r)$, again by assumption on $r$. We want to determine if the line segments $p_0\tilde{p}_0$, $p_0s$, $p_0s'$, $\tilde{p}_0\tilde{s}$, and $\tilde{p}_0\tilde{s}'$ form parts of some 1-cycles (and if so how many) or if the circumcentre of $p_0\tilde{p}_0q_0\tilde{q}_0$ is enclosed in a void.

This brings us to our case analysis. Firstly, the triangle $p_0ss'$ (and therefore the triangle $\tilde{p}_0\tilde{s}\tilde{s}'$) can be acute or obtuse. If it is acute we need to distinguish whether the circumradius of $p_0ss'$ lies inside $[\max(\mathfrak{t}, r_0), r_1)$ or not. If the circumradius does lie inside the interval $[\max(r_{-1}, r_0), r_1)$ then below that value of the circumradius the line segments $p_0s, p_0s'$, $\tilde{p}_0\tilde{s}$, and $\tilde{p}_0\tilde{s}'$ are not part of any boundary. This means that there are either three or one non-trivial 1-cycles. In both other cases (an acute triangle, but $r$ larger than the circumradius, or obtuse) these line segments do not contribute to a non-trivial cycle.

Secondly, we consider the triangle $p_0\tilde{p}_0q_0$ (and symmetrically the triangle $p_0\tilde{p}_0\tilde{q}_0$). This triangle is acute thanks to [1, Lemma 20]. If $r$ is smaller than the circumradius of this triangle, the segment $p_0\tilde{p}_0$ contributes to a 1-cycle. If $r$ is larger than the circumradius of this triangle, the segment $p_0\tilde{p}_0$ no longer contributes to a 1-cycle.

If none of the segments $p_0\tilde{p}_0$, $p_0s$, $p_0s'$, $\tilde{p}_0\tilde{s}$, and $\tilde{p}_0\tilde{s}'$ form parts of some 1-cycles, then the circumcentre of $p_0\tilde{p}_0q_0\tilde{q}_0$ is enclosed in a void (2-cycle), see Figure 9.

- For every $i \ge 2$ and $r \in [r_{i-1}, r_i)$, the set $(C_i \cup \{p_i, \tilde{p}_i\}) \oplus B(r)$ has homotopy type of a torus with either a circle or a 2-sphere attached, depending on whether the radius $r$ is smaller or larger than the circumradius of the triangle $p_i\tilde{p}_i q_i$. The tunnel or void appears when $r = r_{i-1}$ (and in the case of a tunnel it may change from a tunnel to a void when $r$ equals the circumradius of triangle $p_i\tilde{p}_i q_i$) and disappears at $r = R_i = r_{i+1}$.

- At $r = r_k = 1 - \delta$, the homotopy type of all sets $C_i \oplus B(r)$ changes from that of a torus to that of a circle, since the 'interior' of the torus fills up.

- For $r \ge 1 - \delta$, the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ has, at first, the homotopy type of two circles that share a point. The two gaps creating the two 1-cycles are identical. Thus, as the radius $r$ increases, the homotopy type of the set $(C_k \cup \{p_k, \tilde{p}_k\}) \oplus B(r)$ changes from
<figure><img src="image_14.png" /><figcaption>Figure 9 We see the void from two different viewpoints.</figcaption></figure>

that of two circles that share a point to that of two 2-spheres that share a point (there
are two voids that around the circumcentres of $p_k, \tilde{p}_k q_k, \tilde{q}_k$ and $p_k, \tilde{p}_k q'_k, \tilde{q}'_k$, which fill up
when $r = R_k$), to that of a point.

Similarly, the homology type of every other set ($C_i \cup \{p_i, \tilde{p}_i\} \oplus B(r)$) changes from that
of a circle to that of a 2-sphere (when $r$ equals the circumradius of the triangle $p_i, \tilde{p}_i q'_i$
which is also the circumradius of $p_i, \tilde{p}_i \tilde{q}'_i$), to that of a point (at $r = R'_i$). This happens for
$r$ larger than $1 - \delta$ because as long as $r < 1 - \delta$, the $z$-axis in Figure 4 is not intersected
by the thickening of the sample $P$.

References

1 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 arXiv:2206.10485*, accepted for *SoCG 2024*, 2024.