Editing Metric space (section)

== Further examples and applications ==
=== Graphs and finite metric spaces ===
A {{visible anchor|metric space is ''discrete''|Discrete metric space}} if its induced topology is the [[discrete topology]].  Although many concepts, such as completeness and compactness, are not interesting for such spaces, they are nevertheless an object of study in several branches of mathematics.  In particular, {{visible anchor|finite metric spaces|Finite metric space}} (those having a [[finite set|finite]] number of points) are studied in [[combinatorics]] and [[theoretical computer science]].<ref>{{cite book |chapter=Finite metric-spaces—combinatorics, geometry and algorithms |last1=Linial |first1=Nathan |author-link1=Nati Linial |title=Proceedings of the ICM, Beijing 2002 |year=2003 |volume=3 |pages=573–586 |arxiv=math/0304466}}</ref>  Embeddings in other metric spaces are particularly well-studied.  For example, not every finite metric space can be [[isometry|isometrically embedded]] in a Euclidean space or in [[Hilbert space]].  On the other hand, in the worst case the required distortion (bilipschitz constant) is only logarithmic in the number of points.<ref>{{cite journal|doi=10.1007/BF02776078|doi-access=|title=On lipschitz embedding of finite metric spaces in Hilbert space|year=1985|last1=Bourgain|first1=J. |author-link1=Jean Bourgain |journal=[[Israel Journal of Mathematics]]|volume=52|issue=1–2|pages=46–52|s2cid=121649019}}</ref><ref>[[Jiří Matoušek (mathematician)|Jiří Matoušek]] and [[Assaf Naor]], ed. [http://kam.mff.cuni.cz/~matousek/metrop.ps "Open problems on embeddings of finite metric spaces"]. {{webarchive|url=https://web.archive.org/web/20101226232112/http://kam.mff.cuni.cz/~matousek/metrop.ps |date=2010-12-26 }}.</ref>

For any [[graph (discrete mathematics)|undirected connected graph]] {{mvar|G}}, the set {{mvar|V}} of vertices of {{mvar|G}} can be turned into a metric space by defining the [[distance (graph theory)|distance]] between vertices {{mvar|x}} and {{mvar|y}} to be the length of the shortest edge path connecting them. This is also called ''shortest-path distance'' or ''geodesic distance''. In [[geometric group theory]] this construction is applied to the [[Cayley graph]] of a (typically infinite) [[finitely-generated group]], yielding the [[word metric]].  Up to a bilipschitz homeomorphism, the word metric depends only on the group and not on the chosen finite generating set.{{sfn|Margalit|Thomas|2017}}

=== Metric embeddings and approximations ===

An important area of study in finite metric spaces is the embedding of complex metric spaces into simpler ones while controlling the distortion of distances. This is particularly useful in computer science and discrete mathematics, where algorithms often perform more efficiently on simpler structures like tree metrics.

A significant result in this area is that any finite metric space can be probabilistically embedded into a ''tree metric'' with an expected distortion of <math>O(log n)</math>, where <math>n</math> is the number of points in the metric space.<ref>{{cite journal|last1=Fakcharoenphol|first1=J.|last2=Rao|first2=S.|last3=Talwar|first3=K.|year=2004|title=A tight bound on approximating arbitrary metrics by tree metrics|journal=Journal of Computer and System Sciences|volume=69|issue=3|pages=485–497|doi=10.1016/j.jcss.2004.04.011}}</ref>

This embedding is notable because it achieves the best possible asymptotic bound on distortion, matching the lower bound of <math>\Omega(log n)</math>. The tree metrics produced in this embedding ''dominate'' the original metrics, meaning that distances in the tree are greater than or equal to those in the original space. This property is particularly useful for designing approximation algorithms, as it allows for the preservation of distance-related properties while simplifying the underlying structure.

The result has significant implications for various computational problems:

* '''Network design''': Improves approximation algorithms for problems like the ''Group Steiner tree problem'' (a generalization of the ''[[Steiner tree problem]]'') and ''Buy-at-bulk network design'' (a problem in ''[[Network planning and design]]'') by simplifying the metric space to a tree metric.
* '''Clustering''': Enhances algorithms for clustering problems where hierarchical clustering can be performed more efficiently on tree metrics.
* '''Online algorithms''': Benefits problems like the ''[[k-server problem]]'' and ''[[metrical task system]]'' by providing better competitive ratios through simplified metrics.

The technique involves constructing a hierarchical decomposition of the original metric space and converting it into a tree metric via a randomized algorithm. The <math>O(log n)</math> distortion bound has led to improved [[approximation ratio]]s in several algorithmic problems, demonstrating the practical significance of this theoretical result.

=== Distances between mathematical objects ===
In modern mathematics, one often studies spaces whose points are themselves mathematical objects.  A distance function on such a space generally aims to measure the dissimilarity between two objects.  Here are some examples:
* '''Functions to a metric space.''' If {{mvar|X}} is any set and {{mvar|M}} is a metric space, then the set of all [[bounded function]]s <math>f \colon X \to M</math> (i.e. those functions whose image is a [[bounded subset]] of <math>M</math>) can be turned into a metric space by defining the distance between two bounded functions {{mvar|f}} and {{mvar|g}} to be <math display="block">d(f,g) = \sup_{x \in X} d(f(x),g(x)).</math> This metric is called the [[uniform metric]] or supremum metric.{{sfn|Ó Searcóid|2006|p=107}}  If {{mvar|M}} is complete, then this [[function space]] is complete as well; moreover, if {{mvar|X}} is also a topological space, then the subspace consisting of all bounded [[continuous function (topology)|continuous]] functions from {{mvar|X}} to {{mvar|M}} is also complete.  When {{mvar|X}} is a subspace of <math>\R^n</math>, this function space is known as a [[classical Wiener space]].
* '''[[String metric]]s and [[edit distance]]s.''' There are many ways of measuring distances between [[string (computer science)|strings of characters]], which may represent [[sentence (linguistics)|sentence]]s in [[computational linguistics]] or [[Code word (communication)|code word]]s in [[coding theory]].  ''Edit distances'' attempt to measure the number of changes necessary to get from one string to another.  For example, the [[Hamming distance]] measures the minimal number of substitutions needed, while the [[Levenshtein distance]] measures the minimal number of deletions, insertions, and substitutions; both of these can be thought of as distances in an appropriate graph.
* [[Graph edit distance]] is a measure of dissimilarity between two [[Graph (discrete mathematics)|graphs]], defined as the minimal number of [[Graph operations|graph edit operations]] required to transform one graph into another.
* [[Wasserstein metric]]s measure the distance between two [[measure (mathematics)|measure]]s on the same metric space.  The Wasserstein distance between two measures is, roughly speaking, the [[optimal transport|cost of transporting]] one to the other.
* The set of all {{mvar|m}} by {{mvar|n}} [[matrix (mathematics)|matrices]] over some [[field (mathematics)|field]] is a metric space with respect to the [[Rank (linear algebra)|rank]] distance <math>d(A,B) = \mathrm{rank}(B - A)</math>.
* The [[Helly metric]] in [[game theory]] measures the difference between [[strategy (game theory)|strategies]] in a game.

=== Hausdorff and Gromov–Hausdorff distance ===
The idea of spaces of mathematical objects can also be applied to subsets of a metric space, as well as metric spaces themselves. [[Hausdorff distance|Hausdorff]] and [[Gromov–Hausdorff convergence|Gromov–Hausdorff distance]] define metrics on the set of compact subsets of a metric space and the set of compact metric spaces, respectively.

{{anchor|Distance to a set}}
Suppose {{math|(''M'', ''d'')}} is a metric space, and let {{mvar|S}} be a subset of {{mvar|M}}.  The ''distance from {{mvar|S}} to a point {{mvar|x}} of {{mvar|M}}'' is, informally, the distance from {{mvar|x}} to the closest point of {{mvar|S}}.  However, since there may not be a single closest point, it is defined via an [[infimum]]:
<math display="block">d(x,S) = \inf\{d(x,s) : s \in S \}.</math>
In particular, <math>d(x, S)=0</math> if and only if {{mvar|x}} belongs to the [[closure (topology)|closure]] of {{mvar|S}}. Furthermore, distances between points and sets satisfy a version of the triangle inequality:
<math display="block">d(x,S) \leq d(x,y) + d(y,S),</math>
and therefore the map <math>d_S:M \to \R</math> defined by <math>d_S(x)=d(x,S)</math> is continuous.  Incidentally, this shows that metric spaces are [[completely regular]].

Given two subsets {{mvar|S}} and {{mvar|T}} of {{mvar|M}}, their ''Hausdorff distance'' is
<math display="block">d_H(S,T) = \max \{ \sup\{d(s,T) : s \in S \} , \sup\{ d(t,S) : t \in T \} \}.</math>
Informally, two sets {{mvar|S}} and {{mvar|T}} are close to each other in the Hausdorff distance if no element of {{mvar|S}} is too far from {{mvar|T}} and vice versa.  For example, if {{mvar|S}} is an open set in Euclidean space {{mvar|T}} is an [[Delone set|ε-net]] inside {{mvar|S}}, then <math>d_H(S,T)<\varepsilon</math>.  In general, the Hausdorff distance <math>d_H(S,T)</math> can be infinite or zero.  However, the Hausdorff distance between two distinct compact sets is always positive and finite.  Thus the Hausdorff distance defines a metric on the set of compact subsets of {{mvar|M}}.

The Gromov–Hausdorff metric defines a distance between (isometry classes of) compact metric spaces.  The ''Gromov–Hausdorff distance'' between compact spaces {{mvar|X}} and {{mvar|Y}} is the infimum of the Hausdorff distance over all metric spaces {{mvar|Z}} that contain {{mvar|X}} and {{mvar|Y}} as subspaces.  While the exact value of the Gromov–Hausdorff distance is rarely useful to know, the resulting topology has found many applications.

=== Miscellaneous examples === <!-- the goal is to remove these or incorporate them under the various subheadings -->
* Given a metric space {{math|(''X'', ''d'')}} and an increasing [[concave function]] <math>f \colon [0,\infty) \to [0,\infty)</math> such that {{math|''f''(''t'') {{=}} 0}} if and only if {{math|''t'' {{=}} 0}}, then <math>d_f(x,y)=f(d(x,y))</math> is also a metric on {{mvar|X}}.  If {{math|''f''(''t'') {{=}} ''t''<sup>α</sup>}} for some real number {{math|α < 1}}, such a metric is known as a '''snowflake''' of {{mvar|d}}.<ref>{{cite conference |last1=Gottlieb |first1=Lee-Ad |last2=Solomon |first2=Shay |title=Light spanners for snowflake metrics |conference=SOCG '14: Proceedings of the thirtieth annual symposium on Computational geometry |date=8 June 2014 |pages=387–395 |doi=10.1145/2582112.2582140|arxiv=1401.5014 }}</ref>
* The [[tight span]] of a metric space is another metric space which can be thought of as an abstract version of the [[convex hull]].
* The ''knight's move metric'', the minimal number of knight's moves to reach one point in <math>\mathbb{Z}^2</math> from another, is a metric on <math>\mathbb{Z}^2</math>.
* {{anchor|SNCF}}The [[British Rail]] metric (also called the "post office metric" or the "[[French railway metrics|French railway metric]]") on a [[normed vector space]] is given by <math>d(x,y) = \lVert x \rVert + \lVert y \rVert</math> for distinct points <math>x</math> and <math>y</math>, and <math>d(x,x) = 0</math>. More generally <math>\lVert \cdot \rVert</math> can be replaced with a function <math>f</math> taking an arbitrary set <math>S</math> to non-negative reals and taking the value <math>0</math> at most once:  then the metric is defined on <math>S</math> by <math>d(x,y) = f(x) + f(y)</math> for distinct points <math>x</math> and <math>y</math>, and {{nowrap|<math>d(x,x) = 0</math>.}}  The name alludes to the tendency of railway journeys to proceed via London (or Paris) irrespective of their final destination.<!-- source? -->
* The [[Robinson–Foulds metric]] used for calculating the distances between [[Phylogenetic tree]]s in [[Phylogenetics]]<ref>{{Cite journal|last1=Robinson|first1=D.F.|last2=Foulds|first2=L.R.|date=February 1981|title=Comparison of phylogenetic trees|url=https://linkinghub.elsevier.com/retrieve/pii/0025556481900432|journal=Mathematical Biosciences|language=en|volume=53|issue=1–2|pages=131–147|doi=10.1016/0025-5564(81)90043-2|s2cid=121156920 |url-access=subscription}}</ref>