Editing Distance

{{Short description|Separation between two points}}
{{other uses|Distance (disambiguation)}}
{{more citations needed|date=February 2020}}
[[File:Distance board in Vizag cropped.jpg|thumb|275px|A board showing distances near [[Visakhapatnam]], India]]

'''Distance''' is a numerical or occasionally qualitative [[measurement]] of how far apart objects, points, people, or ideas 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").  The term is also frequently used metaphorically<ref>{{cite book |last1=Schnall |first1=Simone |chapter=Are there basic metaphors? |title=The power of metaphor: Examining its influence on social life. |publisher=American Psychological Association |date=2014 |pages=225–247 |doi=10.1037/14278-010|isbn=978-1-4338-1579-9 |url=http://www.dspace.cam.ac.uk/handle/1810/244216 }}</ref> to mean a measurement of the amount of difference between two similar objects (such as [[statistical distance]] between [[probability distribution]]s or [[edit distance]] between [[string (computer science)|strings of text]]) or a degree of separation (as exemplified by [[distance (graph theory)|distance]] between people in a [[social network]]).  Most such notions of distance, both physical and metaphorical, are formalized in [[mathematics]] using the notion of a [[metric space]].

In the [[social science]]s, '''distance''' can refer to a qualitative measurement of separation, such as [[social distance]] or [[psychological distance]].

==Distances in physics and geometry<!--This article violates WP:NOBACKREF all over the place, but I think it sounds better that way, and in some places genuinely requires it.  Please think twice before changing it-->==

The distance between physical locations can be defined in different ways in different contexts.

===Straight-line or Euclidean distance===
{{main|Euclidean distance}}

The distance between two points in physical [[space]] is the [[length]] of a [[line segment|straight line]] between them, which is the shortest possible path.  This is the usual meaning of distance in [[classical physics]], including [[Newtonian mechanics]]. 

Straight-line distance is formalized mathematically as the [[Euclidean distance]] in [[two-dimensional Euclidean space|two-]] and [[three-dimensional space]].  In [[Euclidean geometry]], the distance between two points {{mvar|A}} and {{mvar|B}} is often denoted <math>|AB|</math>.  In [[Cartesian coordinate system|coordinate geometry]], Euclidean distance is computed using the [[Pythagorean theorem]]. The distance between points {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}} and {{math|(''x''<sub>2</sub>, ''y''<sub>2</sub>)}} in the plane is given by:<ref name=":0">{{Cite web|last=Weisstein|first=Eric W.|title=Distance|url=https://mathworld.wolfram.com/Distance.html|access-date=2020-09-01|website=mathworld.wolfram.com|language=en}}</ref><ref>{{Cite web|title=Distance Between 2 Points|url=https://www.mathsisfun.com/algebra/distance-2-points.html|access-date=2020-09-01|website=www.mathsisfun.com}}</ref>
<math display="block">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 three-dimensional space, the distance between them is:<ref name=":0" />
<math display="block">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>
This idea generalizes to higher-dimensional [[Euclidean space]]s.

==== Measurement ====
{{main|Distance measurement}}
There are many ways of [[measuring]] straight-line distances. For example, it can be done directly using a [[ruler]], or indirectly with a [[radar]] (for long distances) or [[interferometry]] (for very short distances).  The [[cosmic distance ladder]] is a set of ways of measuring extremely long distances.

===Shortest-path distance on a curved surface===
[[File:Greatcircle Jetstream routes.svg|thumb|400px|Airline routes between [[Los Angeles]] and [[Tokyo]] approximately follow a [[great circle]] going west (top) but use the [[jet stream]] (bottom) when heading eastwards. The shortest route appears as a curve rather than a straight line because the [[map projection]] does not scale all distances equally compared to the real spherical surface of the Earth.]]
{{main|Geographic distance|geodesic}}

The straight-line distance between two points on the surface of the Earth is not very useful for most purposes, since we cannot tunnel straight through the [[Earth's mantle]].  Instead, one typically measures the shortest path along the [[surface of the Earth]], [[as the crow flies]].  This is approximated mathematically by the [[great-circle distance]] on a sphere.

More generally, the shortest path between two points along a [[surface (mathematics)|curved surface]] is known as a [[geodesic]].  The [[arc length]] of geodesics gives a way of measuring distance from the perspective of an [[ant]] or other flightless creature living on that surface.

===Effects of relativity===
{{main|Distance measure}}
In the [[theory of relativity]], because of phenomena such as [[length contraction]] and the [[relativity of simultaneity]], distances between objects depend on a choice of [[inertial frame of reference]].  On galactic and larger scales, the measurement of distance is also affected by the [[expansion of the universe]].  In practice, a number of [[distance measure]]s are used in [[cosmology]] to quantify such distances.

===Other spatial distances===
[[File:Manhattan distance.svg|thumb|200px|[[Manhattan distance]] on a grid]]
Unusual definitions of distance can be helpful to model certain physical situations, but are also used in theoretical mathematics:
* In practice, one is often interested in the travel distance between two points along roads, rather than as the crow flies.  In a [[grid plan]], the travel distance between street corners is given by the [[Manhattan distance]]: the number of east–west and north–south blocks one must traverse to get between those two points.
* Chessboard distance, formalized as [[Chebyshev distance]], is the minimum number of moves a [[king (chess)|king]] must make on a [[chessboard]] in order to travel between two squares.

==Metaphorical distances==
Many abstract notions of distance used in mathematics, science and engineering represent a degree of difference or separation between similar objects.  This page gives a few examples.

===Statistical distances===
{{main|Statistical distance}}
In [[statistics]] and [[information geometry]], [[statistical distance]]s measure the degree of difference between two [[probability distribution]]s.  There are many kinds of statistical distances, typically formalized as [[divergence (statistics)|divergences]]; these allow a set of probability distributions to be understood as a [[space (mathematics)|geometrical object]] called a [[statistical manifold]].  The most elementary is the [[squared Euclidean distance]], which is minimized by the [[least squares]] method; 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 an example of both an [[f-divergence|''f''-divergence]] and a Bregman divergence (and in fact the only example which is both). Statistical manifolds corresponding to Bregman divergences are [[flat manifold]]s in the corresponding geometry, allowing an analog of the [[Pythagorean theorem]] (which holds 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]] and the [[energy distance]].

===Edit distances===
In [[computer science]], an [[edit distance]] or [[string metric]] between two [[string (computer science)|strings]] measures how different they are. For example, the words "dog" and "dot", which differ by just one letter, are closer than "dog" and "cat", which have no letters in common.  This idea is used in [[spell checker]]s and in [[coding theory]], and is mathematically formalized in a number of different ways, including [[Levenshtein distance]], [[Hamming distance]], [[Lee distance]], and [[Jaro–Winkler distance]].

===Distance in graph theory===
{{main|Distance (graph theory)}}
In a [[graph (discrete mathematics)|graph]], the [[distance (graph theory)|distance]] between two vertices is measured by the length of the shortest [[path (graph theory)|edge path]] between them.  For example, if the graph represents a [[social network]], then the idea of [[six degrees of separation]] can be interpreted mathematically as saying that the distance between any two vertices is at most six.  Similarly, the [[Erdős number]] and the [[Bacon number]]—the number of collaborative relationships away a person is from prolific mathematician [[Paul Erdős]] and actor [[Kevin Bacon]], respectively—are distances in the graphs whose edges represent mathematical or artistic collaborations.

===In the social sciences===
In [[psychology]], [[human geography]], and the [[social science]]s, distance is often theorized not as an objective numerical measurement, but as a qualitative description of a subjective experience.<ref>{{Cite web|title=SOCIAL DISTANCES|url=https://www.hawaii.edu/powerkills/TCH.CHAP16.HTM|access-date=2020-07-20|website=www.hawaii.edu}}</ref>  For example, [[psychological distance]] is "the different ways in which an object might be removed from" the self along dimensions such as "time, space, social distance, and hypotheticality".<ref name=psych>{{cite journal | vauthors = Trope Y, Liberman N | title = Construal-level theory of psychological distance | journal = Psychological Review | volume = 117 | issue = 2 | pages = 440–63 | date = April 2010 | pmid = 20438233 | pmc = 3152826 | doi = 10.1037/a0018963 }}</ref>  In [[sociology]], [[social distance]] describes the separation between individuals or [[social groups]] in [[society]] along dimensions such as [[social class]], [[Race (classification of human beings)|race]]/[[ethnicity]], [[gender]] or [[human sexuality|sexuality]].

==Mathematical formalization==
{{main|Metric space}}
Most of the notions of distance between two points or objects described above are examples of the mathematical idea of a [[metric space|metric]].  A ''metric'' or ''distance function'' is a [[function (mathematics)|function]] {{mvar|d}} which takes pairs of points or objects to [[real numbers]] and satisfies the following rules:
# The distance between an object and itself is always zero.
# The distance between distinct objects is always positive.
# Distance is [[symmetric relation|symmetric]]: the distance from {{mvar|x}} to {{mvar|y}} is always the same as the distance from {{mvar|y}} to {{mvar|x}}.
# Distance satisfies the [[triangle inequality]]: if {{mvar|x}}, {{mvar|y}}, and {{mvar|z}} are three objects, then <math display="block">d(x,z) \leq d(x,y)+d(y,z).</math> This condition can be described informally as "intermediate stops can't speed you up."
As an exception, many of the [[divergence (statistics)|divergence]]s used in statistics are not metrics.

[[File:Distance function animation.gif|thumb|Animation visualizing the function (abs(x)^r + abs(y)^r)^(1/r) for various values of r.]]

==Distance between sets==

[[File:Distance between sets.svg|thumb|The distances between these three sets do not satisfy the triangle inequality:<math display="block">d(A,B)>d(A,C)+d(C,B)</math>]]
There are multiple ways of measuring the physical distance between objects that [[extension (metaphysics)|consist of more than one point]]:
* One may measure the distance between representative points such as the [[center of mass]]; this is used for astronomical distances such as the [[Lunar distance (astronomy)|Earth–Moon distance]].
* One may measure the distance between the closest points of the two objects; in this sense, the [[altitude]] of an airplane or spacecraft is its distance from the Earth.  The same sense of distance is used in Euclidean geometry to define [[distance from a point to a line]], [[distance from a point to a plane]], or, more generally, [[perpendicular distance]] between [[affine subspace]]s.
: Even more generally, this idea can be used to define the distance between two [[subset]]s of a metric space.  The distance between sets {{mvar|A}} and {{mvar|B}} is the [[infimum]] of the distances between any two of their respective points:<math display="block">d(A,B)=\inf_{x\in A, y\in B} d(x,y).</math> This does not define a metric on the set of such subsets: the distance between overlapping sets is zero, and this distance does not satisfy the triangle inequality for any metric space with two or more points (consider the triple of sets consisting of two distinct singletons and their union).
* The [[Hausdorff distance]] between two subsets of a metric space can be thought of as measuring how far they are from perfectly overlapping.  Somewhat more precisely, the Hausdorff distance between {{mvar|A}} and {{mvar|B}} is either the distance from {{mvar|A}} to the farthest point of {{mvar|B}}, or the distance from {{mvar|B}} to the farthest point of {{mvar|A}}, whichever is larger.  (Here "farthest point" must be interpreted as a supremum.)  The Hausdorff distance defines a metric on the set of [[compact space|compact subsets]] of a metric space.

==Related ideas==
{{further|Length}}

The word '''distance''' is also used for related concepts that are not encompassed by the description "a numerical measurement of how far apart points or objects are".

===Distance travelled===
The '''distance travelled''' by an object is the length of a specific path travelled between two points,<ref>{{Cite web|title=What is displacement? (article)|url=https://www.khanacademy.org/science/physics/one-dimensional-motion/displacement-velocity-time/a/what-is-displacement|access-date=2020-07-20|website=Khan Academy|language=en}}</ref> such as the distance walked while navigating a [[maze]].  This can even be a '''closed distance''' along a [[closed curve]] which starts and ends at the same point, such as a ball thrown straight up, or the Earth when it completes one [[orbit]].  This is formalized mathematically as the [[arc length]] of the curve.

The distance travelled may also be [[sign (mathematics)|signed]]: a "forward" distance is positive and a "backward" distance is negative.

'''Circular distance''' is the distance traveled by a point on the circumference of a [[wheel]], which can be useful to consider when designing vehicles or mechanical gears (see also [[odometry]]). The circumference of the wheel is {{math|2&pi; &times; radius}}; if the radius is&nbsp;1, each revolution of the wheel causes a vehicle to travel {{math|2&pi;}} radians.

===Displacement and directed distance{{anchor|Displacement|Directed distance}}===
[[File:Distancedisplacement.svg|thumb|Distance along a path compared with displacement.  The Euclidean distance is the length of the displacement vector.]]
{{main|Displacement (vector)}}
The [[displacement (vector)|displacement]] in classical physics measures the change in position of an object during an interval of time.  While distance is a [[scalar (physics)|scalar]] quantity, or a [[Magnitude (mathematics)|magnitude]], displacement is a [[Vector (geometry)|vector]] quantity with both magnitude and [[Direction (geometry, geography)|direction]].  In general, the vector measuring the difference between two locations (the [[relative position]]) is sometimes called the '''directed distance'''.<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 |access-date=18 September 2018 |archive-url=https://web.archive.org/web/20161110044317/http://www.ittc.ku.edu/~jstiles/220/handouts/The%20Directed%20Distance.pdf |archive-date=10 November 2016}}</ref>  For example, the directed distance from the [[New York Public Library Main Branch|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&nbsp;km

===Signed distance===
{{excerpt|Signed distance function|files=0}}

== See also ==
{{wikiquote}}
{{div col|colwidth=22em}}
*[[Absolute difference]]
*[[Astronomical system of units]]
*[[Color difference]]
*[[Closeness (mathematics)]]
*[[Distance geometry problem]]
*[[Dijkstra's algorithm]]
*[[Distance matrix]]
*[[Distance set]]
*[[Engineering tolerance]]
*[[Multiplicative distance]]
*[[Optical path length]]
*[[Orders of magnitude (length)]]
*[[Proper length]]
*[[Proxemics]] &ndash; physical distance between people
*[[Signed distance function]]
*[[Similarity measure]]
*[[Social distancing]]
*[[Vertical distance]]
{{div col end}}

== Library support ==

* [[Python (programming language)]]
** [https://docs.scipy.org/doc/scipy/reference/spatial.distance.html SciPy] -Distance computations (<code>scipy.spatial.distance</code>)
*[[Julia (programming language)]]
**[https://github.com/JuliaStats/Distances.jl Julia Statistics Distance] -A Julia package for evaluating distances (metrics) between vectors.

== References == 
{{Reflist}}

== Bibliography ==
* {{cite book | vauthors = [[Elena Deza|Deza E]], Deza M |author2-link=Michel Deza|title=Dictionary of Distances|year=2006|publisher=Elsevier|isbn=0-444-52087-2}}

{{Kinematics}}
{{Authority control}}

[[Category:Distance| ]]