View source for Distance

{{short description|Straight line that connects two points in a measurable space or in an observable physical space}}
{{about|distance in mathematics, physics, and computation}}

'''Distance''' is a numerical [[measurement]] of how far apart objects or points are. In [[physics]] or everyday usage, distance may refer to a physical [[length]] or an estimation based on other criteria (e.g. "two counties over"). In most cases, "distance from A to B" is interchangeable with "distance from B to A". In [[mathematics]], a distance function or [[metric (mathematics)|metric]] is a generalization of the concept of physical distance. A metric is a function that behaves according to a specific set of rules, and is a way of describing what it means for elements of some space to be "close to" or "far away from" each other.

==Overview and definitions==

===Physical distances===
[[File:Greatcircle Jetstream routes.svg|thumb|400px|Airline routes between [[Los Angeles]] and [[Tokyo]] approximately follow a direct [[great circle]] route (top), but use the [[jet stream]] (bottom) when heading eastwards.  Note that the shortest route appears as a curve rather than a straight line because this map is a [[Mercator projection]], which does not scale all distances equally compared to the real spherical surface of the Earth.]]
[[File:Manhattan distance.svg|thumb|200px|"Manhattan distance" on a grid]]

A physical distance can mean several different things:
* Distance Travelled: The length of a specific path travelled between two points, such as the distance walked while navigating a maze
* Straight-Line (Euclidean) Distance: The length of the shortest possible path through space, between two points, that could be taken if there were no obstacles (usually formalized as [[Euclidean distance]])
* Geodesic Distance: The length of the shortest path between two points while remaining on some surface, such as the [[great-circle distance]] along the [[Figure of the Earth|curve of the Earth]]
* The length of a specific path that returns to the starting point, such as a ball thrown straight up, or the Earth when it completes one [[orbit]].
[[File:Distance board in Vizag.jpg|thumb|A board showing distances near [[Visakhapatnam]]]]

"Circular distance" is the distance traveled by a wheel, which can be useful when designing vehicles or mechanical gears. The circumference of the wheel is 2''&pi;''&nbsp;&times;&nbsp;radius, and assuming the radius to be&nbsp;1, then each revolution of the wheel is equivalent of the distance 2''&pi;'' radians. In engineering ''&omega;''&nbsp;=&nbsp;2''&pi;&fnof;'' is often used, where ''&fnof;'' is the [[frequency]].

Unusual definitions of distance can be helpful to model certain physical situations, but are also used in theoretical mathematics:
* "[[Manhattan distance]]" is a rectilinear distance, named after the number of blocks north, south, east, or west a taxicab must travel on to reach its destination on the grid of streets in parts of New York City.
* "Chessboard distance", formalized as [[Chebyshev distance]], is the minimum number of moves a king must make on a [[chessboard]] to travel between two squares.

[[Distance measures (cosmology)|Distance measures in cosmology]] are complicated by the [[expansion of the universe]], and by effects described by the [[theory of relativity]] such as [[length contraction]] of moving objects.

===Theoretical distances===

The term "distance" is also used by analogy to measure non-physical entities in certain ways.

In computer science, there is the notion of the "[[edit distance]]" between two strings.  For example, the words "dog" and "dot", which vary by only one letter, are closer than "dog" and "cat", which differ by three letters.  This idea is used in [[spell checker]]s and in [[coding theory]], and is mathematically formalized in several different ways, such as:
* [[Levenshtein distance]]
* [[Hamming distance]]
* [[Lee distance]]
* [[Jaro–Winkler distance]]

In mathematics, a [[metric space]] is a set for which distances between all members of the set are defined.  In this way, many different types of "distances" can be calculated, such as for traversal of graphs, comparison of distributions and curves, and using unusual definitions of "space" (for example using a [[manifold]] or [[Reflection (mathematics)|reflections]]).  The notion of [[Distance (graph theory)|distance in graph theory]] has been used to describe [[social network]]s, for example with the [[Erdős number]] or the [[Bacon number]], the number of collaborative relationships away a person is from prolific mathematician [[Paul Erdős]] or actor [[Kevin Bacon]], respectively.

In psychology, human geography, and the social sciences, distance is often theorized not as an objective metric, but as a subjective experience.

== Distance versus directed distance and displacement ==
[[File:Distancedisplacement.svg|thumb|Distance along a path compared with displacement]]
Both distance and displacement measure the movement of an object. Distance cannot be [[negative number|negative]], and never decreases. Distance is a [[scalar (physics)|scalar]] quantity, or a [[Magnitude (mathematics)|magnitude]].  Whereas [[displacement (vector)|displacement]] is a [[Vector (geometry)|vector]] quantity with both magnitude and [[Direction (geometry, geography)|direction]]. It can be negative, zero, or positive. Directed distance does not measure movement, it measures the separation of two points, and can be a positive, zero, or negative vector.<ref name="ittcKU">{{cite web |title=The Directed Distance |url=http://www.ittc.ku.edu/~jstiles/220/handouts/The%20Directed%20Distance.pdf |website=Information and Telecommunication Technology Center |publisher=University of Kansas |accessdate=18 September 2018 |archiveurl=https://web.archive.org/web/20161110044317/http://www.ittc.ku.edu/~jstiles/220/handouts/The%20Directed%20Distance.pdf |archivedate=10 November 2016}}</ref>

The distance covered by a vehicle (for example as recorded by an [[odometer]]), person, animal, or object along a curved path from a point ''A'' to a point ''B'' should be distinguished from the straight-line distance from ''A'' to ''B''. For example, whatever the distance covered during a round trip from ''A'' to ''B'' and back to ''A'', the displacement is zero as start and end points coincide. In general the straight-line distance does not equal distance travelled, except for journeys in a straight line.

=== Directed distance ===

Directed distances can be determined along straight lines and along curved lines.

Directed distances along straight lines are vectors that give the distance and direction between a starting point and an ending point. A directed distance of a point ''C'' from point ''A'' in the direction of ''B'' on a line ''AB'' in a [[Euclidean vector space]] is the distance from ''A'' to ''C'' if ''C'' falls on the ray ''AB'', but is the negative of that distance if ''C'' falls on the ray ''BA'' (I.e., if ''C'' is not on the same side of ''A'' as ''B'' is). For example, the directed distance from the New York City Main Library flag pole to the Statue of Liberty flag pole has: 
* a starting point: library flag pole
* an ending point: statue flag pole
* a direction: -38°
* a distance: 8.72 km

Another kind of directed distance is that between two different particles or point masses at a given time. For instance, the distance from the [[center of gravity]] of the Earth ''A'' and the center of gravity of the Moon ''B'' (which does not strictly imply motion from ''A'' to ''B'') falls into this category.

A directed distance along a curved line is not a vector and is represented by a segment of that curved line defined by endpoints ''A'' and ''B'', with some specific information indicating the sense (or direction) of an ideal or real motion from one endpoint of the segment to the other (see figure). For instance, just labelling the two endpoints as ''A'' and ''B'' can indicate the sense, if the ordered sequence (''A'', ''B'') is assumed, which implies that ''A'' is the starting point.

===Displacement===

A displacement (see above) is a special kind of directed distance defined in [[mechanics]]. A directed distance is called displacement when it is the distance along a straight line (minimum distance) from ''A'' and ''B'', and when ''A'' and ''B'' are positions occupied by the ''same particle'' at two ''different instants'' of time. This implies [[motion (physics)|motion]] of the particle. The distance traveled by a particle must always be greater than or equal to its displacement, with equality occurring only when the particle moves along a straight path.

==Mathematics==
{{see also|Metric (mathematics)}}

===Geometry===
In [[analytic geometry]], the distance between two points of the [[Cartesian coordinate system|xy-plane]] can be found using the distance formula.  The distance between (''x''<sub>1</sub>, ''y''<sub>1</sub>) and (''x''<sub>2</sub>, ''y''<sub>2</sub>) is given by:
:<math>d=\sqrt{(\Delta x)^2+(\Delta y)^2}=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.</math>
Similarly, given points (''x''<sub>1</sub>, ''y''<sub>1</sub>, ''z''<sub>1</sub>) and (''x''<sub>2</sub>, ''y''<sub>2</sub>, ''z''<sub>2</sub>) in [[Cartesian coordinate system|three-space]], the distance between them is:
:<math>d=\sqrt{(\Delta x)^2+(\Delta y)^2+(\Delta z)^2}=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}.</math>
These formula are easily derived by constructing a right triangle with a leg on the [[hypotenuse]] of another (with the other leg [[orthogonal]] to the [[Plane (mathematics)|plane]] that contains the 1st triangle) and applying the [[Pythagorean theorem]].
In the study of complicated geometries, we call this (most common) type of distance [[Euclidean distance]], as it is derived from the [[Pythagorean theorem]], which does not hold in [[Non-Euclidean geometry|non-Euclidean geometries]]. This distance [[formula]] can also be expanded into the [[arc length|arc-length formula]].

===Distance in Euclidean space===
In the [[Euclidean space]] '''R'''<sup>n</sup>, the distance between two points is usually given by the [[Euclidean distance]] (2-norm distance).  Other distances, based on other [[norm (mathematics)|norms]], are sometimes used instead.

For a point (''x''<sub>1</sub>, ''x''<sub>2</sub>, ...,''x''<sub>''n''</sub>) and a point (''y''<sub>1</sub>, ''y''<sub>2</sub>, ...,''y''<sub>''n''</sub>), the '''[[Minkowski distance]]''' of order ''p'' ('''''p''-norm distance''') is defined as:
{| cellpadding="2"
| 1-norm distance || <math> = \sum_{i=1}^n \left| x_i - y_i \right|</math>
|-
| 2-norm distance || <math> = \left( \sum_{i=1}^n \left| x_i - y_i \right|^2 \right)^{1/2}</math>
|-
| ''p''-norm distance ||<math> = \left( \sum_{i=1}^n \left| x_i - y_i \right|^p \right)^{1/p}</math>
|-
| infinity norm distance ||<math> = \lim_{p \to \infty} \left( \sum_{i=1}^n \left| x_i - y_i \right|^p \right)^{1/p}</math>
|-
| || <math> = \max \left(|x_1 - y_1|,  |x_2 - y_2|,  \ldots, |x_n - y_n| \right).</math>
|}

''p'' need not be an integer, but it cannot be less than 1, because otherwise the [[triangle inequality]] does not hold.

The 2-norm distance is the [[Euclidean distance]], a generalization of the [[Pythagorean theorem]] to more than two [[coordinates]]. It is what would be obtained if the distance between two points were measured with a [[ruler]]: the "intuitive" idea of distance.

The 1-norm distance is more colourfully called the ''taxicab norm'' or ''[[taxicab geometry|Manhattan distance]]'', because it is the distance a car would drive in a city laid out in square blocks (if there are no one-way streets).

The infinity norm distance is also called [[Chebyshev distance]]. In 2D, it is the minimum number of moves [[king (chess)|king]]s require to travel between two squares on a [[chessboard]].

The ''p''-norm is rarely used for values of ''p'' other than 1, 2, and infinity, but see [[super ellipse]].

In physical space the Euclidean distance is in a way the most natural one, because in this case the length of a [[rigid body]] does not change with [[rotation]].

===Variational formulation of distance===
The Euclidean distance between two points in space (<math>A = \vec{r}(0)</math> and <math>B = \vec{r}(T)</math>) may be written in a [[calculus of variations|variational]] form where the distance is the minimum value of an integral:

: <math>
D = \int_0^T \sqrt{\left({\partial \vec{r}(t) \over \partial t}\right)^2} \, dt
</math>

Here <math>\vec{r}(t)</math> is the trajectory (path) between the two points. The value of the integral (D) represents the length of this trajectory. The distance is the minimal value of this integral and is obtained when <math>r = r^{*}</math> where <math>r^{*}</math> is the optimal trajectory. In the familiar Euclidean case (the above integral) this optimal trajectory is simply a straight line. It is well known that the shortest path between two points is a straight line. Straight lines can formally be obtained by solving the [[Euler–Lagrange equations]] for the above [[functional (mathematics)|functional]]. In [[non-Euclidean geometry|non-Euclidean]] manifolds (curved spaces) where the nature of the space is represented by a [[metric tensor]] <math>g_{ab}</math> the integrand has to be modified to <math>\sqrt{g^{ac}\dot{r}_c g_{ab}\dot{r}^b}</math>, where [[Einstein summation convention]] has been used.

===Generalization to higher-dimensional objects===
The Euclidean distance between two objects may also be generalized to the case where the objects are no longer points but are higher-dimensional [[manifolds]], such as space curves, so in addition to talking about distance between two points one can discuss concepts of distance between two strings. Since the new objects that are dealt with are extended objects (not points anymore) additional concepts such as non-extensibility, [[curvature]] constraints, and non-local interactions that enforce non-crossing become central to the notion of distance. The distance between the two manifolds is the [[Scalar (mathematics)|scalar quantity]] that results from minimizing the generalized distance functional, which represents a transformation between the two manifolds:

: <math>
\mathcal {D} = \int_0^L\int_0^T \left \{ \sqrt{\left({\partial \vec{r}(s,t) \over \partial t}\right)^2} + \lambda \left[\sqrt{\left({\partial \vec{r}(s,t) \over \partial s}\right)^2} - 1\right] \right\} \, ds \, dt
</math>

The above double integral is the generalized distance functional between two polymer conformation. <math>s</math> is a spatial parameter and <math>t</math> is pseudo-time. This means that <math>\vec{r}(s,t=t_i)</math> is the polymer/string conformation at time <math>t_i</math> and is parameterized along the string length by <math> s</math>. Similarly <math>\vec{r}(s=S,t)</math> is the trajectory of an infinitesimal segment of the string during transformation of the entire string from conformation <math>\vec{r}(s,0)</math> to conformation <math>\vec{r}(s,T)</math>. The term with cofactor <math>\lambda</math> is a [[Lagrange multiplier]] and its role is to ensure that the length of the polymer remains the same during the transformation. If two discrete polymers are inextensible, then the minimal-distance transformation between them no longer involves purely straight-line motion, even on a Euclidean metric. There is a potential application of such generalized distance to the problem of [[protein folding]]<ref>SS Plotkin, PNAS.2007; 104: 14899–14904,</ref><ref>AR Mohazab, SS Plotkin,"Minimal Folding Pathways for Coarse-Grained Biopolymer Fragments" Biophysical Journal, Volume 95, Issue 12, Pages 5496–5507</ref>
This generalized distance is analogous to the [[Nambu–Goto action]] in [[string theory]], however there is no exact correspondence because the Euclidean distance in 3-space is inequivalent to the spacetime distance minimized for the classical relativistic string.

=== Algebraic distance ===
{{Expand section|date=December 2008}}
This is a metric often used in [[computer vision]] that can be minimized by [[least squares]] estimation. [http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/FISHER/ALGDIST/alg.htm][http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/FISHER/CIRCLEFIT/fit2dcircle/node3.html]  For curves or surfaces given by the equation <math>x^\text{T} C x=0</math> (such as a [[Conic#Homogeneous coordinates|conic in homogeneous coordinates]]), the algebraic distance from the point <math>x'</math> to the curve is simply <math>x'^\text{T} C x'</math>.
It may serve as an "initial guess" for [[geometric distance]] to refine estimations of the curve by more accurate methods, such as [[non-linear least squares]].

===General metric===
In [[mathematics]], in particular [[geometry]], a [[Metric (mathematics)|distance function]] on a given [[Set (mathematics)|set]] ''M'' is a [[Function (mathematics)|function]] {{nowrap|''d'': ''M'' × ''M'' → '''R'''}}, where '''R''' denotes the set of [[real number]]s, that satisfies the following conditions:
*{{nowrap|''d''(''x'',''y'') ≥ 0}}, and {{nowrap|1=''d''(''x'',''y'') = 0}} [[if and only if]] {{nowrap|1=''x'' = ''y''}}.  (Distance is positive between two different points, and is zero precisely from a point to itself.)
*It is [[Symmetric relation|symmetric]]: {{nowrap|1=''d''(''x'',''y'') = ''d''(''y'',''x'')}}.  (The distance between ''x'' and ''y'' is the same in either direction.)
*It satisfies the [[triangle inequality]]: {{nowrap|''d''(''x'',''z'') ≤ ''d''(''x'',''y'') + ''d''(''y'',''z'')}}.  (The distance between two points is the shortest distance along any path). Such a distance function is known as a [[Metric (mathematics)|metric]].  Together with the set, it makes up a [[metric space]].

For example, the usual definition of distance between two real numbers ''x'' and ''y'' is: {{nowrap|1=''d''(''x'',''y'') = {{abs|''x'' − ''y''}}}}. This definition satisfies the three conditions above, and corresponds to the standard [[topology]] of the [[real line]]. But distance on a given set is a definitional choice. Another possible choice is to define: {{nowrap|1=''d''(''x'',''y'') = 0}} if {{nowrap|1=''x'' = ''y''}}, and 1 otherwise. This also defines a metric, but gives a completely different topology, the "[[discrete topology]]"; with this definition numbers cannot be arbitrarily close.

===Distances between sets and between a point and a set===
[[File:Distance between sets.svg|thumb| ''d''(''A'',&nbsp;''B'')&nbsp;>&nbsp;''d''(''A'',&nbsp;''C'')&nbsp;+&nbsp;''d''(''C'',&nbsp;''B'')]]
Various distance definitions are possible between objects. For example, between celestial bodies one should not confuse the surface-to-surface distance and the center-to-center distance. If the former is much less than the latter, as for a [[low earth orbit]], the first tends to be quoted (altitude), otherwise, e.g. for the Earth–Moon distance, the latter.

There are two common definitions for the distance between two non-empty [[subset]]s of a given [[metric space]]:
*One version of distance between two non-empty sets is the [[infimum]] of the distances between any two of their respective points, which is the everyday meaning of the word, i.e.
::<math>d(A,B)=\inf_{x\in A, y\in B} d(x,y).</math>
:This is a symmetric [[premetric space|premetric]]. On a collection of sets of which some touch or overlap each other, it is not "separating", because the distance between two different but touching or overlapping sets is zero. Also it is not [[hemimetric space|hemimetric]], i.e., the [[triangle inequality]] does not hold, except in special cases. Therefore only in special cases this distance makes a collection of sets a [[metric space]].
*The [[Hausdorff distance]] is the larger of two values, one being the [[supremum]], for a point ranging over one set, of the infimum, for a second point ranging over the other set, of the distance between the points, and the other value being likewise defined but with the roles of the two sets swapped. This distance makes the set of non-empty [[compact space|compact]] subsets of a metric space itself a [[metric space]].

The [[Metric space#Distance between points and sets; Hausdorff distance and Gromov metric|distance between a point and a set]] is the infimum of the distances between the point and those in the set. This corresponds to the distance, according to the first-mentioned definition above of the distance between sets, from the set containing only this point to the other set.

In terms of this, the definition of the Hausdorff distance can be simplified: it is the larger of two values, one being the supremum, for a point ranging over one set, of the distance between the point and the set, and the other value being likewise defined but with the roles of the two sets swapped.

===Graph theory===

In [[graph theory]] the [[Distance (graph theory)|distance]] between two vertices is the length of the shortest [[path (graph theory)|path]] between those vertices.

===Statistical distances===
{{main|Statistical distance}}
In [[statistics]] and [[information geometry]], there are many kinds of [[statistical distance]]s, notably [[divergence (statistics)|divergences]], especially [[Bregman divergence]]s and [[f-divergence|''f''-divergences]]. These include and generalize many of the notions of "difference between two [[probability distribution]]s", and allow them to be studied geometrically, as [[statistical manifold]]s. The most elementary is the [[squared Euclidean distance]], which forms the basis of [[least squares]]; this is the most basic Bregman divergence. The most important in [[information theory]] is the [[relative entropy]] ([[Kullback–Leibler divergence]]), which allows one to analogously study [[maximum likelihood estimation]] geometrically; this is the most basic ''f''-divergence, and is also a Bregman divergence (and is the only divergence that is both). Statistical manifolds corresponding to Bregman divergences are [[flat manifold]]s in the corresponding geometry, allowing an analog of the [[Pythagorean theorem]] (which is traditionally true for squared Euclidean distance) to be used for [[linear inverse problem]]s in inference by [[optimization theory]].

Other important statistical distances include the [[Mahalanobis distance]], the [[energy distance]], and many others.

===Other mathematical "distances"===
*[[Canberra distance]] – a weighted version of Manhattan distance, used in computer science

==See also==
{{wikiquote}}
{{div col|colwidth=22em}}

*[[Astronomical system of units]]
*[[Cosmic distance ladder]]
*[[Distance geometry problem]]
*[[Dijkstra's algorithm]]
*[[Distance matrix]]
*[[Distance measuring equipment]] (DME)
*[[Exit number#Distance-based numbers|Distance-based road exit numbers]]
*[[Engineering tolerance]]
*[[Length]]
*[[Meridian arc]]
*[[Milestone]]
*[[Multiplicative distance]]
*[[Orders of magnitude (length)]]
*[[Proper length]]
*[[Proxemics]] &ndash; physical distance between people
*[[Rangefinder]]
*[[Signed distance function]]
*[[Vertical distance]]
{{div col end}}

==References==
;Notes
{{Reflist}}
;Sources
*{{citation|last1=Deza|first1=E.|first2=M.|last2=Deza|author2-link=Michel Deza|title=Dictionary of Distances|year=2006|publisher=Elsevier|isbn=0-444-52087-2}}.

{{Kinematics}}

[[Category:Elementary mathematics]]
[[Category:Metric geometry]]
[[Category:Distance| ]]