Distance function

This article covers the distance function in mathematics. For the concept of the same name in economics, see distance function (microeconomics) .

Distance functions are certain real-valued mapping of metric spaces that transfer the properties of the underlying metric to single-digit functions. The concept of distance functions was introduced in 2011 by Chazal, Cohen-Steiner and Mérigot and can be used, among other things, in geometric and stochastic measurement theory and in data mining .

definition

Let be a non-empty metric space whose metric is induced by a norm without loss of generality (cf. Kunugui's theorem ). ${\displaystyle (X;d_{X})}$ ${\displaystyle \|.\|_{X}}$

A distance function on is now a mapping (which does not assume any negative values) with the following three properties: ${\displaystyle X}$ ${\displaystyle d\colon X\to \mathbb {R} _{0}^{+}}$

1. The function itself is 1- Lipschitz continuous : For every two points the following applies ${\displaystyle x;y\in X}$ ${\displaystyle |d(x)-d(y)|\leq \|x-y\|_{X}}$
2. The function's square is 1-semiconcave: this is equivalent to being a concave function . ${\displaystyle x\mapsto d(x)^{2}-\|x\|_{X}^{2}}$
3. The function diverges whenever the standard does it: The same applies to every network in with . ${\displaystyle (x_{i})_{i\in I}}$ ${\displaystyle X}$ ${\displaystyle \|x_{i}\|_{X}\to \infty }$ ${\displaystyle d(x_{i})\to \infty }$

Pseudo distance function

Strictly speaking, it is sufficient to demand the second and third properties of the above definition, since the 1-Lipschitz continuity of the original mapping already follows from the 1-semiconcavity of the square of a function. However, the first property is clearly what makes a function distance-like: It is easy to calculate that it is 1-Lipschitz continuous if and only if it is compatible with the metric, i.e. if it always holds for every two elements . ${\displaystyle d}$ ${\displaystyle d_{X}}$ ${\displaystyle x;y\in X}$ ${\displaystyle d(x)\leq d(y)+d_{X}(x;y)}$

In a weakening manner of speaking, a function is therefore also called a pseudo-distance function if it is 1-Lipschitz continuous and diverges with the norm. ${\displaystyle d\colon X\to \mathbb {R} _{0}^{+}}$

Distance function to a crowd

The prototype of a distance function is the distance to a compact subset , which is explained by. The compactness here has the effect that the infimum is always actually assumed for at least one point . The 1-Lipschitz continuity then follows from the triangle inequality. ${\displaystyle K\subseteq X}$ ${\displaystyle d_{K}(x)=\inf _{k\in K}\|x-k\|_{X}}$ ${\displaystyle K}$

Distance function to a measure

If we now also add a measure and a real number, it can be shown that by ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle 0\leq m<\mu (X)}$

${\displaystyle \delta _{\mu ;m}(x)=\inf\{r>0|\mu ({\overline {B}}_{r}(x))>m\}}$

a pseudo-distance function is explained, where the closed sphere um denotes with radius . ${\displaystyle {\overline {B}}_{r}(x)=\{y\in X|d_{X}(x;y)\leq r\}}$ ${\displaystyle x}$ ${\displaystyle r}$

For every real number, say the map ${\displaystyle 0<m_{0}<\mu (X)}$

${\displaystyle d_{\mu ;m_{0}}\colon X\to \mathbb {R} _{0}^{+};\ x\mapsto {\sqrt {{\frac {1}{m_{0}}}\int _{0}^{m_{0}}\delta _{\mu ;m}(x)^{2}\ \mathrm {d} m}}}$

the distance function to the dimension with parameter . ${\displaystyle \mu }$ ${\displaystyle m_{0}}$

Differentiability

According to Rademacher's theorem , (pseudo-) distance functions are metrically differentiable almost everywhere , since they are Lipschitz continuous.

Is especially Euclidean , then from Alexandrov's theorem, with the semi-concavity of the square, the twofold (total) differentiability of distance functions almost everywhere follows . ${\displaystyle X=\mathbb {R} ^{n}}$

This enables a detailed investigation of distance functions and the underlying spaces by considering the gradient, comparable to the Morse theory in differential topology .

Individual evidence

1. ^ Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Vol. 11, No. 6, 2011, ISSN  1615-3375 , pp. 733-751, doi : 10.1007 / s10208-011-9098-0 , (online PDF; 628 kB) .
2. ^ Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Vol. 11, No. 6, 2011, ISSN  1615-3375 , pp. 733-751, Proposition 3.1, doi : 10.1007 / s10208-011-9098-0 , (online PDF; 628 kB) .
3. ^ ^{A b} Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Vol. 11, No. 6, 2011, ISSN  1615-3375 , pp. 733-751, Section 3, doi : 10.1007 / s10208-011-9098-0 , (online PDF; 628 kB) .
4. ^ Karsten Grove : Critical Point Theory for Distance Functions. In: Proceedings of Symposia in Pure Mathematics. Vol. 54, No. 3, 1993, ISSN  0082-0717 , pp. 357-385, (Grove uses the term distance function here in the sense of the above definition, without, however, anticipating the comprehensive theory of Chazal et al.).