Estimation of Conformal Metrics

Jérôme Taupin

► To cite this version:

Jérôme Taupin. Estimation of Conformal Metrics. 2025. hal-05516466

HAL Id: hal-05516466

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

Preprint submitted on 18 Feb 2026

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Estimation of Conformal Metrics

## Jérôme Taupin

Université Paris-Saclay, France
INRIA Saclay, France

### Abstract

We study deformations of the geodesic distances on a domain of $\mathbb{R}^N$ induced by a function called conformal factor. We show that under a positive reach assumption on the domain (not necessarily a submanifold) and mild assumptions on the conformal factor, geodesics for the conformal metric have good regularity properties in the form of a lower bounded reach. This regularity allows for efficient estimation of the conformal metric from a random point cloud with a relative error proportional to the Hausdorff distance between the point cloud and the original domain. We then establish convergence rates of order $n^{-1/d}$ that are close to sharp when the intrinsic dimension $d$ of the domain is large, for an estimator that can be computed in $O(n^2)$ time. Finally, this paper includes a useful equivalence result between ball graphs and nearest-neighbors graphs when assuming Ahlfors regularity of the sampling measure, allowing to transpose results from one setting to another.

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

**Keywords and phrases** Geometric inference, metric estimation, conformal metric, geodesics, sets of positive reach

## 1 Introduction

This paper studies metrics over subsets of the Euclidean space $(\mathbb{R}^N, \|\cdot\|)$ obtained by conformal deformation of the shortest-path metric via a positive function. We are particularly interested in the regularity of such metrics and in their estimation via i.i.d. sampling of points.

**► Definition 1.1.** Let $M \subset \mathbb{R}^N$ be a closed path-connected domain and $f: M \to \mathbb{R}_+^*$ be a conformal factor. For all $x, y \in M$ the conformal distance between $x$ and $y$ over $M$ via $f$ is defined as

$$D_{M,f}(x, y) \stackrel{\text{def}}{=} \inf_{\gamma \in \Gamma_M(x,y)} \int_I f(\gamma(t)) \|\dot{\gamma}(t)\| dt \quad (1)$$

where $\Gamma_M(x, y)$ is the set of all Lipschitz paths $\gamma: I \to M$ where $I = [a, b]$ is a nontrivial segment, $\gamma(a) = x$ and $\gamma(b) = y$. The quantity minimized over all paths $\gamma$ is denoted

$$|\gamma|_f \stackrel{\text{def}}{=} \int_I f(\gamma(t)) \|\dot{\gamma}(t)\| dt$$

and referred to as the conformal length of the curve $\gamma$ via $f$. In the case where $f = 1$, we write $D_M(x, y) = D_{M,1}(x, y)$ and $|\gamma| = \int_I \|\dot{\gamma}\|$, respectively the distance between $x$ and $y$ induced by the ambient metric over $M$ and the Euclidean length of a curve $\gamma$.

In the following, to ensure regularity of the conformal metric, the domain $M$ is assumed to have positive reach $\tau_M$, which we recall is defined as the supremum of all $r > 0$ such that any point in the offset $M^r = \{x \in \mathbb{R}^N : d(x, M) < r\}$ has a unique projection onto $M$—where $d(x, M) = \inf_{y \in M} \|x - y\|$ denotes the distance from point $x$ to subset $M$—see [11]. Moreover, the conformal factor $f$ is assumed to be $\kappa$-Lipschitz and lower bounded by $f_{\min} > 0$. These are the sole assumptions used in this paper regarding $M$ and $f$.

Notice that $f$ is defined over $M$ in Theorem 1.1 as paths are constrained to the domain. Since any Lipschitz function defined over a subset of $\mathbb{R}^N$ can be extended to the whole space preserving its Lipschitz property and lower bound (see [17, Theorem 1] for instance), one
may assume without loss of generality that $f$ is defined over the entire space $\mathbb{R}^N$, which is
useful to estimate the conformal metric efficiently. The connectedness and positive reach of
$M$ ensure that for any endpoints $x, y \in M$, there exists a Lipschitz path from $x$ to $y$ in $M$,
so that $\Gamma_M(x, y)$ is always nonempty and $D_{M,f}(x, y)$ is always finite. This can be deduced
from Theorem 2.1 below. Most of the time, a path $\gamma$ is chosen to be parameterized with
constant velocity, i.e., $\|\dot{\gamma}\|$ is constant over $I$, with $I$ being either $[0, 1]$ or $[0, |\gamma|]$. The latter
is referred to as an *arc-length parameterization*, where $\|\dot{\gamma}\| = 1$ almost everywhere.

The *induced metric* $D_M = D_{M,1}$ is the metric induced by the ambient space $\mathbb{R}^N$ onto $M$. If $M$ is a $C^1$ submanifold of $\mathbb{R}^N$ and $f$ is $C^1$, $D_{M,f}$ is a Riemannian metric with tensor $f(x)^2 \cdot g_x$ at point $x \in M$ where $g_x$ is the tensor of the induced metric $D_M$ at $x$. The term “conformal” used in this paper is borrowed from the Riemannian literature. Finally, if $\mu$ is a measure over a submanifold $M$ with density $\rho$ with regard to (w.r.t.) the volume form of $M$ and $f$ is a negative power of the density $\rho$, $D_{M,f}$ has already been studied and is sometimes referred to as the *Fermat distance* [14]. This particular case is one of the main motivations for this article as the Fermat distance has been used for various practical applications, see for instance [13] and the references therein. Particular examples of the conformal factor $f$ are discussed in Section 5.

Conformal metrics are included in the more general class of length-spaces, for which it is
known that the infimum in Theorem 1.1 is in fact a minimum [7, Theorem 2.5.23]. That is, for
all $x, y \in M$ there exists a path $\gamma \in \Gamma_M(x, y)$ such that $D_{M,f}(x, y) = |\gamma|_f$, called a *minimizing geodesic*—and shortened to geodesic in this paper for brevity. Denote $\Gamma_{M,f}^*(x, y)$ the set of such geodesics between two endpoints $x$ and $y$ along with $\Gamma_{M,f}^* = \bigcup_{x \neq y \in M} \Gamma_{M,f}^*(x, y)$ the set of all geodesics w.r.t. the conformal metric. We discuss in Section 2 the regularity of geodesics w.r.t. $D_{M,f}$ and show in Theorem 2.4 that under the aforementioned assumptions on $M$ and $f$, geodesics have positive reach that is lower bounded by an explicit constant depending on the reach of the domain and on the conformal factor. In particular, any geodesic may be parameterized as a $C^{1,1}$ curve with an explicit upper bound on the Lipschitz constant of its first derivative.

We then show in Section 3 that the conformal metric can be approached using polygonal
paths on a weighted graph built from a point cloud $X \subset M$, provided that the graph only
contains edges of length at most some threshold $r$ and that $X$ is close to $M$ in Hausdorff
distance. The small edges condition ensures that paths on the graph cannot venture too far
outside the domain. This kind of construction is the same as the one used for the Isomap
algorithm [5], although we allow more generality by adapting the weights to the conformal
factor $f$. When $f=1$ and $M$ is a geodesically convex $C^2$ submanifold, [5] provides a relative
error bound of order $r^2/\tau^2 + \rho/r$ where $\tau$ is the minimum radius of curvature of $M$ and $\rho$ denotes
the Hausdorff distance between $M$ and $X$. The term depending on $\rho$ can be made quadratic
as shown in [2], where an assumption called geodesic smoothness that is slightly weaker than
that of a positive reach allows to obtain a bound of order $Ar + \rho^2/r^2$ where $A$ depends on
the assumption. This assumption however lacks precision when comparing distances at a
local scale which results in the first term being of order $r$ instead of $r^2$. By using a positive
reach assumption instead, the upper bound can be further improved to $r^2/\tau^2 + \rho^2/r^2$ according
to [3] where $\tau$ is the reach of the domain, although the setup also implicitly assumes that
the domain $M$ is a smooth manifold isometric to a convex domain. Going back to our
setup, we adapt these prior works to fit any conformal change. Under some condition on the
weight function used, that in particular always holds for the induced metric, we establish in
Theorem 3.5 the same upper bound on the approximation error as in [3], that is $r^2/\tau^2 + \rho^2/r^2$ where
$\tau$ is the explicit lower bound on the reach of any geodesic provided by Theorem 2.4. This
result emphasizes the fact that the only assumption on the domain needed for this level of precision is that of a positive reach. The approximation error can thus be made proportional to the Hausdorff distance between the point cloud and the domain by choosing appropriately $r \asymp \sqrt{\tau \rho}$. When the conformal factor $f$ is unknown, replacing it with an estimate $g$ does not alter the results provided that $g$ is close enough to $f$, as shown in Theorem 3.6.

Assuming that $X = X_n$ is the outcome of $n \ge 1$ i.i.d. samples from a $d$-standard measure $\mu$ over $M$, we study in Section 4 the estimator of $D_{M,f}$ built on $X_n$ following the construction of Section 3. This estimator is shown in Theorem 4.2 to converge to $D_{M,f}$ at a rate of $n^{-1/d}$ provided that $f$ is known or can be estimated with same rate. This rate follows from Theorem 3.5 and the fact that $X_n$ is known to converge to $M$ in Hausdorff distance at a rate of $n^{-1/d}$. In particular, this allows for efficient estimation of the induced metric with the sole assumption that $M$ has positive reach. This convergence is shown using ball graphs. However, practical estimation is made easier by using nearest-neighbors graphs instead, in part because it does not require to know the intrinsic dimension $d$ to obtain an optimal convergence speed. For this reason, we show in Theorem 4.5 that it is possible to retrieve the same convergence speed when replacing the ball graph in the estimator with a $k$-nearest-neighbors graph with $k \asymp \sqrt{n}$. To do so, we establish an equivalence with high probability between nearest-neighbors graphs and ball graphs when their respective parameters are properly scaled and the underlying measure is $d$-Ahlfors, see Theorem 4.4. Finally, the nearest-neighbors estimator of the conformal distance between two fixed points may be computed in $O(n^2)$ if the time complexity of evaluating $f$ is considered constant. Under the stronger assumption that $M$ is a $C^k$ submanifold of dimension $d$ with $k \ge 2$, the minimax optimal convergence rate for the induced metric is known to be of order $n^{-k/d}$ [1]. When only assuming positive reach and no differential structure on $M$, the discussion of the optimal minimax rate proves to be harder as we are not able to match the upper bound of $n^{-1/d}$ and obtain a lower bound of order $n^{-1/(d-1/2)}$ instead, see Theorem 4.6. We discuss with more details the comparison between our setup and the $C^k$ case in Section 4.4.

## 2 Regularity of the Geodesics for the Conformal Metric

Recall that the term “geodesic” refers in this paper to a curve that achieves a global minimum of the conformal length. In this section we study the regularity of the geodesics w.r.t. $D_{M,f}$. We show that geodesics are $C^{1,1}$ curve with reach bounded from below by a constant depending only on $\tau_M$, $\kappa$ and $f_{\min}$. This regularity property is crucial to obtain a good approximation of the geodesics by polygonal paths. The reach of a set can be characterized through the local distortion of the induced metric compared to the Euclidean metric.

**► Lemma 2.1.** [6, Theorem 1] The reach of $M$ may be expressed as

$$ \tau_M = \sup \left\{ r > 0 : \forall x, y \in M, \|x - y\| < 2r \Rightarrow D_M(x, y) \le 2r \arcsin \left( \frac{\|x - y\|}{2r} \right) \right\}. $$

Given a path $\gamma \in \Gamma_M$ parameterized over an interval $I$ and without self-intersection, denote $\tau_\gamma$ the reach of the curve $\gamma(I) \subset \mathbb{R}^N$ along with $D_\gamma = D_{\gamma(I)}$ the induced metric over the curve for short. $D_\gamma(x, y)$ is nothing more than the length of the curve $\gamma(I)$ between two intermediate point $x$ and $y$. In particular if $x$ and $y$ are the endpoints of $\gamma$ then $D_\gamma(x, y) = |\gamma|$. One consequence of Theorem 2.1 is that the length of a geodesic between two points at most $2\tau_M$ apart is upper bounded by the length of an arc of radius $\tau_M$ between both points. That
4 Estimation of Conformal Metrics

is, if $x, y \in M$ and $\|x - y\| < 2\tau_M$ then

$$D_M(x, y) \le 2\tau_M \arcsin \left( \frac{\|x - y\|}{2\tau_M} \right). \qquad (2)$$

Moreover, if $\gamma$ is a geodesic, it then induces a geodesic between any of the points it goes through, which implies that $D_\gamma$ is exactly the restriction of $D_M$ to the curve $\gamma$. Then, another consequence of the characterization of Theorem 2.1 is that the reach of $M$ is the minimal reach of any geodesic, that is

$$\tau_M = \inf_{\gamma \in \Gamma_M^*} \tau_\gamma.$$

We now introduce a notion of reach associated with the conformal deformation of $M$ by $f$ using the same point of view of the metric and its geodesics.

**Definition 2.2.** The conformal reach of $M$ via $f$ is defined as the minimal reach of any geodesic w.r.t. the conformal metric, that is

$$\tau_{M,f} \stackrel{\text{def}}{=} \inf_{\gamma \in \Gamma_{M,f}^*} \tau_\gamma.$$

In the case of the induced metric this notion coincides with the usual notion of reach, that is $\tau_{M,1} = \tau_M$. The characterization given by Theorem 2.1 also holds for the conformal reach.

**Proposition 2.3.** The conformal reach of $M$ via $f$ may be expressed as

$$\tau_{M,f} = \sup \left\{ \begin{array}{l} r > 0 : \forall x, y \in M, \forall \gamma \in \Gamma_{M,f}^*(x, y), \\ \|x - y\| < 2r \Rightarrow |\gamma| \le 2r \arcsin \left( \frac{\|x - y\|}{2r} \right) \end{array} \right\}. \qquad (3)$$

Beware that Equation (3) involves geodesic w.r.t. the conformal metric $D_{M,f}$, but compares their Euclidean length—not conformal—to the one of an arc of radius $r$.

**Proof.** Denote $A$ the subset of $\mathbb{R}_+^*$ that appears in the right-hand side of Equation (3) and let us show that its supremum is indeed $\tau_{M,f}$. Since a geodesic induces a geodesic between any pair of points it goes through, one can write $A = \bigcap_\gamma A_\gamma$ where the intersection is taken over all geodesics w.r.t. $D_{M,f}$ and

$$A_\gamma = \left\{ r > 0 : \forall x, y \in \gamma, \|x - y\| < 2r \Rightarrow D_\gamma(x, y) \le 2r \arcsin \left( \frac{\|x - y\|}{2r} \right) \right\}.$$

Theorem 2.1 states that $\tau_\gamma = \sup A_\gamma$ and standard reasoning over ordered sets shows that

$$\tau_{M,f} = \inf_{\gamma} \tau_{\gamma} = \inf_{\gamma} \sup A_{\gamma} \ge \sup \bigcap_{\gamma} A_{\gamma} = \sup A.$$

Moreover, for all $x, y \in M$, $r \mapsto 2r \arcsin (\|x - y\|/2r)$ is a non-increasing function over $(\|x - y\|, +\infty)$, which implies that for all $\gamma$, if $r \in A_\gamma$ then $s \in A_\gamma$ for all $0 < s \le r$. In particular, it follows that the inequality above is in fact an equality, hence $\tau_{M,f} = \sup A$ which concludes the proof. ◀

Using Theorem 2.3, we are able to lower bound the reach of any geodesic w.r.t. $D_{M,f}$.
**Proposition 2.4.** Assume that M has positive reach $\tau_M > 0$ and that f is $\kappa$-Lipschitz and lower bounded by $f_{\min} > 0$. Then any conformal geodesic $\gamma$ w.r.t. $D_{M,f}$ has positive reach $\tau_\gamma > 0$. Precisely, the conformal reach of M via f is lower bounded as follows.

$$ \tau_{M,f} \geq \mathcal{T}_{M,f} \quad \text{where} \quad \mathcal{T}_{M,f} \stackrel{\text{def}}{=} \min \left( \frac{\tau_M}{2}, \frac{f_{\min}}{8\kappa} \right). $$

The reasoning behind Theorem 2.4 is the following. If the reach of a geodesic $\gamma$ w.r.t. $D_{M,f}$ is small compared to $\tau_M$, then according to Theorem 2.3 there exists a path in M significantly shorter than $\gamma$ Euclidean-wise. If $\tau_\gamma$ is also small compared to $f_{\min}/\kappa$, then this path is shown to also have a shorter conformal length than $\gamma$ due to the properties of f, which implies a contradiction with the geodesic nature of $\gamma$. This reasoning is detailed in Section B.2. Now, consider an arc-length parameterized geodesic $\gamma: I \to M$ w.r.t. $D_{M,f}$, i.e., such that $\|\dot{\gamma}\| = 1$ almost everywhere over I. Being a geodesic, $\gamma$ has no self-intersection. Then, stating that $\gamma$ has positive reach is equivalent to stating that $\gamma$ is a $C^{1,1}$ curve, i.e., that $\dot{\gamma}$ is Lipschitz w.r.t. the angular distance. Precisely, for all $t, s \in I$,

$$ \angle(\dot{\gamma}(t), \dot{\gamma}(s)) \leq \frac{|t-s|}{\tau_{\gamma}}. \qquad (4) $$

See [11, Remark 4.20] and [16, Theorem 4] for references. Equation (4) allows to obtain a finer control on the approximation error of the polygonal paths on the graph by upper bounding efficiently the difference between small successive steps $\gamma(t) - \gamma(t - \delta)$ and $\gamma(t + \delta) - \gamma(t)$ of a geodesic path.

**Lemma 2.5.** Let $\gamma: [0, |\gamma|] \to \mathbb{R}^N$ be an arc-length parameterized curve without self-intersection and with positive reach $\tau_\gamma$. Then for all $t_0 \in [0, |\gamma|]$ and $\delta \in (0, \frac{\pi}{2}\tau_\gamma]$ such that $[t_0 - \delta, t_0 + \delta] \subset [0, |\gamma|]$, the angle between the velocity vector of $\gamma$ at $t_0$ and the direction from $\gamma(t_0)$ to $\gamma(t_0 + \delta)$ is upper bounded as follows:

$$ \angle(\gamma(t_0 + \delta) - \gamma(t_0), \dot{\gamma}(t_0)) \leq \frac{\delta}{2\tau_{\gamma}}. \qquad (5) $$

Moreover, denoting $v^- = \gamma(t_0) - \gamma(t_0 - \delta)$ and $v^+ = \gamma(t_0 + \delta) - \gamma(t_0)$, the difference between small steps of the path on both side from $t_0$ is upper bounded as follows:

$$ \left\| \frac{v^+}{\|v^+\|} - \frac{v^-}{\|v^-\|} \right\| \leq \frac{1}{\tau_\gamma} \min (\|v^+\|, \|v^-\|). \qquad (6) $$

Theorem 2.5 is key to obtain an approximation error of the conformal metric proportional to the Hausdorff distance between the domain and a point cloud. A proof is provided in Section A.1 and Equation (5) is illustrated by Figure 1.

## 3 Polygonal Approximation of the Conformal Metric

Consider a point cloud $X \subset M$ of points sampled from the domain. If the point cloud approximates well the domain, it is possible to estimate the conformal distance over M through weighted polygonal paths built over X within a small margin of error. Assuming that f is known, the edges of the polygonal path are weighted using f to approximate the conformal distance between their endpoints. The degree of approximation of M by X is measured using the Hausdorff distance

$$ d_H(M, X) \stackrel{\text{def}}{=} \max \left( \sup_{x \in M} d(x, X), \sup_{x \in X} d(x, M) \right) $$
<figure><img src="image_2.png" /><figcaption>Figure 1 Bounding the angular velocity of a path with positive reach.</figcaption></figure>

which simplifies to $d_H(M, X) = \sup_{x \in M} d(x, X)$ assuming that $X \subset M$. By definition, any point in $M$ is at distance at most $d_H(M, X)$ from a point in $X$.

The idea behind the polygonal approximation is the following. Consider a geodesic $\gamma \in \Gamma_{M,f}^*(x, y)$ between two points $x, y \in M$. If $d_H(M, X)$ is small, there exists a polygonal path over $X$ that follows closely the trajectory of $\gamma$. Assuming that the edges of this path are equipped with appropriate weights to simulate the conformal distance between their endpoints, the total weight of the polygonal path should be close to the conformal length $|\gamma|_f$. Moreover, since $\gamma$ is a geodesic, polygonal paths should not be able to have a weight much smaller than $|\gamma|_f$. This is ensured by using only short edges, which allows the weights to approximate well the conformal length by preventing shortcuts outside the domain. In the end, the shortest weighted path on the graph is expected to retrieve $|\gamma|_f = D_{M,f}(x, y)$.

## 3.1 Weighted Graphs

Let us now describe formally this construction. The polygonal approximation of $D_{M,f}$ is defined as the metric of an appropriate weighted graph on a point cloud $X$.

**Definition 3.1.** Let $X \subset \mathbb{R}^N$ be a finite point cloud.

- For all $r > 0$, the r-ball graph over $X$ is denoted $G_r(X)$ and is the graph of vertex set $X$ and with an edge between points $x$ and $y$ if and only if $\|x - y\| \le r$.

- For all integer $k \ge 1$, the k-nearest-neighbors graph (or k-NN graph) over $X$ is denoted $G_k(X)$ and is the graph of vertex set $X$ with an edge between two points $x$ and $y$ if and only if $x$ (or $y$) is among the k nearest points of $X$ to $y$ (or $x$) excluding self. In both cases, the parameter $r$ or $k$ is referred to as the threshold of the graph.

Ball graphs are more convenient to study whereas NN graphs are more practical, see Section 4.2. We define the polygonal metric in both contexts. The graph used is equipped with a weight function to approximate the conformal length of its edges.

**Definition 3.2.** Given a function $f: \mathbb{R}^N \to \mathbb{R}_+^*$, consider the weight functions

$$w_{f,q}(x, y) \stackrel{\text{def}}{=} \frac{\|x - y\|}{2(q - 1)} \left( f(x) + 2 \sum_{k=2}^{q-1} f\left(\frac{q-k}{q-1}x + \frac{k-1}{q-1}y\right) + f(y) \right)$$

defined for any $q \ge 2$ and $x, y \in \mathbb{R}^N$, along with

$$w_{f,\infty}(x, y) \stackrel{\text{def}}{=} \|x - y\| \int_{0}^{1} f((1 - t)x + ty)dt.$$

The parameter $q \in \{2, \dots, \infty\}$ is referred to as the resolution of the weights.
The weight function $w_{f,q}$ is meant to approximate the conformal distance between the endpoints of an edge. Theorem 3.3 below shows that it is indeed the case when the endpoints are close, which is the reason why graphs with small edges are used. Recall that we have assumed without loss of generality that $f$ is defined over the whole space, allowing its evaluation outside $M$ when $q \neq 2$. As $q$ grows, the weight $w_{f,q}$ becomes more accurate and converges to the weight with infinite resolution $w_{f,\infty}$, the latter being exactly the conformal length of the straight path. However, the computational cost is linear with $q$ and there is no closed-form formula for $w_{f,\infty}$ in general. On the other hand,

$$w_{f,2}(x, y) = \|x - y\| \frac{f(x) + f(y)}{2}$$

is the simplest choice for the weights and may be more suitable if evaluating $f$ is possible only at points in $X$. Note that the weight $w_{f,q}$ is the optimal approximation of $w_{f,\infty}$ using only $q$ samples of the Lipschitz function $f$. Under stronger assumptions on $f$ such as $C^k$ regularity, other definitions would be better suited.

**Proposition 3.3.** For all $x, y \in M$ such that $\|x - y\| \le \tau_{M,f}$,

$$\left| 1 - \frac{w_{f,q}(x, y)}{D_{M,f}(x, y)} \right| \le \frac{\kappa}{4f_{\min}} \frac{\|x - y\|}{q - 1} + \frac{\|x - y\|^2}{16T_{M,f}^2} . \qquad (7)$$

and we denote $\delta_q(\|x - y\|)$ this upper bound. The first term in Equation (7) is to be interpreted as 0 if $q = \infty$ and represents the offset between $w_{f,q}$ and $w_{f,\infty}$, whereas the second term represents the offset between $w_{f,\infty}$ and $D_{M,f}$.

Theorem 3.3 shows that the conformal metric $D_{M,f}$ may be approximated locally by the weights $w_{f,q}$. Note that for fixed resolution $q$ in the $r$-ball graph, the distortion between the weights and the conformal distances is linear in $r$. However, by choosing $q$ to be inversely proportional to $r$, the distortion becomes quadratic in $r$. The proof for Theorem 3.3 is provided in Section B.3. We now introduce the polygonal approximation of the conformal metric as the metric of the weighted graph built on $X$.

**Definition 3.4.** Consider a point cloud $X \subset \mathbb{R}^N$, function $f: \mathbb{R}^N \to \mathbb{R}_+^*$ and parameters $r > 0$ or $k \ge 1$ and $q \in \{2, \dots, \infty\}$. The polygonal metric associated with these parameters is defined between two points $x, y \in \mathbb{R}^N$ as

$$\hat{D}_{X,f}(x, y) \stackrel{\text{def}}{=} \min_{(x_0, \dots, x_K)} \sum_{k=0}^{K-1} w_{f,q}(x_k, x_{k+1}) \qquad (8)$$

where the minimum is taken over the set of paths $(x_0, \dots, x_K)$ such that $x_0 = x$ and $x_K = y$ in the graph $G$ that is chosen either as the $r$-ball graph $G_r(X \cup \{x, y\})$ or the $k$-NN graph $G_k(X \cup \{x, y\})$.

The choice of a ball graph or a NN graph along with the threshold $r$ or $k$ and the resolution $q$ of the weights are left implicit when writing $\hat{D}_{X,f}$ to avoid heavy notations. Note that when the endpoints $x$ and $y$ do not belong to the point cloud, the distance $\hat{D}_{X,f}(x, y)$ is computed by adding them to the graph. As a result, $\hat{D}_{X,f}$ induces a distance over $X$ but not over $M$. Indeed, when considering endpoints outside $X$, $\hat{D}_{X,f}$ may not satisfy the triangular inequality due to the set of possible paths depending on the endpoints.
## 3.2 Metric Approximation

To evaluate how efficient is the approximation of a metric, the error between the true distances and their estimation may be measured using either of the multiplicative loss functions

$$ \ell_{\infty,M}(D', D) \stackrel{\text{def}}{=} \sup_{x \neq y \in M} \left| \frac{D'(x, y) - D(x, y)}{D'(x, y) \vee D(x, y)} \right| \quad \text{and} \quad l_{\infty,M}(D'|D) \stackrel{\text{def}}{=} \sup_{x \neq y \in M} \left| 1 - \frac{D'(x, y)}{D(x, y)} \right| $$

In the case where $D'$ takes infinite values—which happens for instance when $D'$ is the metric of a non-connected graph—we let $\ell_{\infty,M}(D', D) = 1$ and $l_{\infty,M}(D'|D) = +\infty$. The inequality

$$ \ell_{\infty,M}(D', D) \le l_{\infty,M}(D'|D) \le \frac{\ell_{\infty,M}(D', D)}{1 - \ell_{\infty,M}(D', D)} \quad (9) $$

holds in general, so that both losses are equivalent. The loss $\ell_{\infty,M}$ is however easier to manipulate in some situations as it is symmetric and upper bounded by 1. Thanks to the regularity of geodesics stated by Theorem 2.4 and the local approximation of the conformal metric by the weights $w_{f,q}$ stated by Theorem 3.3, we are able to show that the conformal metric $D_{M,f}$ is approximated by the polygonal metric from Theorem 3.4 using the r-ball graph.

**▶ Theorem 3.5.** Let $X \subset M$ be a point cloud, $r > 0$ and $q \in \{2, \dots, \infty\}$ two parameters. Assume that $4d_H(M, X) \le r \le T_{M,f}$. Then the approximation $\hat{D}_{X,f}$ defined in Theorem 3.4 using the r-ball graph with resolution $q$ satisfies

$$ l_{\infty,M}(\hat{D}_{X,f}|D_{M,f}) \le \frac{1}{32T_{M,f}(q-1)} + \frac{r^2}{8T_{M,f}^2} + 56 \frac{d_H(M, X)^2}{r^2}. \quad (10) $$

The first term in Equation (10) is to be interpreted as 0 if $q = \infty$.

Let us describe the reasoning behind Theorem 3.5. Given $x \neq y \in X$, paths in $G_r(X)$ cannot create significant shortcuts outside $M$ as $r \le \tau_{M,f}$. This is illustrated by Theorem 3.3 from which it can be deduced that

$$ \hat{D}_{X,f}(x, y) \ge (1 - \delta_q(r)) D_{M,f}(x, y) \quad (11) $$

and, assuming that $\|x - y\| \le r$,

$$ \hat{D}_{X,f}(x, y) \le (1 + \delta_q(r)) D_{M,f}(x, y). \quad (12) $$

As for when $\|x - y\| > r$, consider a geodesic $\gamma \in \Gamma_{M,f}^*(x, y)$. Decompose $\gamma$ into sections of length at most $r - 2d_H(M, X)$ and for each intermediate point select a point in $X$ at distance at most $d_H(M, X)$. This process draws a polygonal path in $G_r(X \cup \{x, y\})$ as it uses edges of length at most $r$. Summing the approximation error from Theorem 3.3 between each edge of this path and the corresponding section of $\gamma$ eventually yields the upper bound

$$ \hat{D}_{X,f}(x, y) \le \left( 1 + \delta_q(r) + c_1 \frac{d_H(M, X)}{T_{M,f}} + c_2 \frac{d_H(M, X)^2}{r^2} \right) D_{M,f}(x, y) \quad (13) $$

when $\|x - y\| > r$ and where $c_1$ and $c_2$ are universal constants. The positive reach of $\gamma$ and Theorem 2.5 play a crucial role in obtaining terms of order $d_H(M, X)/T_{M,f}$ and $d_H(M, X)^2/r^2$ instead of $d_H(M, X)/r$. Together, Equations (11)–(13) eventually imply Equation (10). The
details of this reasoning are provided in Section B.4. The upper bound in Equation (10) is made proportional to $d_H(M, X)$ by setting

$$r \asymp \sqrt{T_{M,f} d_H(M, X)} \quad \text{and} \quad q \asymp \sqrt{\frac{T_{M,f}}{d_H(M, X)}}.$$

In the case of the induced metric with $f = 1$, the first term in the right-hand side of Equation (10) disappears, and the error is of order $r^2/\tau_M^2 + d_H(M, X)^2/r^2$ similarly to the one obtained in [3]. In the general conformal case, we keep this magnitude of error by setting the resolution $q$ to be at least of order $1/r$. If it is not possible to evaluate $f$ outside the point cloud $X$, setting $q = 2$ instead yields an error of order $r/T_{M,f} + d_H(M, X)^2/r^2$ which is slightly worse. A similar upper bound was achieved in [2] for the induced metric and the term linear in $r$ was due to the geodesically smooth assumption used in the paper being slightly weaker than a positive reach assumption. In particular, the latter allows for an efficient local estimation in the form of Equation (12). The main takeaway of Theorem 3.5 is that the crucial assumption to achieve an approximation error proportional to $d_H(M, X)$ is the positive reach. In particular, the domain need not be $C^2$, or even a submanifold.

## 3.3 Unknown Conformal Factor

In general, $f$ may not be known and needs to be estimated from the data. The polygonal metric $\hat{D}_{X,g}$ from Theorem 3.4 can be defined for any function $g: \mathbb{R}^N \to \mathbb{R}_+$ without the need of Lipschitz and lower bound assumptions. Then, the approximation error between $\hat{D}_{X,g}$ and $D_{M,f}$ is upper bounded by the sum of the error w.r.t. the conformal factor and the error w.r.t. the domain.

**Lemma 3.6.** Let $f: \mathbb{R}^N \to \mathbb{R}_+$ a function lower bounded by $f_{\min}$, $X \subset M$ a point cloud and $g: \mathbb{R}^N \to \mathbb{R}_+$ such that $\|g - f\|_{\infty} \le \frac{1}{2}f_{\min}$. Then

$$\ell_{\infty,M}(\hat{D}_{X,g}, D_{M,f}) \le \frac{2}{f_{\min}} \|g - f\|_{\infty} + 2\ell_{\infty,M}(\hat{D}_{X,f}, D_{M,f}). \quad (14)$$

This result holds regardless of the type of graph, threshold and resolution as long as they are shared between $\hat{D}_{X,f}$ and $\hat{D}_{X,g}$.

The proof of Theorem 3.6 consists in straightforward computations and is deferred to Section B.5. As a consequence, in the context of estimation of the domain $M$ by a point cloud $X_n$ as in Section 4 and of the conformal factor $f$ by a function $f_n: \mathbb{R}^N \to \mathbb{R}_+$, the rate of convergence of $\hat{D}_{X_n,f_n}$ towards $D_{M,f}$ is the slowest rate of convergence among that of $\hat{D}_{X_n,f}$ towards $D_{M,f}$ and that of $f_n$ towards $f$. Recall that $f_n$ is not required to satisfy the Lipschitz and lower bounded assumptions for the polygonal metric $\hat{D}_{X_n,f_n}$ to be defined and for Theorem 3.6 to hold. It may also be defined only over $X_n$ if the resolution is set to $q = 2$.

# 4 Estimation from Random Samples

In this section we transpose Theorem 3.5 to a probabilistic setup where the point cloud $X$ is replaced with a random point cloud $X_n$ consisting of $n$ i.i.d. samples from a probability measure $\mu$ with support $M$. The following assumptions on $\mu$ are needed to ensure that $X_n$ covers $M$ efficiently as $n$ grows, allowing to deduce explicit convergence rates for the estimator $\hat{D}_{X_n,f}$ from Theorem 3.5.

**Definition 4.1.** Consider a probability measure $\mu$ with support $M \subset \mathbb{R}^N$ and $d \ge 2$.
■ The measure $\mu$ is d-standard with lower constant $c_\mu > 0$ if for all $x \in M$ and $r > 0$,

$$ \mu(B(x, r)) \geq c_{\mu} r^{d} \wedge 1 $$

where $B(x, r)$ denotes the open ball centered at $x$ with radius $r$.

■ The measure $\mu$ is d-Ahlfors with lower and upper constants $c_\mu > 0$ and $C_\mu > 0$ if for all $x \in M$ and $r > 0$,

$$ c_{\mu} r^{d} \wedge 1 \leq \mu(B(x, r)) \leq C_{\mu} r^{d}. $$

If $\mu$ is d-standard with lower constant $c_\mu$, we also denote $L_\mu = c_\mu^{-1/d}$ which is related to the size of the support. The definition ensures that $\mu(B(x, L_\mu)) = 1$ for all $x \in M$, hence $L_\mu \geq \text{diam}(M)$. Moreover, $d$ acts as the intrinsic dimension of the support $M$ of $\mu$. For instance, any measure with a density $\rho$ w.r.t. the volume measure of a submanifold of $\mathbb{R}^N$ of dimension $d$ is d-Ahlfors if $\rho$ is bounded above and below. The d-standard assumption ensures that the random point cloud $X_n$ converges to $M$ in Hausdorff distance. Ahlfors regularity is a stronger assumption and is needed to show the equivalence between ball graphs and NN graphs in Theorem 4.4.

## 4.1 Convergence of the Ball Graph Estimator

We first discuss the case of a ball graph estimator. It is known that if $\mu$ is d-standard, then $d_H(M, X_n)$ is of order $L_\mu(\log(n)/n)^{1/d}$ at most, see Section A.2. This convergence combined with Theorem 3.5 allows to derive convergence rates for the estimation of $D_{M,f}$.

**► Theorem 4.2.** Assume that $X_n$ is the result of $n$ i.i.d. samples from a d-standard probability measure $\mu$ with support $M$. Consider the estimator $\hat{D}_{X_n,f}$ from Theorem 3.4 using the r-ball graph with resolution $q$ where $r$ and $q$ are specified below. Then there exists a constant $n_0$ depending on $L_\mu$, $T_{M,f}$ and $d$ such that for all $n \geq n_0$ the following holds.

■ If $r = 8\sqrt{L_\mu T_{M,f}} \left(\frac{\log(n)}{n}\right)^{\frac{1}{2d}}$ and $q \geq 1 + 4\frac{T_{M,f}}{r}$, then

$$ \mathbb{E} \left[ \ell_{\infty,M} (\hat{D}_{X_n,f}, D_{M,f}) \right] \leq 16 \frac{L_\mu}{T_{M,f}} \left( \frac{\log(n)}{n} \right)^{\frac{1}{d}}. \qquad (15) $$

■ If $r = 8L_\mu^{2/3} T_{M,f}^{1/3} \left(\frac{\log(n)}{n}\right)^{\frac{2}{3d}}$ and $q = 2$, then

$$ \mathbb{E} \left[ \ell_{\infty,M} (\hat{D}_{X_n,f}, D_{M,f}) \right] \leq 8 \left( \frac{L_\mu}{T_{M,f}} \right)^{\frac{2}{3}} \left( \frac{\log(n)}{n} \right)^{\frac{2}{3d}}. \qquad (16) $$

The first case in Theorem 4.2 includes $q = \infty$. There is no use setting $q$ to be greater than the indicated threshold of order $T_{M,f}/r$, as the term in the upper bound depending on $q$ becomes negligible past this threshold. Note that the optimal choice for $r$ and $q$ requires the knowledge of $L_\mu$, $T_{M,f}$ and most importantly $d$. Theorem 4.2 is stated with these choices of parameters to highlight the optimal theoretical dependency in these constants. For practical purposes, the knowledge of $L_\mu$ and $T_{M,f}$ is not actually needed as, in general, any choice of $r \asymp (\log(n)/n)^{1/2d}$ and $q \gtrsim 1/r$ yields a convergence rate of $(\log(n)/n)^{1/d}$. Likewise, any choice of $r \asymp (\log(n)/n)^{2/3d}$ and $q = 2$ yields a convergence rate of $(\log(n)/n)^{2/3d}$. It is not possible however to get rid of the dependency in $d$ for the range parameter $r$ without altering the convergence rate. To circumvent this issue, one may use the NN graph instead, for which the optimal choice of the parameter is shown in Section 4.2 to be $k = \sqrt{n}$ which does not
depend on $d$. Theorem 4.2 is derived directly from Theorem 3.5 and the convergence of $X_n$ to $M$ in Hausdorff distance. The precise computations are deferred to Section C.1. In the case of the induced metric, the weight function $w_{f,q}$ becomes the Euclidean distance regardless of the resolution and $T_{M,f}$ is replaced with $\tau_M$.

**Corollary 4.3.** Under the same assumptions as in Theorem 4.2 and when $f = 1$, there exists a constant $n_0$ depending on $L_\mu$, $\tau_M$ and $d$ such that for all $n \ge n_0$, setting $r = 8\sqrt{L_\mu\tau_M(\log(n)/n)^{1/2d}}$, the estimator $\hat{D}_{X_{n,1}}$ satisfies

$$ \mathbb{E} [ \ell_{\infty,M}(\hat{D}_{X_{n,1}}, D_M) ] \le 16 \frac{L_\mu}{\tau_M} \left( \frac{\log(n)}{n} \right)^{\frac{1}{d}} . $$

Recall that in the case of a submanifold of class $C^k$ with $k \ge 2$ and dimension $d$, the optimal convergence rate for the estimation of the induced metric is $n^{-k/d}$ [1]. Theorem 4.3 extends the upper bound to any set of positive reach with the convergence rate $n^{-1/d}$.

## 4.2 Convergence of the Nearest-Neighbors Graph Estimator

We now treat the case of a NN graph estimator, by observing that for adequate choice of $r$ and $k$, the $r$-ball graph and $k$-NN graph are similar. Indeed, assuming that $\mu$ is $d$-Ahlfors regular, a ball of radius $r$ is expected to contain between $c_\mu nr^d$ and $C_\mu nr^d$ points from $X_n$.

**Proposition 4.4.** Let $\mu$ be a $d$-Ahlfors measure as defined in Theorem 4.1 and $X_n$ a point cloud sampled i.i.d. from $\mu$. Let $k \ge 1$, $\varepsilon \in (0, 1)$ and define

$$ r_{-} = \left( (1 - \varepsilon) \frac{k}{C_{\mu}(n-1)} \right)^{\frac{1}{d}} \quad \text{and} \quad r_{+} = \left( \frac{1}{1 - \varepsilon} \frac{k}{c_{\mu}(n-1)} \right)^{\frac{1}{d}} . $$

Then with probability at least $1 - 2ne^{-\varepsilon^2k/2}$, the $k$-NN graph $\mathcal{G}_k(X_n)$ is enclosed between two ball graphs $G_{r_{-}}(X_n)$ and $G_{r_{+}}(X_n)$, that is

$$ \mathbb{P} (G_{r_{-}}(X_n) \subset \mathcal{G}_k(X_n) \subset G_{r_{+}}(X_n)) \ge 1 - 2n \exp \left( -\frac{\varepsilon^2}{2} k \right) $$

where the inclusion $\subset$ refers to the inclusion of edge sets.

Theorem 4.4 shows that if $r$ and $k$ are chosen such that $k \asymp nr^d$, the $k$-NN graph and the $r$-ball graph are very similar with high probability. This result stems from a common intuition and a detailed proof is provided in Section A.3 for completeness. Theorem 4.2 is then extended to $k$-NN graphs by choosing $k \asymp \sqrt{n \log(n)}$, which does not depend on $d$.

**Theorem 4.5.** Assume that $X_n$ is the result of $n$ i.i.d. samples from a $d$-Ahlfors probability measure $\mu$ with support $M$. Consider the estimator $\hat{D}_{X_{n,f}}$ from Theorem 3.4 using the $k$-NN graph with parameters $k = \lceil \sqrt{n \log(n)} \rceil$ and $q = \lceil n^{1/4} \rceil$. Then there exists a constant $n_0$ depending on $L_\mu$, $T_{M,f}$ and $d$ such that for all $n \ge n_0$ the following holds.

$$ \mathbb{E} [ \ell_{\infty,X_n}(\hat{D}_{X_{n,f}}, D_{M,f}) ] \le C \left( \frac{\log(n)}{n} \right)^{\frac{1}{d}} $$

where $C$ is a constant depending on $L_\mu$ and $T_{M,f}$.

Notice that in Theorem 4.5 the loss is over $X_n$ instead of $M$ like in Theorem 4.2. The same result could be stated over $M$, although the proof would be more tedious and is
12 Estimation of Conformal Metrics

therefore omitted here. Recall that no knowledge on either $d$, $c_μ$, $C_μ$, $τ_M$, $κ$ or $f_{min}$ is
necessary to compute the estimator, so that it can be used in practice. Setting the resolution
$q$ to be $(n/\log(n))^{1/2d}$ would be sufficient to achieve the same upper bound, however this
choice requires the knowledge of $d$. On the other hand, when setting the resolution to
$q = 2$ the optimal choice of $k$ can be shown similarly to be $k = n^{1/3}\log(n)^{2/3}$ and to
yield a convergence rate of order $(\log(n)/n)^{2/3d}$. Theorem 4.5 is a direct consequence of
Theorems 4.2 and 4.4 and the precise computations are provided in Section C.2. Regarding
the case of the induced metric, the same statement as in Theorem 4.3 holds for NN graphs.
Namely, the estimator $\hat{D}_{X,n,1}$ defined over the $k$-NN graph with $k = \lceil\sqrt{n\log(n)}\rceil$ converges
to $D_M$ at rate $(\log(n)/n)^{1/d}$.

Let us now discuss the algorithmic complexity of the k-NN estimator with resolution $q$. In general, building the k-NN graph over a point cloud $X$ of size $n$ is done in $O(n^2N)$ time when the ambient dimension $N$ is large. Now, consider two points $x, y \in \mathbb{R}^N$ and assume that $f$ can be evaluated at any point with cost $c_f$. Computing the edges of the graph $G_k(X \cup \{x, y\})$ takes $O(nkqc_f)$ time as the amount of edges in the graph is $O(nk)$ and the weight of each edge uses $q$ evaluations of $f$. Finally, computing the infimum that defines $D_{X,f}(x, y)$ in Theorem 3.4 using Dijkstra's algorithm takes $O(n\log(n) + nk)$ time. Overall, if $k = \lceil\sqrt{n\log(n)}\rceil$ and $q = \lceil n^{1/4}\rceil$, the time complexity is $O(n^2N + n^{7/4}\log(n)^{1/2}c_f)$.

4.3 Minimax lower bound

We now study the worst case performance of any estimator of the induced metric $D_M$.

► **Theorem 4.6.** *Denote $\mathcal{D}_n$ the set of all estimators $\hat{D}$ of the induced metric based on $n$ samples, that given any point cloud $X$ of $n$ points in $\mathbb{R}^N$ provides a function $\hat{D}_X : \mathbb{R}^N \times \mathbb{R}^N \to \mathbb{R}_+$. Let $2 \le d \le N$, $L, \tau > 0$ and $\mathcal{M}(d, L, \tau)$ be the set of all $d$-standard measures $\mu$ with $L_\mu \le L$ and support $M_\mu \subset \mathbb{R}^N$ that has positive reach lower bounded by $\tau$. Then there exists two constants $C > 0$ and $n_0$ depending on $d$, $L$ and $\tau$ such that for all $n \ge n_0$,*

$$
\inf_{\hat{D} \in \mathcal{D}_n} \sup_{\mu \in \mathcal{M}(d, L, \tau)} \mathbb{E}_{X \sim \mu \otimes n} [\ell_{\infty, M_\mu}(\hat{D}_X, D_{M_\mu})] \ge C \left(\frac{1}{n}\right)^{\frac{1}{d-1/2}}. \quad (17)
$$

Notice that Theorem 4.6 only addresses the case of the induced metric. This is not a
loss of generality and in fact highlights the fact that the conformal change does not make
the problem any harder, as we have established in Section 2 that geodesics have the same
regularity as in the case of the induced metric. Given any other function $f$ satisfying the
assumptions for a conformal metric, the same lower bound may be obtained with a similar
reasoning as what follows, albeit with more technicalities. The rate $n^{-1/(d-1/2)}$ is faster than
the rate $n^{1/d}$ obtained in Theorems 4.2 and 4.5, although the difference becomes negligible
when $d$ is large. The nature of the minimax convergence rate remains therefore open. Under
stronger assumptions on the domain, this question is already solved—see [1]—which we
discuss in Section 4.4.

Theorem 4.6 is based on Le Cam’s method [19], for which a statement adapted to our setup is given in Theorem C.1. The method consists in finding two measures $\mu_1$ and $\mu_2$ in $M(d, L, \tau)$ that are at most $1/n$ apart in total variation distance and such that the relative difference between $D_{M_1}$ and $D_{M_2}$ is of order at least $n^{-1/(d-1/2)}$.

Consider $\mu_1$ the uniform probability on the cube $M_1 = [-\alpha L, \alpha L]^d \times \{0\}^{N-d} \subset \mathbb{R}^N$ where $\alpha > 0$. Let $0 < \varepsilon \le \alpha L \wedge \tau$ and consider $M_2$ the result of removing from $M_1$ its intersection with a ball of radius $\tau$ centered at $(0, t, t, \dots, t)$ for some $t > \alpha L$ such that the ball intersects the edge from $(-\alpha L, \alpha L, \alpha L, \dots, \alpha L)$ to $(\alpha L, \alpha L, \alpha L, \dots, \alpha L)$ at two points $x$ and $y$ that
<figure><img src="image_3.png" /><figcaption>■ **Figure 2** Carving an edge of the cube in $\mathbb{R}^3$.</figcaption></figure>

are $2\epsilon$ apart, as pictured in Figure 2. Denote $\mu_2$ the uniform probability over $M_2$, which has reach exactly $\tau$ due to the carved area. By choosing $\alpha$ small enough, which depends only on $d$, $\mu_1$ and $\mu_2$ are $d$-standard with lower constant $L^{-d}$. Then $\mu_1$ and $\mu_2$ both belong to $M(d, L, \tau)$. The volume of the carved area is of order $\epsilon(\epsilon^2)^{d-1}$ as it spans a length $2\epsilon$ between $x$ and $y$ and a length of order $\epsilon^2$ for every other dimension of the cube. This implies that the total variation distance between $\mu_1$ and $\mu_2$ is of order $\epsilon^{2d-1}$. Moreover, The distance from $x$ to $y$ goes from $2\epsilon$ in $M_1$ to $2\tau$ arcsin($\epsilon/\tau$) in $M_2$, following the red arc of radius $\tau$ in Figure 2. This implies that the relative difference between both distances is of order $\epsilon^2$. Choosing $\epsilon \asymp n^{-1/2d-1}$ so that the total variation distance is at most $1/n$ eventually yields the desired bound. This reasoning is detailed in Section C.3.

Using this method, the above construction leads to a minimax lower bound that does not quite fit the upper bound from Theorem 4.2. If a better lower bound can be obtained, it is likely that it would require a different technique. Indeed, given fixed endpoints $x$ and $y$ at distance $\epsilon$ from each other and belonging to the intersection of two domains $M_1$ and $M_2$ with lower bounded reach, the relative difference between $D_{M_1}(x, y)$ and $D_{M_2}(x, y)$ is of order at most $\epsilon^2$ due to the reach assumption. Then, in order to achieve such distortion, it is reasonable to expect that the volume of the difference between $M_1$ and $M_2$ needs to be of order at least $\epsilon$ in the direction of $x-y$ and at least $\epsilon^2$ in the other directions to ensure that the uniform measures are $d$-standard, which leads to a volume of order $\epsilon^{2d-1}$ as in the previous construction.

## 4.4 Case of a Smooth Manifold

Recall that the minimax convergence rate for the induced metric of a $C^k$ manifold of dimension $d$ is $n^{-k/d}$ [1]. The methods that achieve such rates are however not computationally feasible in practice as they rely on manifold reconstruction via non-discrete sets. For instance, the optimal convergence rate in the $C^2$ case was achieved by [3] using the tangential Delaunay complex. Precisely, these methods build an approximation of the manifold that is at Hausdorff distance of order $n^{-k/d}$, then state that the induced metric over this reconstruction is an estimation of the original metric with an error proportional to the Hausdorff distance, that is of order $n^{-k/d}$.

In order to get a concrete estimator, one may use such manifold reconstruction, then sample a fine $n^{-k/d}$-net over it which approximates the original domain with the same Hausdorff error. Our work then implies that the polygonal metric over this net would be an estimation of the original metric with minimax optimal error of order $n^{-k/d}$. Such
construction would however be very costly as the point cloud size would grow from $n$ to $n^k$.

# 5 Practical Examples of Conformal Factors

We discuss two examples of conformal factors associated with a measure from the literature.

## 5.1 Density as a conformal factor

If $\mu$ is a measure with density $\rho$ w.r.t. the volume measure over a submanifold $M$, the conformal change via $f = \rho^{-\beta}$ for some parameter $\beta > 0$ is sometimes referred to as the *Fermat distance* due to the parallel with the Fermat principle in optics—that may however be observed with any conformal change. This metric has been applied to various topological data analysis and learning problems, e.g., in [12, 13], as it tends to accentuate features and disparities in the data. Moreover, the metric can be estimated in a simple fashion by using the same overall reasoning as ours but using weights of the form $w(x, y) = \|x - y\|^{\alpha}$ where $\alpha > 1$ is a parameter depending on $\beta$ and $d$ [14, 15]. However, this kind of estimation does not feature any known convergence rate. Using our estimator instead provides an alternative method with quantitative guarantees, granted that an estimator of the density is available. To this extent, density estimation is a well-studied problem with many propositions in the literature. For instance, [4] provides a kernel density estimator $\rho_n$ that converges in $L^p$ norm towards $\rho$ at a rate of $n^{-1/d+1}$ under our assumptions and provided that $M$ is a $C^1$ submanifold and that $\rho$ is also $C^1$. Under these assumptions, setting $f_n = \rho_n^{-\beta}$ yields a convergence rate of $n^{-1/d}$ according to Theorem 3.6, at the cost of a more complex computation than the usual discrete Fermat distance studied in [14].

## 5.2 Distance-to-measure as a conformal factor

In general, given a parameter $m \in (0, 1)$, the *distance-to-measure* $d_{\mu,m}: \mathbb{R}^N \to \mathbb{R}_+$ introduced in [8] is defined for any measure $\mu$ over $\mathbb{R}^N$. It is 1-Lipschitz and lower bounded by a positive value as long as $\mu$ has no atom, hence satisfies the assumption for our work. A slightly different setup where paths are allowed to leave the domain under a specific constraint is studied in [18], where it is argued that this metric should behave similarly to the conformal metric associated with the density but with more stability w.r.t. the measure. The distance-to-measure is shown [10] to be estimated from $n$ i.i.d. samples of the underlying measure with convergence rate $n^{-1/2}$, which is faster than $n^{-1/d}$ hence does not impact the convergence speed of the estimator of the conformal metric according to Theorem 3.6.

# 6 Conclusion

In this work, we have shown that under a reach assumption on the domain and Lipschitz lower bounded assumptions on the conformal change, the conformal metric has the same regularity as the induced metric in the sense of geodesics having positive reach. We have also shown that positive reach is a sufficient assumption to ensure metric estimation from a polygonal metric with error proportional to the Hausdorff distance between the point cloud and the original domain. This leads to a convergence rate of order $n^{-1/d}$ for the estimation of the conformal metric using $n$ i.i.d. samples from a $d$-standard measure, which in particular applies to the induced metric of any set with positive reach.
References

1 Eddie Aamari, Clément Berenfeld, and Clément Levrard. Optimal reach estimation and metric learning. *The Annals of Statistics*, 51(3):1086–1108, 2023-06. doi:10.1214/23-A0S2281.

2 Catherine Aaron and Olivier Bodart. Convergence rates for estimators of geodesic distances and Frèchet expectations. *Journal of Applied Probability*, 55(4):1001–1013, 2018-12. doi: 10.1017/jpr.2018.66.

3 Ery Arias-Castro, Adel Javanmard, and Bruno Pelletier. Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning. *Journal of Machine Learning Research*, 21(1):498–534, 2020. URL: http://jmlr.org/papers/v21/18-720.html.

4 Clément Berenfeld and Marc Hoffmann. Density estimation on an unknown submanifold. *Electronic Journal of Statistics*, 15(1):2179–2223, 2021-01. doi:10.1214/21-EJS1826.

5 Mira Bernstein, Vin Silva, John Langford, and Joshua Tenenbaum. Graph Approximations to Geodesics on Embedded Manifolds, 2000-12-20. URL: https://api.semanticscholar.org/ CorpusID:10751942.

6 Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. *Journal of Applied and Computational Topology*, 3(1):29–58, 2019-06-01. doi:10.1007/s41468-019-00029-8.

7 Dmitri Burago, Yuri Burago, and Sergei Ivanov. *A Course in Metric Geometry*, volume 33 of *Graduate Studies in Mathematics*. American Mathematical Society, 2001-06-12. doi: 10.1090/gsm/033.

8 Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. Geometric Inference for Measures based on Distance Functions. *Foundations of Computational Mathematics*, 11(6):733, 2011. doi:10.1007/s10208-011-9098-0.

9 Frédéric Chazal, Marc Glisse, Catherine Labruère, and Bertrand Michel. Convergence Rates for Persistence Diagram Estimation in Topological Data Analysis. *Journal of Machine Learning Research*, 16(110):3603–3635, 2015. URL: http://jmlr.org/papers/v16/chazal15a.html.

10 Frédéric Chazal, Pascal Massart, and Bertrand Michel. Rates of convergence for robust geometric inference. *Electronic Journal of Statistics*, 10(2):2243–2286, 2016-01. doi:10.1214/ 16-EJS1161.

11 Herbert Federer. Curvature measures. *Transactions of the American Mathematical Society*, 93(3):418–491, 1959. doi:10.1090/S0002-9947-1959-0110078-1.

12 Ximena Fernández, Eugenio Borghini, Gabriel Mindlin, and Pablo Groisman. Intrinsic persistent homology via density-based metric learning. *Journal of Machine Learning Research*, 24(1):75:3341–75:3382, 2023-01-01. URL: https://jmlr.org/papers/v24/21-1044.html.

13 Nicolas Garcia Trillos, Anna Little, Daniel McKenzie, and James M. Murphy. Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms. *Journal of Machine Learning Research*, 25(1):176:8331–176:8395, 2024-01-01. URL: http://jmlr.org/papers/v25/23-0939.html.

14 Pablo Groisman, Matthieu Jonckheere, and Facundo Sapienza. Nonhomogeneous Euclidean first-passage percolation and distance learning. *Bernoulli*, 28(1):255–276, 2022-02. doi: 10.3150/21-BEJ1341.

15 Sung Jin Hwang, Steven B. Damelin, and Alfred O. Hero Iii. Shortest path through random points. *The Annals of Applied Probability*, 26(5):2791–2823, 2016-10. doi:10.1214/ 15-AAP1162.

16 André Lieutier and Mathijs Wintraecken. Manifolds of positive reach, differentiability, tangent variation, and attaining the reach, 2024-12-06. arXiv:2412.04906.

17 E. J. McShane. Extension of range of functions. *Bulletin of the American Mathematical Society*, 40(12):837–842, 1934. doi:10.1090/S0002-9904-1934-05978-0.

18 Jérôme Taupin and Frédéric Chazal. Fermat Distance-to-Measure: A robust Fermat-like metric, 2025-04-03. arXiv:2504.02381.
19 Bin Yu. Assouad, Fano, and Le Cam. Research Papers in Probability and Statistics, 1997. doi:10.1007/978-1-4612-1880-7_29.

A Intermediate Results

This section is devoted to the proofs of some intermediate results used in the main text.

A.1 Rate of Change of a Curve with Positive Reach

In this section we prove Theorem 2.5. Let $v^+ = \gamma(t_0 + \delta) - \gamma(t_0)$ and $v^- = \gamma(t_0) - \gamma(t_0 - \delta)$.
The angle between two non-zero vectors is the arccosine of the dot product of the normalized
vectors, thus

$$
\angle(v^+, \dot{\gamma}(t_0)) = \arccos\left(\left\langle\frac{v^+}{\|v^+\|}, \dot{\gamma}(t_0)\right\rangle\right). \qquad (18)
$$

$$
\text{Since } v^+ = \gamma(t_0 + \delta) - \gamma(t_0) = \int_{t_0}^{t_0+\delta} \dot{\gamma}(t) dt,
$$

$$
\langle v^+, \dot{\gamma}(t_0) \rangle = \int_{t_0}^{t_0+\delta} \langle \dot{\gamma}(t), \dot{\gamma}(t_0) \rangle dt = \int_{t_0}^{t_0+\delta} \cos(\angle(\dot{\gamma}(t), \dot{\gamma}(t_0))) dt . \quad (19)
$$

Moreover, $\|v^+\| = \|\gamma(t_0 + \delta) - \gamma(t_0)\| \le \delta$ as $\gamma$ is 1-Lispchitz, and cos is non-increasing over $[0, \frac{\pi}{2}]$. Therefore, Equations (4) and (19) imply that

$$
\left\langle \frac{v^+}{\|v^+\|}, \dot{\gamma}(t_0) \right\rangle = \frac{1}{\|v^+\|} \int_{t_0}^{t_0+\delta} \cos \left( \angle(\dot{\gamma}(t), \dot{\gamma}(t_0)) \right) dt \ge \frac{1}{\delta} \int_{t_0}^{t_0+\delta} \cos \left( \frac{t-t_0}{\tau_\gamma} \right) dt . \quad (20)
$$

Now, since arccos is non-increasing and concave over $[0, 1]$, Equations (18) and (20) together
with Jensen's inequality yield

$$
\angle(v^+, \dot{\gamma}(t_0)) \le \arccos \left( \frac{1}{\delta} \int_{t_0}^{t_0+\delta} \cos \left( \frac{t-t_0}{\tau_\gamma} \right) dt \right) \le \frac{1}{\delta} \int_{t_0}^{t_0+\delta} \frac{t-t_0}{\tau_\gamma} dt = \frac{\delta}{2\tau_\gamma}
$$

which concludes Equation (5). The same result holds when comparing $\dot{\gamma}(t_0)$ to a small
variation before $t_0$ instead of after, therefore

$$
\angle(v^+, v^-) \le \angle(v^+, \dot{\gamma}(t_0)) + \angle(v^-, \dot{\gamma}(t_0)) \le \frac{\delta}{\tau_\gamma}.
$$

Moreover, applying Equation (2) to the induced metric on the curve $\gamma$ between endpoints $\gamma(t_0)$ and either $\gamma(t_0 + \delta)$ or $\gamma(t_0 - \delta)$ shows that

$$
\delta \le \min \left( 2\tau_{\gamma} \arcsin \left( \frac{\|v^+\|}{2\tau_{\gamma}} \right), 2\tau_{\gamma} \arcsin \left( \frac{\|v^-\|}{2\tau_{\gamma}} \right) \right).
$$

Finally,

$$
\left\| \frac{v^+}{\|v^+\|} - \frac{v^-}{\|v^-\|} \right\| = 2 \sin \left( \frac{1}{2} \angle(v^+, v^-) \right) \le 2 \sin \left( \frac{\delta}{2\tau_\gamma} \right) \le \frac{1}{\tau_\gamma} \min (\|v^+\|, \|v^-\|)
$$

which concludes Equation (6).
## A.2 Convergence of a Point Cloud in Hausdorff Distance

Recall the convergence in probability of the Hausdorff distance between an i.i.d. point cloud and the support of a d-standard measure.

**Lemma A.1.** [9, Theorem 2] Let $X_n$ be sampled i.i.d. from a d-standard measure $\mu$ with support $M$ and lower constant $c_\mu$. Then for all $\varepsilon > 0$,

$$ \mathbb{P}(d_H(M, X_n) > \varepsilon) \le \frac{4^d}{c_\mu \varepsilon^d} \exp\left(-n \frac{c_\mu \varepsilon^d}{2^d}\right). $$

To establish our results in Section 4, we require the convergence of the Hausdorff distance in expectation.

**Corollary A.2.** Under the same assumptions as in Theorem A.1 and assuming that $n \ge 8$, for all $1 \le p \le 2d$ it holds that

$$ \mathbb{E}[d_H(M, X_n)^p] \le \frac{2^{3p/2}}{c_\mu^{p/d}} \left(\frac{\log(n)}{n}\right)^{p/d}. $$

**Proof.** Denote $Z = d_H(M, X_n)$, $c = 4^d/c_\mu$ and $\alpha = c_\mu n/2^d$ for simplicity, so that

$$ \mathbb{P}(Z > t) \le \frac{c}{t^d} \exp(-\alpha t^d) \quad (21) $$

for all $t > 0$ according to Theorem A.1. Then, the expectation of $Z^{2d}$ can be written as

$$ \mathbb{E}[Z^{2d}] = \int_{0}^{+\infty} \mathbb{P}(Z^{2d} > u)du = \int_{0}^{+\infty} 2dt^{2d-1}\mathbb{P}(Z > t)dt. $$

Given any $t_0 > 0$, upper bounding the probability by 1 when $t \le t_0$ and using Equation (21) when $t > t_0$ instead yields

$$ \mathbb{E}[Z^{2d}] \le \int_{0}^{t_0} 2dt^{2d-1}dt + 2c \int_{t_0}^{+\infty} dt^{d-1} \exp(-\alpha t^d)dt = t_0^{2d} + \frac{2c}{\alpha} \exp(-\alpha t_0^d). $$

Then, setting $t_0 = (\log(n)/\alpha)^{1/d}$ and replacing $c$ and $\alpha$ with their definition yields

$$ \mathbb{E}[Z^{2d}] \le 2^{2d} \left( \frac{\log(n)}{c_\mu n} \right)^2 + \frac{2^{3d+1}}{c_\mu^2 n^2} = \left( 2^{2d} + \frac{2^{3d+1}}{\log(n)^2} \right) \left( \frac{\log(n)}{c_\mu n} \right)^2 \le 2^{3d} \left( \frac{\log(n)}{c_\mu n} \right)^2 $$

by lower bounding $\log(n)^2 \ge 4$ when $n \ge 8$. Finally, using Jensen's inequality yields the desired inequality for all $1 \le p \le 2d$, that is

$$ \mathbb{E}[Z^p] \le \mathbb{E}[Z^{2d}]^{\frac{p}{2d}} \le 2^{\frac{3p}{2}} \left( \frac{\log(n)}{c_\mu n} \right)^{\frac{p}{d}}. $$

## A.3 Ball Graphs and Nearest-Neighbors Graphs

In this section we prove Theorem 4.4. Denote $X_n = (x_1, \dots, x_n) \sim \mu^{\otimes n}$ the point cloud. As a preliminary result, denote for all $n \in \mathbb{N}^*$, $p \in (0, 1)$ and $k \in \mathbb{R}$, $\phi(n, p, k)$ the probability that a random variable following the binomial law with parameters $n$ and $p$ is greater than
k. Denote $\psi(n, p, k)$ the probability that a random variable with same law is smaller than $k$. Then for all $k > np$,

$$ \phi(n, p, k) \le \exp \left( \left( 1 + \log \left( \frac{np}{k} \right) - \frac{np}{k} \right) k \right), \qquad (22) $$

and for all $k < np$,

$$ \psi(n, p, k) \le \exp \left( \left( 1 + \log \left( \frac{np}{k} \right) - \frac{np}{k} \right) k \right). \qquad (23) $$

Indeed, both quantities may be upper bounded using a Chernoff bound by

$$ \left(\frac{np}{k}\right)^k \left(\frac{n-np}{n-k}\right)^{n-k} = \left(\frac{np}{k}\right)^k \left(1 + \frac{k-np}{n-k}\right)^{n-k} \le \left(\frac{np}{k}\right)^k e^{k-np}. $$

Now consider $k \in \{1, \dots, n-1\}$, $\varepsilon \in (0, 1)$ and let

$$ r_{-} = \left( (1 - \varepsilon) \frac{k}{C_{\mu}(n-1)} \right)^{\frac{1}{d}} \quad \text{and} \quad r_{+} = \left( \frac{1}{1 - \varepsilon} \frac{k}{c_{\mu}(n-1)} \right)^{\frac{1}{d}}. $$

For all $x \in M$, denote $p_x^- = \mu(B(x, r_-))$, which is upper bounded by $p^- = C_\mu(r_-)^d$ by Ahlfors assumption. Denote $A_i^-$ the event that $B(x_i, r_-)$ contains at least $k$ points from $X_n \setminus \{x_i\}$. Then, since each of the $n-1$ other sample points has a probability $p_x^- \le p^-$ of falling within $B(x, r_-)$,

$$ \mathbb{P}(A_i^-) = \int_M \mathbb{P}(A_i^- | x_i = x) \, d\mu(x) = \int_M \phi(n-1, p_x^-, k) \, d\mu(x) \le \phi(n-1, p^-, k). $$

Notice that $(n-1)p^- = (1 - \varepsilon)k < k$. Then, according to Equation (22),

$$ \mathbb{P}(A_i^-) \le \exp \left( (1 + \log(1 - \varepsilon) - 1 + \varepsilon)k \right) \le \exp \left( -\frac{\varepsilon^2}{2}k \right). $$

If the graph $G_{r_-}(X_n)$ is not included in $G_k(X_n)$, then there exists two sample points $x_i$ and $x_j$ that are at most $r_-$ apart but such that neither of them is one of the $k$ nearest neighbors of the other, and in particular $A_i^-$ holds. Then

$$ \mathbb{P} \left( G_{r_{-}}(X_{n}) \not\subset \mathcal{G}_{k}(X_{n}) \right) \le \mathbb{P} \left( \bigcup_{i=1}^{n} A_{i}^{-} \right) \le n \exp \left( -\frac{\varepsilon^2}{2}k \right). \qquad (24) $$

For all $x \in M$ denote $p_x^+ = \mu(\bar{B}(x, r_+))$, which is lower bounded by $p^+ = c_\mu(r_+)^d$ by Ahlfors assumption. Denote $A_i^+$ the event that $\bar{B}(x_i, r_+) \subset B(x, r_+)$ contains at most $k-1$ points from $X_n \setminus \{x_i\}$. Then, since each of the $n-1$ other sample points has a probability $p_x^+ \ge p^+$ of falling within $\bar{B}(x, r_+)$,

$$ \mathbb{P}(A_i^+) = \int_M \mathbb{P}(A_i^+ | x_i = x) \, d\mu(x) = \int_M \psi(n-1, p_x^+, k-1) \, d\mu(x) \le \psi(n-1, p^+, k). $$

Notice that $k = (1 - \varepsilon)(n - 1)p^+ < (n - 1)p^+$. Then, according to Equation (23),

$$ \mathbb{P}(A_i^+) \le \exp \left( \left( 1 + \log \left( \frac{1}{1-\varepsilon} \right) - \frac{1}{1-\varepsilon} \right) k \right) \le \exp \left( -\frac{\varepsilon^2}{2}k \right). $$
If the graph $G_k(X_n)$ is not included in $G_{r_+}(X_n)$, then there exists two sample points $x_i$ and $x_j$ that are more than $r_-$ apart but such that $x_j$ is one of the $k$ nearest neighbors of $x_i$, and in particular $A_i^+$ holds. Then

$$ \mathbb{P}(G_k(X_n) \not\subset G_{r_+}(X_n)) \le \mathbb{P}\left(\bigcup_{i=1}^{n} A_i^+\right) \le n \exp\left(-\frac{\varepsilon^2}{2}k\right). \qquad (25) $$

Finally, it follows from Equations (24) and (25) that

$$ \mathbb{P}(G_{r_{-}}(X_n) \subset G_k(X_n) \subset G_{r_{+}}(X_n)) \ge 1 - 2n \exp \left( -\frac{\varepsilon^2}{2}k \right) $$

which concludes the proof of Theorem 4.4.

## B Deterministic Technical Proofs

This section is devoted to technical proofs involving paths of positive reach and the objects studied in Section 3.

### B.1 Length of Paths

In this section we state some useful inequalities deduced from Equation (2) along with lemmas for comparing the conformal length of paths. The following quantities are all valid upper bounds of $\arcsin(t) - t$ for all $0 < t \le \frac{1}{2}$, which is deduced from elementary computations.

$$ \frac{\arcsin(t)^3}{6}, \quad 4\left(1-\frac{3}{\pi}\right)\arcsin(t)t^2, \quad 4\left(\frac{\pi}{3}-1\right)t^3, \quad \frac{1}{8}(\arcsin(2t)-2t). \qquad (26) $$

The lower bounds

$$ \arcsin(t) - t \ge \arcsin(t) \frac{t^2}{6} \ge \frac{t^3}{6} \qquad (27) $$

also hold for all $0 \le t \le 1$. Applying the upper bounds from Equation (26) to Equation (2) with $t = \|x - y\|/2\tau_M$ yields the following inequalities.

**Lemma B.1.** If $\|x - y\| \le \tau_M$ then

$$ \|x - y\| \ge D_M(x, y) - \frac{D_M(x, y)^3}{24\tau_M^2}, \qquad (28) $$

$$ D_M(x, y) \le \|x - y\| + \left(\frac{\pi}{3} - 1\right) \frac{\|x - y\|^3}{\tau_M^2} \le \frac{\pi}{3} \|x - y\|, \qquad (29) $$

$$ 1 - \frac{\|x - y\|}{D_M(x, y)} \le \left(1 - \frac{3}{\pi}\right) \frac{\|x - y\|^2}{\tau_M^2}, \qquad (30) $$

$$ D_M(x, y) - \|x - y\| \le \frac{1}{4} \left( \tau_M \arcsin \left( \frac{\|x - y\|}{\tau_M} \right) - \|x - y\| \right). \qquad (31) $$
<figure><img src="image_4.png" /><figcaption>Figure 3 Comparison between the path and the straight line.</figcaption></figure>

Note that in Theorem B.1 the set $M$ may be the whole domain as well as any given curve $\gamma$ between endpoints $x$ and $y$ and with positive reach, in which case $D_{\gamma}(x, y) = |\gamma|$.

The following results show that a path with length close to the Euclidean distance between its endpoints must remain close to the straight line at all time. Since $f$ is Lipschitz, it follows that two paths with same endpoints and length close to the Euclidean distance between the endpoints also have similar conformal lengths.

**Lemma B.2.** Let $x, y \in \mathbb{R}^N$ and $\gamma \in \Gamma(x, y)$ be a path parameterized over $[0, 1]$ with constant velocity. Denote $\bar{\gamma} : t \mapsto (1-t)x + ty$ the straight path from $x$ to $y$. Then

$$ \|\gamma - \bar{\gamma}\|_1 \le \frac{1}{\sqrt{6}} \sqrt{|\gamma|^2 - |\bar{\gamma}|^2}. \qquad (32) $$

**Proof.** Fix $t \in [0, 1]$. Denote $a \le |\gamma|t$ and $b \le |\gamma|(1-t)$ the respective distances from $\gamma(t)$ to $x$ and $y$. Denote $\tau \in \mathbb{R}$ such that $\bar{\gamma}(\tau)$ is the orthogonal projection of $\gamma(t)$ onto the line passing through $x$ and $y$. The fact that $\tau$ may not belong to $[0, 1]$ does not influence the following. Finally denote $h = \|\gamma(t) - \bar{\gamma}(\tau)\|$. See Figure 3 for an illustration of the above. By Pythagoras theorem, it holds that

$$ h^2 = a^2 - |\bar{\gamma}|^2 \tau^2 = b^2 - |\bar{\gamma}|^2 (1 - \tau)^2 = \|\gamma(t) - \bar{\gamma}(t)\|^2 - |\bar{\gamma}|^2 (t - \tau)^2. $$

In particular,

$$ \begin{aligned} \|\gamma(t) - \bar{\gamma}(t)\|^2 &= (1-t)(a^2 - |\bar{\gamma}|^2 \tau^2) + t(b^2 - |\bar{\gamma}|^2 (1-\tau)^2) + |\bar{\gamma}|^2 (t-\tau)^2 \\ &= (1-t)a^2 + tb^2 + |\bar{\gamma}|^2 ((t-1)\tau^2 - t + 2t\tau - t\tau^2 + t^2 - 2t\tau + \tau^2) \\ &= (1-t)a^2 + tb^2 - t(1-t)|\bar{\gamma}|^2 \\ &\le (1-t)t^2|\gamma|^2 + t(1-t)^2|\gamma|^2 - t(1-t)|\bar{\gamma}|^2 \\ &= t(1-t)(|\gamma|^2 - |\bar{\gamma}|^2). \end{aligned} $$

Integrating the above then yields

$$ \|\gamma - \bar{\gamma}\|_1 \le \|\gamma - \bar{\gamma}\|_2 \le \sqrt{\int_0^1 t(1-t)(|\gamma|^2 - |\bar{\gamma}|^2)dt} = \frac{1}{\sqrt{6}} \sqrt{|\gamma|^2 - |\bar{\gamma}|^2} $$

which concludes the proof.

**Corollary B.3.** Let $x, y \in \mathbb{R}^N$ and $\gamma, \omega \in \Gamma_M(x, y)$. Then

$$ \left| \frac{|\gamma|f}{|\gamma|} - \frac{|\omega|f}{|\omega|} \right| \le \frac{\kappa}{\sqrt{6}} \left( \sqrt{|\gamma|^2 - \|x-y\|^2} + \sqrt{|\omega|^2 - \|x-y\|^2} \right). $$
**Proof.** Consider parameterizations of $\gamma$ and $\omega$ over $[0, 1]$ with constant velocity. Using in order the $\kappa$-Lipschitz property of $f$, the triangular inequality of $\|\cdot\|_1$ and Theorem B.2 yields

$$ \begin{aligned} \left| \frac{|\gamma|_f}{|\gamma|} - \frac{|\omega|_f}{|\omega|} \right| & \le \int_0^1 \left| f(\gamma(t)) - f(\omega(t)) \right| dt \\ & \le \kappa \|\gamma - \omega\|_1 \\ & \le \frac{\kappa}{\sqrt{6}} \left( \sqrt{|\gamma|^2 - \|x-y\|^2} + \sqrt{|\omega|^2 - \|x-y\|^2} \right) \end{aligned} $$

which concludes the proof.

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

## B.2 Regularity of Geodesics

In this section we prove Theorem 2.4 using the results proven in Section B.1. Assume by contradiction that $\tau_{M,f} < \mathcal{T}_{M,f}$. Then according to Theorem 2.3 there exists $0 < r < \mathcal{T}_{M,f} = \frac{\tau_M}{2} \wedge \frac{f_{\min}}{8\kappa}$ and $x, y \in M$ such that, letting $\gamma \in \Gamma_{M,f}^*(x, y)$ be a geodesic and $\bar{\gamma} = t \mapsto (1-t)x + ty$ be the straight path from $x$ to $y$, one has $|\bar{\gamma}| = \|x - y\| < 2r$ and

$$ |\gamma| \ge 2r \arcsin \left( \frac{|\bar{\gamma}|}{2r} \right). \qquad (33) $$

Let $\omega \in \Gamma_M^*(x, y)$ be a geodesic w.r.t. the induced metric and let us show that $|\omega|_f < |\gamma|_f$, which contradicts the geodesic nature of $\gamma$. First, rewrite

$$ |\omega|_f - |\gamma|_f = \left( \frac{|\omega|}{|\gamma|} - 1 \right) |\gamma|_f + |\omega| \left( \frac{|\omega|_f}{|\omega|} - \frac{|\gamma|_f}{|\gamma|} \right). \qquad (34) $$

The first term in the right-hand side of Equation (34) is negative as $|\omega| = D_M(x, y) \le |\gamma|$ hence can be upper bounded by noticing that $|\gamma|_f \ge |\gamma|f_{\min}$. As for the second term, it can be upper bounded according to Theorem B.3. Moreover, recall that $|\bar{\gamma}| < 2r < \tau_M$, hence Equation (29) may be rewritten as

$$ |\omega| \le |\bar{\gamma}| + \left(\frac{\pi}{3} - 1\right) \frac{|\bar{\gamma}|^3}{\tau_M^2} \le \frac{\pi}{3} |\bar{\gamma}|. \qquad (35) $$

Combining these three inequalities yields

$$ |\omega|_f - |\gamma|_f \le (|\omega| - |\gamma|)f_{\min} + \frac{\pi\kappa}{3\sqrt{6}}|\bar{\gamma}| \left( \sqrt{|\omega|^2 - |\bar{\gamma}|^2} + \sqrt{|\gamma|^2 - |\bar{\gamma}|^2} \right). \qquad (36) $$

In the following, both terms are upper bounded in a way that factors out $|\gamma| - |\bar{\gamma}|$. Using in order Equation (31), the fact that $2r \le \tau_M$ and $t \mapsto t \arcsin(|\bar{\gamma}|/t)$ is non-increasing, and the initial assumption given by Equation (33), it holds that

$$ |\omega| - |\bar{\gamma}| \le \frac{1}{4} \left( \tau_M \arcsin \left( \frac{|\bar{\gamma}|}{\tau_M} \right) - |\bar{\gamma}| \right) \le \frac{1}{4} \left( 2r \arcsin \left( \frac{|\bar{\gamma}|}{2r} \right) - |\bar{\gamma}| \right) \le \frac{1}{4} (|\gamma| - |\bar{\gamma}|) $$

and

$$ |\omega| - |\gamma| = |\omega| - |\bar{\gamma}| + |\bar{\gamma}| - |\gamma| \le -\frac{3}{4}(|\gamma| - |\bar{\gamma}|). \qquad (37) $$

On the other hand, applying Equation (27) to $t = |\bar{\gamma}|/2r$, then Equation (33),

$$ |\bar{\gamma}|^3 \le 6(2r)^3 \left( \arcsin\left(\frac{|\bar{\gamma}|}{2r}\right) - \frac{|\bar{\gamma}|}{2r} \right) \le 24r^2 (|\gamma| - |\bar{\gamma}|). \qquad (38) $$
Then, using Equation (35) again, then Equation (38),

$$
\begin{align*}
|\bar{\gamma}|\sqrt{|\omega|^2 - |\bar{\gamma}|^2} &= |\bar{\gamma}|\sqrt{|\omega| + |\bar{\gamma}|}\sqrt{|\omega| - |\bar{\gamma}|} \\
&\le |\bar{\gamma}|\sqrt{\left(\frac{\pi}{3} + 1\right)|\bar{\gamma}|}\sqrt{\left(\frac{\pi}{3} - 1\right)\frac{|\bar{\gamma}|^3}{\tau_M^2}} \\
&= \sqrt{\frac{\pi^2}{9} - 1}\frac{|\bar{\gamma}|^3}{\tau_M} \\
&\le \sqrt{\frac{\pi^2}{9} - 1}\frac{24r^2}{\tau_M}(|\gamma| - |\bar{\gamma}|).
\end{align*}
$$

Hence, since $2r \le \tau_M$,

$$
|\bar{\gamma}|\sqrt{|\omega|^2 - |\bar{\gamma}|^2} \le 12\sqrt{\frac{\pi^2}{9} - 1} r(|\gamma| - |\bar{\gamma}|). \quad (39)
$$

Likewise, Equation (38) and $|\bar{\gamma}| \le 2r$ imply that

$$
|\bar{\gamma}|\sqrt{|\gamma|^2 - |\bar{\gamma}|^2} = \sqrt{2|\bar{\gamma}|^3 + |\bar{\gamma}|^2(|\gamma| - |\bar{\gamma}|)} \sqrt{|\gamma| - |\bar{\gamma}|} \le \sqrt{48r^2 + (2r)^2}(|\gamma| - |\bar{\gamma}|) . \quad (40)
$$

Finally, combining Equations (36), (37), (39), and (40) yields

$$
|\omega|_f - |\gamma|_f \le \left( -\frac{3}{4} f_{\min} + \frac{\pi}{3\sqrt{6}} \left( 12\sqrt{\frac{\pi^2}{9} - 1} + 2\sqrt{13} \right) \kappa r \right) (|\gamma| - |\bar{\gamma}|) .
$$

By assumption,

$$
r < \frac{f_{\min}}{8\kappa} \le \left( 12\sqrt{\frac{\pi^2}{9} - 1} + 2\sqrt{13} \right)^{-1} \frac{9\sqrt{6} f_{\min}}{4\pi \kappa},
$$

which concludes that $|\omega|_f - |\gamma|_f$ is negative, hence the contradiction and Theorem 2.4 is proven. The choice of the constant $\frac{1}{8}$ instead of the one appearing in the right-hand side of the last inequality is purely for cosmetic reasons.

B.3 Weight Function

In this section we state the Lipschitz property of the weight function defined in Theorem 3.2 w.r.t. the function $f$ and the endpoints $(x, y)$. The latter is inherited from the Lipschitz nature of $f$. We also quantify the convergence of $w_{f,q}$ to $w_{f,\infty}$ as $q \to \infty$ and then prove Theorem 3.3. The following three lemmas are obtained through elementary computations that are not detailed here. Recall that

$$
w_{f,q}(x,y) = \frac{\|x-y\|}{2(q-1)} \left( f(x) + 2 \sum_{k=2}^{q-1} f \left( \frac{q-k}{q-1}x + \frac{k-1}{q-1}y \right) + f(y) \right)
$$

and

$$
w_{f,\infty}(x, y) = \|x - y\| \int_{0}^{1} f((1 - t)x + ty)dt .
$$

► Lemma B.4. Let $f: \mathbb{R}^N \rightarrow \mathbb{R}_+^*$ be a $\kappa$-Lipschitz function and $q \in \{2, \dots, \infty\}$. Then the weight function $w_{f,q}$ satisfies for all $x, y, x', y' \in M$

$$
\left| \frac{w_{f,q}(x, y)}{\|x - y\|} - \frac{w_{f,q}(x', y')}{\|x' - y'\|} \right| \le \kappa \frac{\|x - x'\| + \|y - y'\|}{2} .
$$
**Lemma B.5.** Let $f,g: \mathbb{R}^N \to \mathbb{R}_+^*$ be two functions and $q \in \{2, \dots, \infty\}$. Then for all $x,y \in M$

$$|w_{f,q}(x,y) - w_{g,q}(x,y)| \le \|x - x\| \|f - g\|_{\infty}.$$

**Lemma B.6.** Let $f: \mathbb{R}^N \to \mathbb{R}_+^*$ be a $\kappa$-Lipschitz function and $q \ge 2$ an integer. Then for all $x,y \in M$

$$|w_{f,q}(x,y) - w_{f,\infty}(x,y)| \le \frac{\kappa \|x-y\|^2}{4(q-1)}.$$

Theorem B.7 below states the upper bound on the distortion of the weight function when $q = \infty$. The case of finite $q$ is then deduced from Theorem B.6. Indeed, according to Theorems B.6 and B.7, for all $\|x - y\| \le \tau_{M,f}$ one has

$$\begin{aligned} \left| 1 - \frac{w_{f,q}(x,y)}{D_{M,f}(x,y)} \right| & \le \left| \frac{w_{f,\infty}(x,y) - w_{f,q}(x,y)}{D_{M,f}(x,y)} \right| + \left| 1 - \frac{w_{f,\infty}(x,y)}{D_{M,f}(x,y)} \right| \\ & \le \frac{\kappa \|x-y\|^2}{4(q-1)D_{M,f}(x,y)} + \frac{\|x-y\|^2}{16T_{M,f}^2} \\ & \le \frac{\kappa \|x-y\|}{4f_{\min}(q-1)} + \frac{\|x-y\|^2}{16T_{M,f}^2} \end{aligned}$$

since $D_{M,f}(x,y) \ge f_{\min}\|x - y\|$. This concludes Theorem 3.3.

**Lemma B.7.** Let $x,y \in M$ such that $\|x - y\| \le \tau_{M,f}$. Then

$$\left| 1 - \frac{w_{f,\infty}(x,y)}{D_{M,f}(x,y)} \right| \le \frac{\|x-y\|^2}{16 T_{M,f}^2}. \qquad (41)$$

**Proof.** Let $\gamma \in \Gamma_{M,f}^*(x,y)$ be a geodesic and $\bar{\gamma}$ be the straight path from $x$ to $y$. By definition $D_{M,f}(x,y) = |\gamma|_f$, $w_{f,\infty}(x,y) = |\bar{\gamma}|_f$ and $|\bar{\gamma}| = \|x - y\|$. First rewrite

$$D_{M,f}(x,y) - w_{f,\infty}(x,y) = \left(1 - \frac{|\bar{\gamma}|}{|\gamma|}\right) |\gamma|_f + |\bar{\gamma}| \left(\frac{|\gamma|_f}{|\gamma|} - \frac{|\bar{\gamma}|_f}{|\bar{\gamma}|}\right). \qquad (42)$$

Regarding the first term, as $\|x - y\| \le \tau_{M,f} \le \tau_{\gamma}$, applying Equation (30) to the induced metric $D_{\gamma}$ yields

$$0 \le 1 - \frac{|\bar{\gamma}|}{|\gamma|} = 1 - \frac{\|x - y\|}{D_{\gamma}(x, y)} \le \left(1 - \frac{3}{\pi}\right) \frac{\|x - y\|^2}{\tau_{\gamma}^2}. \qquad (43)$$

As for the second term, applying Theorem B.3 yields

$$\left| \frac{|\gamma|_f}{|\gamma|} - \frac{|\bar{\gamma}|_f}{|\bar{\gamma}|} \right| \le \frac{\kappa}{\sqrt{6}} \sqrt{|\gamma|^2 - |\bar{\gamma}|^2} = \frac{\kappa}{\sqrt{6}} |\gamma| \sqrt{1 + \frac{|\bar{\gamma}|}{|\gamma|}} \sqrt{1 - \frac{|\bar{\gamma}|}{|\gamma|}}$$

and using the fact that $|\gamma|_f \ge |\gamma|f_{\min}$ and $|\bar{\gamma}| \le |\gamma|$ along with Equation (43) further implies that

$$\left| \frac{|\gamma|_f}{|\gamma|} - \frac{|\bar{\gamma}|_f}{|\bar{\gamma}|} \right| \le \frac{\kappa}{\sqrt{6}} \frac{|\gamma|_f}{f_{\min}} \sqrt{2\left(1 - \frac{3}{\pi}\right) \frac{\|x - y\|^2}{\tau_{\gamma}^2}}. \qquad (44)$$
Finally, combining Equations (42)–(44) together with the fact that $\tau_\gamma \ge \mathcal{T}_{M,f}$ and $\frac{f_{\min}}{8\kappa} \ge \mathcal{T}_{M,f}$ yields

$$ \begin{aligned} \left|1 - \frac{w_{f,\infty}(x, y)}{D_{M,f}(x, y)}\right| & \le \left(\left(1 - \frac{3}{\pi}\right) \frac{1}{\tau_\gamma^2} + \sqrt{\frac{1}{3} - \frac{1}{\pi}} \frac{\kappa}{f_{\min}\tau_\gamma}\right) \|x - y\|^2 \\ & \le \left(1 - \frac{3}{\pi} + \frac{1}{8}\sqrt{\frac{1}{3} - \frac{1}{\pi}}\right) \frac{\|x - y\|^2}{\mathcal{T}_{M,f}^2} \\ & \le \frac{\|x - y\|^2}{16\mathcal{T}_{M,f}^2} \end{aligned} $$

where the last inequality is purely cosmetic and concludes the proof.

## B.4 Discrete Approximation of the Conformal Metric

In this section we prove Theorem 3.5. Let $X \subset M$ be a point cloud and denote $\rho = d_H(M, X)$. Assume that $4\rho \le r \le \mathcal{T}_{M,f}$ and let $x, y \in M$.

**Lower bound** Let $(x_0, \dots, x_K)$ be a polygonal path in $G_r(X \cup \{x, y\})$ from $x = x_0$ to $y = x_K$ achieving the infimum in Theorem 3.4. According to Theorem 3.3,

$$ \hat{D}_{X,f}(x, y) = \sum_{k=1}^{K-1} w_{f,q}(x_k, x_{k+1}) \ge \sum_{k=1}^{K-1} (1 - \delta_q(\|x_k - x_{k+1}\|)) D_{M,f}(x_k, x_{k+1}). $$

Using the fact that $\delta_q$ is non-decreasing and that $\|x_k - x_{k+1}\| \le r$ for all $k$, along with the triangular inequality of $D_{M,f}$, it follows that

$$ \hat{D}_{X,f}(x, y) \ge (1 - \delta_q(r)) D_{M,f}(x, y). \quad (45) $$

**Local upper bound** If $\|x - y\| \le r$, the edge $(x, y)$ belongs to $G_r(X \cup \{x, y\})$, hence according to Theorem 3.3,

$$ \hat{D}_{X,f}(x, y) \le w_{f,q}(x, y) \le (1 + \delta_q(r)) D_{M,f}(x, y). \quad (46) $$

**Global upper bound** Assume that $\|x - y\| \ge r$. Let $\gamma \in \Gamma_{M,f}^*(x, y)$ be a geodesic and decompose it into $K = \lceil |\gamma|/(r - 2\rho) \rceil$ sections of equal arc-length $l = |\gamma|/K$. Denote $(x = x_0, x_1, \dots, x_K = y)$ the intermediate points resulting from this decomposition and $(x = x'_0, x'_1, \dots, x'_K = y)$ their respective nearest neighbors in the point cloud $X \cup \{x, y\}$. Then

$$ 1 \le \frac{|\gamma|}{r - 2\rho} \le K \le \frac{2|\gamma|}{r - 2\rho} \quad \text{and} \quad \frac{r}{4} \le \frac{r}{2} - \rho \le l \le r - 2\rho. $$

In particular, $\|x'_k - x'_{k+1}\| \le \|x'_k - x_k\| + \|x_k - x_{k+1}\| + \|x_{k+1} - x'_{k+1}\| \le \rho + l + \rho \le r$ so that $(x'_0, \dots, x'_K)$ is indeed a path in $G_r(X \cup \{x, y\})$. Denote for short

$$ \varepsilon_k = x'_k - x_k, $$

$$ w_k = w_{f,q}(x_k, x_{k+1}), $$

$$ w'_k = w_{f,q}(x'_k, x'_{k+1}), $$

$$ u_k = \frac{x_k - x_{k+1}}{\|x_k - x_{k+1}\|}, $$

$$ \bar{w}_k = \frac{w_{f,q}(x_k, x_{k+1})}{\|x_k - x_{k+1}\|}, $$

$$ \bar{w}'_k = \frac{w_{f,q}(x'_k, x'_{k+1})}{\|x'_k - x'_{k+1}\|}. $$
Let us show that the weight $\sum_k w'_k$ of the polygonal path is not much greater than the conformal distance $D_{M,f}(x, y)$. First, rewrite

$$w'_{k} = w_{k} + \|x'_{k} - x'_{k+1}\| (\overline{w}'_{k} - \overline{w}_{k}) + (\|x'_{k} - x'_{k+1}\| - \|x_{k} - x_{k+1}\|) \overline{w}_{k}. \quad (47)$$

In order to upper bound the last term in Equation (47), we use the following inequality from the proof of Theorem 2.1 in [2]:

$$\|x'_{k} - x'_{k+1}\| \le \|x_{k} - x_{k+1}\| + \langle u_{k}, \varepsilon_{k} - \varepsilon_{k+1} \rangle + \frac{1}{2} \frac{\|\varepsilon_{k} - \varepsilon_{k+1}\|^{2}}{\|x_{k} - x_{k+1}\|},$$

which implies that

$$(\|x'_{k} - x'_{k+1}\| - \|x_{k} - x_{k+1}\|) \overline{w}_{k} \le \langle \overline{w}_{k} u_{k}, \varepsilon_{k} - \varepsilon_{k+1} \rangle + \frac{w_{k}}{2} \frac{\|\varepsilon_{k} - \varepsilon_{k+1}\|^{2}}{\|x_{k} - x_{k+1}\|}$$

and from Equation (47) it follows that

$$w'_{k} \le \underbrace{w_{k}}_{(i)} + \underbrace{\|x'_{k} - x'_{k+1}\| (\overline{w}'_{k} - \overline{w}_{k})}_{(ii)} + \underbrace{\langle \overline{w}_{k} u_{k}, \varepsilon_{k} - \varepsilon_{k+1} \rangle}_{(iii)} + \underbrace{\frac{w_{k}}{2} \frac{\|\varepsilon_{k} - \varepsilon_{k+1}\|^{2}}{\|x_{k} - x_{k+1}\|}}_{(iv)}. \quad (48)$$

Let us now upper bound all four terms in this upper bound.

(i) Theorem 3.3 ensures that

$$w_k \le (1 + \delta_q(\|x_k - x_{k+1}\|)) D_{M,f}(x_k, x_{k+1}) \le (1 + \delta_q(r)) D_{M,f}(x_k, x_{k+1}). \quad (49)$$

(ii) Theorem B.4 ensures that

$$\|x'_{k} - x'_{k+1}\| (\overline{w}'_{k} - \overline{w}_{k}) \le \|x'_{k} - x'_{k+1}\| \frac{\kappa}{2} (\|x'_{k} - x_{k}\| + \|x'_{k+1} - x_{k+1}\|) \\ \le (l + 2\rho)\kappa\rho,$$

which implies since $\rho \le \frac{r}{4} \le l$ and $D_{M,f}(x_k, x_{k+1}) \ge l f_{\min}$ that

$$\|x'_{k} - x'_{k+1}\| (\overline{w}'_{k} - \overline{w}_{k}) \le 3 \frac{\kappa}{f_{\min}} \rho D_{M,f}(x_k, x_{k+1}). \quad (50)$$

(iii) Recall that $\varepsilon_0 = \varepsilon_K = 0$. Then when summing over $k$, the terms can be rearranged so that

$$\sum_{k=0}^{K-1} \langle \overline{w}_k u_k, \varepsilon_k - \varepsilon_{k+1} \rangle = \sum_{k=1}^{K-1} \langle \overline{w}_k u_k - \overline{w}_{k-1} u_{k-1}, \varepsilon_k \rangle \\ = \sum_{k=1}^{K-1} (\overline{w}_k \langle u_k - u_{k-1}, \varepsilon_k \rangle + (\overline{w}_k - \overline{w}_{k-1}) \langle u_{k-1}, \varepsilon_k \rangle).$$

According to Theorem 2.5, $\|u_k - u_{k+1}\| \le \frac{1}{\tau_\gamma} \|x_k - x_{k+1}\|$ since $r - 2\rho \le T_{M,f} \le \tau_\gamma$.

According to Theorem B.4, $\overline{w}_k - \overline{w}_{k-1} \le \frac{\kappa}{2} (\|x_k - x_{k+1}\| + \|x_{k+1} - x_{k+2}\|) \le \kappa l$. Then, using Cauchy-Schwartz inequality and $D_{M,f}(x_k, x_{k+1}) \ge l f_{\min}$,

$$\overline{w}_k \langle u_k - u_{k-1}, \varepsilon_k \rangle + (\overline{w}_k - \overline{w}_{k-1}) \langle u_{k-1}, \varepsilon_k \rangle \le \frac{\overline{w}_k}{\tau_\gamma} \|x_k - x_{k+1}\| \rho + \kappa l \rho \\ \le \frac{w_k}{\tau_\gamma} \rho + \frac{\kappa}{f_{\min}} D_{M,f}(x_k, x_{k+1}) \rho .$$

Adding the analogous term corresponding to $k = 0$,

$$\sum_{k=0}^{K-1} \langle \overline{w}_k u_k, \varepsilon_k - \varepsilon_{k+1} \rangle \le \sum_{k=0}^{K-1} \left( \frac{w_k}{\tau_\gamma} + \frac{\kappa}{f_{\min}} D_{M,f}(x_k, x_{k+1}) \right) \rho . \quad (51)$$
(iv) Since $\|x_k - x_{k+1}\| \le D_\gamma(x_k, x_{k+1}) = l \le \tau_\gamma$ and $r \le 4l$, applying Equation (28) to the metric $D_\gamma$ yields

$$ \|x_k - x_{k+1}\| \ge l - \frac{l^3}{24\tau_\gamma^2} \ge \frac{23}{24}l \ge \frac{23}{96}r, $$

hence

$$ \frac{w_k}{2} \frac{\|\varepsilon_k - \varepsilon_{k+1}\|^2}{\|x_k - x_{k+1}\|^2} \le \frac{w_k}{2} \left(\frac{96}{23}\right)^2 \frac{4\rho^2}{r^2}. \qquad (52) $$

Finally, since $(x_0, \dots, x_K)$ are intermediate points on the geodesic $\gamma$ from $x$ to $y$, $D_{M,f}(x, y) = \sum_{k=0}^{K-1} D_{M,f}(x_k, x_{k+1})$. Together with Equations (48)–(52), this yields

$$ \sum_{k=0}^{K-1} w'_{k} \le \left(1 + \delta_{q}(r) + 4 \frac{\kappa}{f_{\min}} \rho\right) D_{M,f}(x, y) + \left(\frac{\rho}{\tau_{\gamma}} + 2 \left(\frac{96}{23}\right)^2 \frac{\rho^2}{r^2}\right) \sum_{k=0}^{K-1} w_k $$

In particular, recall that $\frac{\kappa}{f_{\min}} \le \frac{1}{8T_{M,f}}$ and $r \le T_{M,f}$, hence $\delta_q(r) \le \frac{9}{64}$ and Equation (49) further implies that $w_k \le \frac{73}{64}D_{M,f}(x_k, x_{k+1})$, so that

$$ \hat{D}_{X,f}(x, y) \le \sum_{k=0}^{K-1} w'_{k} \le \left(1 + \delta_q(r) + \frac{105}{64} \frac{\rho}{T_{M,f}} + \frac{73}{32} \left(\frac{96}{23}\right)^2 \frac{\rho^2}{r^2}\right) D_{M,f}(x, y). $$

Upper bounding $\frac{105}{64} \le 2$ and $\frac{73}{32} \left(\frac{96}{23}\right)^2 \le 40$ to get cleaner constants, it finally holds that

$$ \hat{D}_{X,f}(x, y) \le \left(1 + \delta_q(r) + 2 \frac{\rho}{T_{M,f}} + 40 \frac{\rho^2}{r^2}\right) D_{M,f}(x, y). \qquad (53) $$

**Conclusion** According to the lower bound Equation (45) and to the upper bounds Equations (46) and (53) depending on the case, the distortion between the polygonal metric and the original metric is upper bounded as

$$ \begin{aligned} l_{\infty,M}(\hat{D}_{X,f}|D_{M,f}) &\le \delta_q(r) + 2 \frac{\rho}{T_{M,f}} + 40 \frac{\rho^2}{r^2} \\ &= \frac{\kappa}{4f_{\min}} \frac{r}{q-1} + \frac{r^2}{16T_{M,f}^2} + 2 \cdot \frac{r}{4T_{M,f}} \cdot \frac{4\rho}{r} + 40 \frac{\rho^2}{r^2} \\ &\le \frac{1}{32T_{M,f}} \frac{r}{q-1} + \frac{r^2}{8T_{M,f}^2} + 56 \frac{\rho^2}{r^2} \end{aligned} $$

where we used the inequality $2ab \le a^2 + b^2$. This concludes the proof of Theorem 3.5.

## B.5 Approximation of the Conformal Factor

In this section we prove Theorem 3.6. Fix $x, y \in M$ and denote $\hat{D}_g = \hat{D}_{X,g}(x, y)$, $\hat{D}_f = \hat{D}_{X,f}(x, y)$ and $D = D_{M,f}(x, y)$ for short. Denote $G$ the graph considered for the paths in both $\hat{D}_g$ and $\hat{D}_f$ and $q$ the resolution. First, notice that the assumption that $\|g - f\|_{\infty} \le \frac{1}{2}f_{\min}$ implies the lower bound $g_{\min} = \frac{1}{2}f_{\min}$ on $g$. For any edge $(u, v)$ in $G$, Theorem B.5 yields

$$ |w_{g,q}(u, v) - w_{f,q}(u, v)| \le \|u - v\| \|g - f\|_{\infty}. \qquad (54) $$
Then, since $w_{g,q}(u, v) \ge \|u - v\|g_{\min}$, summing Equation (54) over a path that realizes $\hat{D}_g$ yields

$$ \hat{D}_f \le \left( 1 + \frac{\|g - f\|_{\infty}}{g_{\min}} \right) \hat{D}_g \le 2\hat{D}_g. \qquad (55) $$

On the other hand, since $w_{f,q}(u, v) \ge \|u - v\|f_{\min}$, summing Equation (54) over a path that realizes $\hat{D}_f$ yields

$$ \hat{D}_g \le \left( 1 + \frac{\|g - f\|_{\infty}}{f_{\min}} \right) \hat{D}_f, $$

and it follows that

$$ \left| \hat{D}_g - \hat{D}_f \right| \le \max \left( \frac{\|g - f\|_{\infty}}{g_{\min}} \hat{D}_g, \frac{\|g - f\|_{\infty}}{f_{\min}} \hat{D}_f \right) = 2 \frac{\|g - f\|_{\infty}}{f_{\min}} \hat{D}_g. \qquad (56) $$

Then, Equations (55) and (56) imply that

$$ \begin{aligned} |\hat{D}_g - D| & \le |\hat{D}_g - \hat{D}_f| + |\hat{D}_f - D| \\ & \le 2 \frac{\|g - f\|_{\infty}}{f_{\min}} \hat{D}_g + \ell_{\infty,M}(\hat{D}_{X,f}, D_{M,f}) (\hat{D}_f \vee D) \\ & \le 2 \frac{\|g - f\|_{\infty}}{f_{\min}} \hat{D}_g + 2\ell_{\infty,M}(\hat{D}_{X,f}, D_{M,f}) (\hat{D}_g \vee D). \end{aligned} $$

Taking the supremum over $x$ and $y$ finally yields

$$ \ell_{\infty,M}(\hat{D}_{X,g}, D_{M,f}) \le 2 \left( \frac{\|g - f\|_{\infty}}{f_{\min}} + \ell_{\infty,M}(\hat{D}_{X,f}, D_{M,f}) \right) $$

which concludes the proof of Theorem 3.6.

# C Probabilistic Technical Proofs

## C.1 Convergence on the Ball Graph

In this section we prove Theorem 4.2. In the following we say that something is true for $n$ large enough when it is true for all $n$ larger than some constant depending on $L_\mu$, $T_{M,f}$ and $d$. Assume that $0 < r \le T_{M,f}$ and $q \in \{2, \dots, \infty\}$. Then

$$ \mathbb{E} \left[ \ell_{\infty,M} (\hat{D}_{X_n,f}, D_{M,f}) \right] \le \mathbb{P} (4d_H(M, X_n) > r) + \mathbb{E} \left[ \mathbb{1}_{(4d_H(M, X_n) \le r)} \ell_{\infty,M} (\hat{D}_{X_n,f} | D_{M,f}) \right] $$

since $\ell_{\infty,M}$ is upper bounded both by 1 and by $\ell_{\infty,M}$ according to Equation (9). According to Theorem A.1,

$$ \mathbb{P}(4d_H(M, X_n) > r) \le \frac{16^d}{c_\mu r^d} e^{-nc_\mu} \left(\frac{r}{8}\right)^d = \left(\frac{16L_\mu}{r}\right)^d e^{-n\left(\frac{r}{8L_\mu}\right)^d}. \qquad (57) $$

On the other hand, assuming that $n \ge 8$, Theorems A.2 and 3.5 yield

$$ \mathbb{E} \left[ \mathbb{1}_{(4d_H(M, X_n) \le r)} \ell_{\infty,M} (\hat{D}_{X_n,f}, D_{M,f}) \right] \le \frac{r}{32(q-1)T_{M,f}} + \frac{r^2}{8T_{M,f}^2} + 448 \frac{L_\mu^2}{r^2} \left( \frac{\log(n)}{n} \right)^{\frac{2}{d}} \qquad (58) $$
so that

$$ \mathbb{E}[\ell_{\infty,M}(\hat{D}_{X_n,f}, D_{M,f})] \le A_n(r) + B_n(r,q) \quad (59) $$

where $A_n(r)$ and $B_n(r, q)$ respectively denote the right-hand sides in Equation (57) and in Equation (58). We now consider the two cases for the choice of the parameters $r$ and $q$ specified in Theorem 4.2.

**Large resolution** Let $r = 8\sqrt{L_\mu T_{M,f}}(\log(n)/n)^{1/2d}$, which is indeed smaller than $T_{M,f}$ for $n$ large enough. Let $q \ge 1 + 4\frac{T_{M,f}}{r}$. Then

$$ A_n(r) = 2^d \left( \frac{L_\mu}{T_{M,f}} \right)^{\frac{d}{2}} \sqrt{\frac{n}{\log(n)}} \exp \left( - \left( \frac{T_{M,f}}{L_\mu} \right)^{\frac{d}{2}} \sqrt{n \log(n)} \right) \le \frac{1}{2} \frac{L_\mu}{T_{M,f}} \left( \frac{\log(n)}{n} \right)^{\frac{1}{d}} $$

for $n$ large enough and

$$ B_n(r, q) \le B_n \left( 1 + 4 \frac{T_{M,f}}{r}, r \right) = \left( \frac{1}{2} + 8 + 7 \right) \frac{L_\mu}{T_{M,f}} \left( \frac{\log(n)}{n} \right)^{\frac{1}{d}}, $$

so that according to Equation (59),

$$ \mathbb{E}[\ell_{\infty,M}(\hat{D}_{X_n,f}, D_{M,f})] \le 16 \frac{L_\mu}{T_{M,f}} \left(\frac{\log(n)}{n}\right)^{\frac{1}{d}} $$

which concludes the proof of Equation (15).

**Small resolution** Let $r = 8L_\mu^{2/3}T_{M,f}^{1/3}(\log(n)/n)^{2/3d}$, which is indeed smaller than $T_{M,f}$ for $n$ large enough. Let $q = 2$. Then

$$ A_n(r) = 2^d \left( \frac{L_\mu}{T_{M,f}} \right)^{\frac{d}{3}} \left( \frac{n}{\log(n)} \right)^{\frac{2}{3}} \exp \left( - \left( \frac{T_{M,f}}{L_\mu} \right)^{\frac{d}{3}} n^{\frac{1}{3}} \log(n)^{\frac{2}{3}} \right) \\ \le \frac{1}{2} \left( \frac{L_\mu}{T_{M,f}} \right)^{\frac{2}{3}} \left( \frac{\log(n)}{n} \right)^{\frac{2}{3d}} $$

for $n$ large enough and

$$ B_n(q,r) = \left(\frac{1}{4} + 7\right) \left(\frac{L_\mu}{T_{M,f}}\right)^{\frac{2}{3}} \left(\frac{\log(n)}{n}\right)^{\frac{2}{3d}} + 8 \left(\frac{L_\mu}{T_{M,f}}\right)^{\frac{4}{3}} \left(\frac{\log(n)}{n}\right)^{\frac{4}{3d}} \\ \le \frac{15}{2} \left(\frac{L_\mu}{T_{M,f}}\right)^{\frac{2}{3}} \left(\frac{\log(n)}{n}\right)^{\frac{2}{3d}} $$

for $n$ large enough, so that according to Equation (59),

$$ \mathbb{E}[\ell_{\infty,M}(\hat{D}_{X_n,f}, D_{M,f})] \le 8 \left( \frac{L_\mu}{T_{M,f}} \right)^{\frac{2}{3}} \left( \frac{\log(n)}{n} \right)^{\frac{2}{3d}} $$

which concludes the proof of Equation (16).
## C.2 Convergence on the Nearest-Neighbors Graph

In this section we prove Theorem 4.5 using Theorems 4.2 and 4.4. Consider $k = ⌊\sqrt{n \log(n)}⌋$, $q = ⌈n^{1/4}⌋$ and let

$$r_{-} = \left( \frac{k}{2C_{\mu}(n-1)} \right)^{\frac{1}{d}} \quad \text{and} \quad r_{+} = \left( \frac{2k}{c_{\mu}(n-1)} \right)^{\frac{1}{d}},$$

so that according to Theorem 4.4, the event

$$A_1 \stackrel{\text{def}}{=} \{G_{r_{-}}(X_n) \subset \mathcal{G}_k(X_n) \subset G_{r_{+}}(X_n)\}$$

satisfies

$$\mathbb{P}(\overline{A_1}) \le 2n \exp \left( -\frac{1}{8} \sqrt{n \log(n)} \right). \qquad (60)$$

Denote $\hat{D}_{r_{-}}$, $\hat{D}_{r_{+}}$ and $\hat{D}_{k}$ the three different instances of $\hat{D}_{X_n,f}$ defined for the $r_{-}$-ball graph, the $r_{+}$-ball graph and the $k$-NN graph respectively, all with resolution $q$. Also denote $D = D_{M,f}$ for short. Under the event $A_1$, for all $x, y \in X_n$ it holds that

$$\hat{D}_{r_{+}}(x, y) \le \hat{D}_{k}(x, y) \le \hat{D}_{r_{-}}(x, y)$$

as the graphs are equipped with the same weight function $w_{f,q}$ and the infimum over paths increases when fewer paths are allowed due to the graph being smaller. It follows that

$$\begin{aligned} l_{\infty, X_n}(\hat{D}_k|D) &= \sup_{x \neq y \in M} \left| \frac{D(x, y) - \hat{D}_k(x, y)}{D(x, y)} \right| \\ &\le \sup_{x \neq y \in M} \left| \frac{D(x, y) - \hat{D}_{r_{-}}(x, y)}{D(x, y)} \right| \lor \left| \frac{D(x, y) - \hat{D}_{r_{+}}(x, y)}{D(x, y)} \right| \\ &= l_{\infty, X_n}(\hat{D}_{r_{-}}|D) \lor l_{\infty, X_n}(\hat{D}_{r_{+}}|D). \end{aligned}$$

Under the event

$$A_2 \stackrel{\text{def}}{=} \left\{ \ell_{\infty, X}(\hat{D}_{r_{-}}, D) \le \frac{1}{2} \right\} \cap \left\{ \ell_{\infty, X_n}(\hat{D}_{r_{+}}, D) \le \frac{1}{2} \right\},$$

it then holds according to Equation (9) that

$$\begin{aligned} \ell_{\infty, X_n}(\hat{D}_k, D) &\le l_{\infty, X_n}(\hat{D}_k|D) \\ &\le l_{\infty, X_n}(\hat{D}_{r_{-}}|D) \lor l_{\infty, X_n}(\hat{D}_{r_{+}}|D) \\ &\le 2\ell_{\infty, X_n}(\hat{D}_{r_{-}}, D) + 2\ell_{\infty, X_n}(\hat{D}_{r_{+}}, D). \end{aligned}$$

This implies that

$$\mathbb{E}[\mathbb{1}_{A_1 \cap A_2} \ell_{\infty, X_n}(\hat{D}_k, D)] \le 2\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{-}}, D)] + 2\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{+}}, D)]. \qquad (61)$$

The event $A_1$ is already known to have high probability. Regarding $A_2$, Markov inequality yields

$$\mathbb{P}(\overline{A_2}) \le 2\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{-}}, D)] + 2\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{+}}, D)]. \qquad (62)$$
Since $r_{-} \asymp r_{+} \asymp (\log(n)/n)^{1/2d}$ when $n$ is large and $q = \lceil n^{1/4} \rceil \gtrsim 1/r_{+} \ge 1/r_{-}$, there exists according to Theorem 4.2 a constant $c$ depending on $L_{\mu}$ and $T_{M,f}$ such that

$$ \mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{-}}, D)] + \mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{+}}, D)] \le c \left(\frac{\log(n)}{n}\right)^{\frac{1}{d}}. \quad (63) $$

Finally, as $\ell_{\infty, X_n} \le 1$, combining Equations (60)–(63) yields

$$ \begin{aligned} \mathbb{E}[\ell_{\infty, X_n}(\hat{D}_k, D)] &\le \mathbb{E}[\mathbb{1}_{A_1 \cap A_2} \ell_{\infty, X_n}(\hat{D}_k, D)] + \mathbb{P}(\overline{A_2}) + \mathbb{P}(\overline{A_1}) \\ &\le 4\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{-}}, D)] + 4\mathbb{E}[\ell_{\infty, X_n}(\hat{D}_{r_{+}}, D)] + 2ne^{-\frac{1}{8}\sqrt{n \log(n)}} \\ &\le C \left(\frac{\log(n)}{n}\right)^{\frac{1}{d}} \end{aligned} $$

where $C$ is a constant depending on $L_{\mu}$ and $T_{M,f}$. This concludes the proof of Theorem 4.5.

### C.3 Minimax Lower Bound

In this section we prove Theorem 4.6 using Le Cam's method [19]. We first adapt this standard result to our context.

**▶ Lemma C.1.** Let $n \ge 2$ and $\mathcal{M}$ be some set of distributions over $\mathbb{R}^N$ such that there exists two measures $\mu_1, \mu_2 \in \mathcal{M}$ with respective supports $M_1$ and $M_2$ and at total variation distance $d_{TV}(\mu_1, \mu_2) \le \frac{1}{n}$ from each other. Then, for all $x, y \in M_1 \cap M_2$ the minimax risk associated with the estimation of the induced metric may be lower bounded by the distortion between the two metrics $D_{M_1}$ and $D_{M_2}$ at endpoints $x$ and $y$.

$$ \inf_{\hat{D} \in \mathcal{D}_n} \sup_{\mu \in \mathcal{M}} \mathbb{E}_{X \sim \mu^{\otimes n}} [\ell_{\infty, M_\mu}(\hat{D}_X, D_{M_\mu})] \ge \frac{1}{8} \left| \frac{D_{M_1}(x, y) - D_{M_2}(x, y)}{D_{M_1}(x, y) \vee D_{M_2}(x, y)} \right| \quad (64) $$

where we recall $\mathcal{D}_n$ is the set of possible estimators defined in Theorem 4.6 and $M_\mu$ denotes the support of $\mu$.

**Proof.** Denote $\mathcal{R}_n$ the left-hand side of Equation (64) to be lower bounded. The supremum over all measures in $\mathcal{M}$ is lower bounded by the supremum over the two measures $\mu_1$ and $\mu_2$ and the loss $\ell_{\infty, M_\mu}$ by the distortion between endpoints $x$ and $y$. Finally, the supremum is lower bounded by the average. These inequalities yield

$$ \begin{aligned} \mathcal{R}_n &\ge \inf_{\hat{D}} \sup_{\mu \in \{\mu_1, \mu_2\}} \mathbb{E}_{\mu^{\otimes n}}[\ell_{\infty, M_\mu}(\hat{D}_X, D_M)] \\ &\ge \inf_{\hat{D}} \sup_{\mu \in \{\mu_1, \mu_2\}} \mathbb{E}_{\mu^{\otimes n}}\left[\left|\frac{\hat{D}_X(x, y) - D_{M_\mu}(x, y)}{\hat{D}_X(x, y) \vee D_{M_\mu}(x, y)}\right|\right] \\ &\ge \frac{1}{2} \inf_{\hat{D}} \left\{ \mathbb{E}_{\mu_1^{\otimes n}}\left[\left|\frac{\hat{D}_X(x, y) - D_{M_1}(x, y)}{\hat{D}_X(x, y) \vee D_{M_1}(x, y)}\right|\right] + \mathbb{E}_{\mu_2^{\otimes n}}\left[\left|\frac{\hat{D}_X(x, y) - D_{M_2}(x, y)}{\hat{D}_X(x, y) \vee D_{M_2}(x, y)}\right|\right] \right\} \\ &\ge \frac{1}{2} \inf_{\hat{D}} \mathbb{E}_{\mu_1^{\otimes n}}\left[\left(\left|\frac{\hat{D}_X(x, y) - D_{M_1}(x, y)}{\hat{D}_X(x, y) \vee D_{M_1}(x, y)}\right| + \left|\frac{\hat{D}_X(x, y) - D_{M_2}(x, y)}{\hat{D}_X(x, y) \vee D_{M_2}(x, y)}\right|\right) \left(1 \wedge \frac{d\mu_2^{\otimes n}}{d\mu_1^{\otimes n}}\right)\right] \end{aligned} $$

and it can be shown using elementary computations that for all $a, b > 0$,

$$ \min_{\delta \ge 0} \left( \left| \frac{\delta - a}{\delta \vee a} \right| + \left| \frac{\delta - b}{\delta \vee b} \right| \right) = \left| \frac{a - b}{a \vee b} \right|, $$
hence

$$ \mathcal{R}_n \geq \frac{1}{2} \mathbb{E}_{\mu_1^{\otimes n}} \left[ \left| \frac{D_{M_1}(x, y) - D_{M_2}(x, y)}{D_{M_1}(x, y) \vee D_{M_2}(x, y)} \right| \left( 1 \wedge \frac{d\mu_2^{\otimes n}}{d\mu_1^{\otimes n}} \right) \right]. $$

Moreover, using the properties of the total variation distance along with the assumption that $d_{\text{TV}}(\mu_1, \mu_2) \leq \frac{1}{n}$ and $n \geq 2$,

$$ \mathbb{E}_{\mu_1^{\otimes n}} \left[ 1 \wedge \frac{d\mu_2^{\otimes n}}{d\mu_1^{\otimes n}} \right] = 1 - d_{\text{TV}}(\mu_1^{\otimes n}, \mu_2^{\otimes n}) = (1 - d_{\text{TV}}(\mu_1, \mu_2))^{n} \geq \left(1 - \frac{1}{n}\right)^{n} \geq \frac{1}{4}, $$

hence

$$ \mathcal{R}_n \geq \frac{1}{8} \left| \frac{D_{M_1}(x, y) - D_{M_2}(x, y)}{D_{M_1}(x, y) \vee D_{M_2}(x, y)} \right| $$

which concludes the proof.

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

Let us now prove Theorem 4.6 using Theorem C.1 with the measures $\mu_1$ and $\mu_2$ described in Section 4.3. The total variation distance between $\mu_1, \mu_2 \in \mathcal{M}(d, L, \tau)$ is the fraction of volume of $M_1$ that was carved out to create $M_2$. The carved volume is upper bounded by $\|x - y\| \rho^{d-1}$ where $\rho$ is the distance of the middle of the black arcs in Figure 2 to the missing edge, that is $\rho = (\tau - \delta)/\sqrt{d-1}$ where $\delta = \sqrt{\tau^2 - \varepsilon^2}$ is the distance from the edge to the center of the ball used to carve $M_2$. Then,

$$ \begin{aligned} d_{\text{TV}}(\mu_1, \mu_2) &\le \frac{\|x - y\| \rho^{d-1}}{(2\alpha L)^d} \\ &= \frac{2\varepsilon}{(\alpha L)^d (d-1)^{\frac{d-1}{2}}} \tau^{d-1} \left(1 - \sqrt{1 - \frac{\varepsilon^2}{\tau^2}}\right)^{d-1} \\ &\le \frac{2}{\alpha^d (d-1)^{\frac{d-1}{2}}} \frac{\varepsilon \tau^{d-1}}{L^d} \left(\frac{\varepsilon^2}{\tau^2}\right)^{d-1} \\ &= \beta \frac{\varepsilon^{2d-1}}{L^d \tau^{d-1}} \end{aligned} $$

where $\beta = 2\alpha^{-d}(d-1)^{-(d-1)/2}$ is a constant depending only on $d$. Moreover, since a geodesic between $x$ and $y$ is a straight line in $M_1$ and an arc of radius $\tau$ in $M_2$, the induced distortion is

$$ \frac{D_{M_2}(x, y) - D_{M_1}(x, y)}{D_{M_2}(x, y) \vee D_{M_1}(x, y)} = \frac{\arcsin\left(\frac{\|x-y\|}{2\tau}\right) - \frac{\|x-y\|}{2\tau}}{\arcsin\left(\frac{\|x-y\|}{2\tau}\right)} \ge \frac{1}{6} \left(\frac{\|x-y\|}{2\tau}\right)^2 = \frac{\varepsilon^2}{6\tau^2} $$

using Equation (27) to get the lower bound. Then, by letting

$$ \varepsilon = \left( \frac{L^d \tau^{d-1}}{\beta n} \right)^{\frac{1}{2d-1}}, $$

which is indeed smaller than both $\alpha L$ and $\tau$ for $n$ large enough depending on $d$, $L$ and $\tau$, one has $d_{\text{TV}}(\mu_1, \mu_2) \leq \frac{1}{n}$ and

$$ \frac{D_{M_2}(x, y) - D_{M_1}(x, y)}{D_{M_2}(x, y) \vee D_{M_1}(x, y)} \ge \frac{1}{6} \left( \frac{L^d}{\beta \tau^d n} \right)^{\frac{2}{2d-1}}. $$

Theorem 4.6 then follows from Theorem C.1.