Distance Between Two Points - Revision history

Lila: /* Squared Euclidean distance */

2021-10-26T19:33:49Z

Squared Euclidean distance

Lila: /* Squared Euclidean distance */

2021-10-26T19:32:51Z

Squared Euclidean distance

Lila at 19:27, 26 October 2021

2021-10-26T19:27:13Z

Lila at 19:26, 26 October 2021

2021-10-26T19:26:08Z

Show changes

Lila: Lila moved page Distance Between Two Points in the Real Numbers to Distance Between Two Points

2021-10-25T19:49:00Z

Lila moved page Distance Between Two Points in the Real Numbers to Distance Between Two Points

Lila: Created page with "Using the Pythagorean theorem to compute two-dimensional Euclidean distance In mathematics, the '''Euclidean distance..."

2021-10-25T19:38:10Z

Created page with "thumb|upright=1.35|Using the Pythagorean theorem to compute two-dimensional Euclidean distance In mathematics, the '''Euclidean distance..."

New page

[[File:Euclidean distance 2d.svg|thumb|upright=1.35|Using the Pythagorean theorem to compute two-dimensional Euclidean distance]]
In [[mathematics]], the '''Euclidean distance''' between two points in [[Euclidean space]] is the length of a [[line segment]] between the two points.
It can be calculated from the [[Cartesian coordinate]]s of the points using the [[Pythagorean theorem]], therefore occasionally being called the '''Pythagorean distance'''. These names come from the ancient Greek mathematicians [[Euclid]] and [[Pythagoras]], although Euclid did not represent distances as numbers, and the connection from the Pythagorean theorem to distance calculation was not made until the 18th century.

The distance between two objects that are not points is usually defined to be the smallest distance among pairs of points from the two objects. Formulas are known for computing distances between different types of objects, such as the [[distance from a point to a line]]. In advanced mathematics, the concept of distance has been generalized to abstract [[metric space]]s, and other distances than Euclidean have been studied. In some applications in statistics and optimization, the square of the Euclidean distance is used instead of the distance itself.

== Distance formulas ==
=== One dimension ===
The distance between any two points on the [[real line]] is the [[absolute value]] of the numerical difference of their coordinates. Thus if <math>p</math> and <math>q</math> are two points on the real line, then the distance between them is given by:<ref name=smith>{{citation|title=Precalculus: A Functional Approach to Graphing and Problem Solving|first=Karl|last=Smith|publisher=Jones & Bartlett Publishers|year=2013|isbn=978-0-7637-5177-7|page=8|url=https://books.google.com/books?id=ZUJbVQN37bIC&pg=PA8}}</ref>
<math display=block>d(p,q) = |p-q|.</math>
A more complicated formula, giving the same value, but generalizing more readily to higher dimensions, is:<ref name=smith />
<math display=block>d(p,q) = \sqrt{(p-q)^2}.</math>
In this formula, [[square (algebra)|squaring]] and then taking the [[square root]] leaves any positive number unchanged, but replaces any negative number by its absolute value.<ref name=smith />

=== Two dimensions ===
In the [[Euclidean plane]], let point <math>p</math> have [[Cartesian coordinates]] <math>(p_1,p_2)</math> and let point <math>q</math> have coordinates <math>(q_1,q_2)</math>. Then the distance between <math>p</math> and <math>q</math> is given by:<ref name=cohen>{{citation|title=Precalculus: A Problems-Oriented Approach|first=David|last=Cohen|edition=6th|publisher=Cengage Learning|year=2004|isbn=978-0-534-40212-9|page=698|url=https://books.google.com/books?id=_6ukev29gmgC&pg=PA698}}</ref>
<math display=block>d(p,q) = \sqrt{(q_1-p_1)^2 + (q_2-p_2)^2}.</math>
This can be seen by applying the [[Pythagorean theorem]] to a [[right triangle]] with horizontal and vertical sides, having the line segment from <math>p</math> to <math>q</math> as its hypotenuse. The two squared formulas inside the square root give the areas of squares on the horizontal and vertical sides, and the outer square root converts the area of the square on the hypotenuse into the length of the hypotenuse.<ref>{{citation|title=College Trigonometry|first1=Richard N.|last1=Aufmann|first2=Vernon C.|last2=Barker|first3=Richard D.|last3=Nation|edition=6th|publisher=Cengage Learning|year=2007|isbn=978-1-111-80864-8|page=17|url=https://books.google.com/books?id=kZ8HAAAAQBAJ&pg=PA17}}</ref>

It is also possible to compute the distance for points given by [[Polar coordinate system|polar coordinates]]. If the polar coordinates of <math>p</math> are <math>(r,\theta)</math> and the polar coordinates of <math>q</math> are <math>(s,\psi)</math>, then their distance is<ref name=cohen /> given by the [[law of cosines]]:
<math display=block>d(p,q)=\sqrt{r^2 + s^2 - 2rs\cos(\theta-\psi)}.</math>

When <math>p</math> and <math>q</math> are expressed as [[complex number]]s in the [[complex plane]], the same formula for one-dimensional points expressed as real numbers can be used:<ref>{{citation|title=Complex Numbers from A to ... Z|first1=Titu|last1=Andreescu|first2=Dorin|last2=Andrica|publisher=Birkhäuser|year=2014|edition=2nd|isbn=978-0-8176-8415-0|contribution=3.1.1 The Distance Between Two Points|pages=57–58}}</ref>
<math display=block>d(p,q)=|p-q|.</math>

=== Higher dimensions ===
[[File:Euclidean distance 3d 2 cropped.png|thumb|upright=1.2|Deriving the <math>n</math>-dimensional Euclidean distance formula by repeatedly applying the Pythagorean theorem]]
In three dimensions, for points given by their Cartesian coordinates, the distance is
<math display=block>d(p,q)=\sqrt{(p_1-q_1)^2 + (p_2-q_2)^2 + (p_3-q_3)^2}.</math>
In general, for points given by Cartesian coordinates in <math>n</math>-dimensional Euclidean space, the distance is<ref>{{citation|title=Geometry: The Language of Space and Form|series=Facts on File math library|first=John|last=Tabak|publisher=Infobase Publishing|year=2014|isbn=978-0-8160-6876-0|page=150|url=https://books.google.com/books?id=r0HuPiexnYwC&pg=PA150}}</ref>

<math display=block>d(p,q) = \sqrt{(p_1- q_1)^2 + (p_2 - q_2)^2+\cdots+(p_i - q_i)^2+\cdots+(p_n - q_n)^2}.</math>

=== Objects other than points ===
For pairs of objects that are not both points, the distance can most simply be defined as the smallest distance between any two points from the two objects, although more complicated generalizations from points to sets such as [[Hausdorff distance]] are also commonly used.<ref>{{citation|title=Metric Spaces|series=Springer Undergraduate Mathematics Series|first=Mícheál|last=Ó Searcóid|publisher=Springer|year=2006|isbn=978-1-84628-627-8|contribution=2.7 Distances from Sets to Sets|pages=29–30|url=https://books.google.com/books?id=aP37I4QWFRcC&pg=PA29}}</ref> Formulas for computing distances between different types of objects include:
*The [[distance from a point to a line]], in the Euclidean plane<ref name=baljer>{{citation|last1=Ballantine|first1=J. P.|last2=Jerbert|first2=A. R.|date=April 1952|department=Classroom notes|doi=10.2307/2306514|issue=4|journal=[[American Mathematical Monthly]]|jstor=2306514|pages=242–243|title=Distance from a line, or plane, to a point|volume=59}}</ref>
*The [[distance from a point to a plane]] in three-dimensional Euclidean space<ref name=baljer />
*The [[Skew lines#Distance|distance between two lines]] in three-dimensional Euclidean space<ref>{{citation|last=Bell|first=Robert J. T.|author-link=Robert J. T. Bell|edition=2nd|contribution=49. The shortest distance between two lines|contribution-url=https://archive.org/details/elementarytreati00bell/page/56/mode/2up|pages=57–61|publisher=Macmillan|title=An Elementary Treatise on Coordinate Geometry of Three Dimensions|year=1914}}</ref>

== Properties ==
The Euclidean distance is the prototypical example of the distance in a [[metric space]],<ref>{{citation|title=Easy as π?: An Introduction to Higher Mathematics|first=Oleg A.|last=Ivanov|publisher=Springer|year=2013|isbn=978-1-4612-0553-1|page=140|url=https://books.google.com/books?id=reALBwAAQBAJ&pg=PA140}}</ref> and obeys all the defining properties of a metric space:<ref name=strichartz>{{citation|title=The Way of Analysis|first=Robert S.|last=Strichartz|publisher=Jones & Bartlett Learning|year=2000|isbn=978-0-7637-1497-0|page=357|url=https://books.google.com/books?id=Yix09oVvI1IC&pg=PA357}}</ref>
*It is ''symmetric'', meaning that for all points <math>p</math> and <math>q</math>, <math>d(p,q)=d(q,p)</math>. That is (unlike road distance with one-way streets) the distance between two points does not depend on which of the two points is the start and which is the destination.<ref name=strichartz />
*It is ''positive'', meaning that the distance between every two distinct points is a [[positive number]], while the distance from any point to itself is zero.<ref name=strichartz />
*It obeys the [[triangle inequality]]: for every three points <math>p</math>, <math>q</math>, and <math>r</math>, <math>d(p,q)+d(q,r)\ge d(p,r)</math>. Intuitively, traveling from <math>p</math> to <math>r</math> via <math>q</math> cannot be any shorter than traveling directly from <math>p</math> to <math>r</math>.<ref name=strichartz />

Another property, [[Ptolemy's inequality]], concerns the Euclidean distances among four points <math>p</math>, <math>q</math>, <math>r</math>, and <math>s</math>. It states that
<math display=block>d(p,q)\cdot d(r,s)+d(q,r)\cdot d(p,s)\ge d(p,r)\cdot d(q,s).</math>
For points in the plane, this can be rephrased as stating that for every [[quadrilateral]], the products of opposite sides of the quadrilateral sum to at least as large a number as the product of its diagonals. However, Ptolemy's inequality applies more generally to points in Euclidean spaces of any dimension, no matter how they are arranged.<ref>{{citation|title=Rays, Waves, and Scattering: Topics in Classical Mathematical Physics|series=Princeton Series in Applied Mathematics|first=John A.|last=Adam|publisher=Princeton University Press|year=2017|isbn=978-1-4008-8540-4|pages=26–27|chapter-url=https://books.google.com/books?id=DnygDgAAQBAJ&pg=PA26|chapter=Chapter 2. Introduction to the "Physics" of Rays|doi=10.1515/9781400885404-004}}</ref> Euclidean [[distance geometry]] studies properties of Euclidean distance such as Ptolemy's inequality, and their application in testing whether given sets of distances come from points in a Euclidean space.<ref>{{citation|title=Euclidean Distance Geometry: An Introduction|series=Springer Undergraduate Texts in Mathematics and Technology|first1=Leo|last1=Liberti|first2=Carlile|last2=Lavor|publisher=Springer|year=2017|isbn=978-3-319-60792-4|page=xi|url=https://books.google.com/books?id=jOQ2DwAAQBAJ&pg=PP10}}</ref>

== Squared Euclidean distance ==
{{multiple image
|image1=3d-function-5.svg
|caption1=A [[cone]], the [[Graph of a function|graph]] of Euclidean distance from the origin in the plane
|image2=3d-function-2.svg
|caption2=A [[paraboloid]], the graph of squared Euclidean distance from the origin
}}
In many applications, and in particular when comparing distances, it may be more convenient to omit the final square root in the calculation of Euclidean distances. The value resulting from this omission is the [[Square (algebra)|square]] of the Euclidean distance, and is called the '''squared Euclidean distance'''.<ref name=spencer /> As an equation, it can be expressed as a [[sum of squares]]:

<math display=block>d^2(p,q) = (p_1 - q_1)^2 + (p_2 - q_2)^2+\cdots+(p_i - q_i)^2+\cdots+(p_n - q_n)^2.</math>

Beyond its application to distance comparison, squared Euclidean distance is of central importance in [[statistics]], where it is used in the method of [[least squares]], a standard method of fitting statistical estimates to data by minimizing the average of the squared distances between observed and estimated values.<ref>{{citation|title=Basic Statistics in Multivariate Analysis|series=Pocket Guide to Social Work Research Methods|first1=Karen A.|last1=Randolph|author1-link=Karen Randolph|first2=Laura L.|last2=Myers|publisher=Oxford University Press|year=2013|isbn=978-0-19-976404-4|page=116|url=https://books.google.com/books?id=WgSnudjEsrMC&pg=PA116}}</ref> The addition of squared distances to each other, as is done in least squares fitting, corresponds to an operation on (unsquared) distances called [[Pythagorean addition]].<ref>{{citation |author=Moler, Cleve and Donald Morrison |title=Replacing Square Roots by Pythagorean Sums |journal=IBM Journal of Research and Development |volume=27 |issue=6 |pages=577–581 |year=1983 |url=http://www.research.ibm.com/journal/rd/276/ibmrd2706P.pdf |doi=10.1147/rd.276.0577 | citeseerx = 10.1.1.90.5651 }}</ref> In [[cluster analysis]], squared distances can be used to strengthen the effect of longer distances.<ref name=spencer>{{citation|title=Essentials of Multivariate Data Analysis|first=Neil H.|last=Spencer|publisher=CRC Press|year=2013|isbn=978-1-4665-8479-2|contribution=5.4.5 Squared Euclidean Distances|page=95|contribution-url=https://books.google.com/books?id=EG3SBQAAQBAJ&pg=PA95}}</ref>

Squared Euclidean distance does not form a metric space, as it does not satisfy the triangle inequality.<ref>{{citation|last1=Mielke|first1=Paul W.|last2=Berry|first2=Kenneth J.|editor1-last=Brown|editor1-first=Timothy J.|editor2-last=Mielke|editor2-first=Paul W. Jr.|contribution=Euclidean distance based permutation methods in atmospheric science|doi=10.1007/978-1-4757-6581-6_2|pages=7–27|publisher=Springer|title=Statistical Mining and Data Visualization in Atmospheric Sciences|year=2000}}</ref> However it is a smooth, strictly [[convex function]] of the two points, unlike the distance, which is non-smooth (near pairs of equal points) and convex but not strictly convex. The squared distance is thus preferred in [[optimization theory]], since it allows [[convex analysis]] to be used. Since squaring is a [[monotonic function]] of non-negative values, minimizing squared distance is equivalent to minimizing the Euclidean distance, so the optimization problem is equivalent in terms of either, but easier to solve using squared distance.<ref>{{citation|title=Maxima and Minima with Applications: Practical Optimization and Duality|volume=51|series=Wiley Series in Discrete Mathematics and Optimization|first=Wilfred|last=Kaplan|publisher=John Wiley & Sons|year=2011|isbn=978-1-118-03104-9|page=61|url=https://books.google.com/books?id=bAo6KNZcUP0C&pg=PA61}}</ref>

The collection of all squared distances between pairs of points from a finite set may be stored in a [[Euclidean distance matrix]], and is used in this form in distance geometry.<ref>{{citation|title=Euclidean Distance Matrices and Their Applications in Rigidity Theory|first=Abdo Y.|last=Alfakih|publisher=Springer|year=2018|isbn=978-3-319-97846-8|page=51|url=https://books.google.com/books?id=woJyDwAAQBAJ&pg=PA51}}</ref>

== Generalizations ==
In more advanced areas of mathematics, when viewing Euclidean space as a [[vector space]], its distance is associated with a [[Norm (mathematics)|norm]] called the [[Norm (mathematics)#Euclidean norm|Euclidean norm]], defined as the distance of each vector from the [[Origin (mathematics)|origin]]. One of the important properties of this norm, relative to other norms, is that it remains unchanged under arbitrary rotations of space around the origin.<ref>{{citation|title=Relativistic Celestial Mechanics of the Solar System|first1=Sergei|last1=Kopeikin|first2=Michael|last2=Efroimsky|first3=George|last3=Kaplan|publisher=John Wiley & Sons|year=2011|isbn=978-3-527-63457-6|page=106|url=https://books.google.com/books?id=uN5_DQWSR14C&pg=PA106}}</ref> By [[Dvoretzky's theorem]], every finite-dimensional [[normed vector space]] has a high-dimensional subspace on which the norm is approximately Euclidean; the Euclidean norm is the
only norm with this property.<ref>{{citation|last=Matoušek|first=Jiří|author-link=Jiří Matoušek (mathematician)|isbn=978-0-387-95373-1|page=349|publisher=Springer|series=[[Graduate Texts in Mathematics]]|title=Lectures on Discrete Geometry|url=https://books.google.com/books?id=K0fhBwAAQBAJ&pg=PA349|year=2002}}</ref> It can be extended to infinite-dimensional vector spaces as the [[Lp space|L<sup>2</sup> norm]] or L<sup>2</sup> distance.<ref>{{citation|title=Linear and Nonlinear Functional Analysis with Applications|first=Philippe G.|last=Ciarlet|publisher=Society for Industrial and Applied Mathematics|year=2013|isbn=978-1-61197-258-0|page=173|url=https://books.google.com/books?id=AUlWAQAAQBAJ&pg=PA173}}</ref>

Other common distances on Euclidean spaces and low-dimensional vector spaces include:<ref>{{citation|last=Klamroth|first=Kathrin|author-link=Kathrin Klamroth|contribution=Section 1.1: Norms and Metrics|doi=10.1007/0-387-22707-5_1|pages=4–6|publisher=Springer|series=Springer Series in Operations Research|title=Single-Facility Location Problems with Barriers|year=2002}}</ref>
*[[Chebyshev distance]], which measures distance assuming only the most significant dimension is relevant.
*[[Manhattan distance]], which measures distance following only axis-aligned directions.
*[[Minkowski distance]], a generalization that unifies Euclidean distance, Manhattan distance, and Chebyshev distance.

For points on surfaces in three dimensions, the Euclidean distance should be distinguished from the [[geodesic]] distance, the length of a shortest curve that belongs to the surface. In particular, for measuring great-circle distances on the earth or other spherical or near-spherical surfaces, distances that have been used include the [[haversine distance]] giving great-circle distances between two points on a sphere from their longitudes and latitudes, and [[Vincenty's formulae]] also known as "Vincent distance" for distance on a spheroid.<ref>{{citation|title=Computing in Geographic Information Systems|first=Narayan|last=Panigrahi|publisher=CRC Press|year=2014|isbn=978-1-4822-2314-9|contribution=12.2.4 Haversine Formula and 12.2.5 Vincenty's Formula|pages=212–214|url=https://books.google.com/books?id=kjj6AwAAQBAJ&pg=PA212}}</ref>

==Licensing==
Content obtained and/or adapted from:
* [https://en.wikipedia.org/wiki/Euclidean_distance Euclidean distance, Wikipedia] under a CC BY-SA license

@@ Line 49: / Line 49: @@
 == Squared Euclidean distance ==
-[[Image:3d-function-5.svg|A cone, the graph of Euclidean distance from the origin in the plane]]
+[[Image:3d-function-5.svg|frame|A cone, the graph of Euclidean distance from the origin in the plane]]
-[[Image:3d-function-2.svg|A paraboloid, the graph of squared Euclidean distance from the origin]]
+[[Image:3d-function-2.svg|frame|A paraboloid, the graph of squared Euclidean distance from the origin]]
 In many applications, and in particular when comparing distances, it may be more convenient to omit the final square root in the calculation of Euclidean distances. The value resulting from this omission is the square of the Euclidean distance, and is called the '''squared Euclidean distance'''. As an equation, it can be expressed as a sum of squares:

@@ Line 49: / Line 49: @@
 == Squared Euclidean distance ==
-{{multiple image
+[[Image:3d-function-5.svg|A cone, the graph of Euclidean distance from the origin in the plane]]
-|image1=3d-function-5.svg
+[[Image:3d-function-2.svg|A paraboloid, the graph of squared Euclidean distance from the origin]]
-|caption1=A cone, the graph of Euclidean distance from the origin in the plane
 In many applications, and in particular when comparing distances, it may be more convenient to omit the final square root in the calculation of Euclidean distances. The value resulting from this omission is the square of the Euclidean distance, and is called the '''squared Euclidean distance'''. As an equation, it can be expressed as a sum of squares:

@@ Line 9: / Line 9: @@
 The distance between any two points on the real line is the absolute value of the numerical difference of their coordinates. Thus if <math>p</math> and <math>q</math> are two points on the real line, then the distance between them is given by:
 <math display=block>d(p,q) = |p-q|.</math>
-A more complicated formula, giving the same value, but generalizing more readily to higher dimensions, is:<ref name=smith />
+A more complicated formula, giving the same value, but generalizing more readily to higher dimensions, is:
 <math display=block>d(p,q) = \sqrt{(p-q)^2}.</math>
-In this formula, squaring and then taking the square root leaves any positive number unchanged, but replaces any negative number by its absolute value.<ref name=smith />
+In this formula, squaring and then taking the square root leaves any positive number unchanged, but replaces any negative number by its absolute value.
 === Two dimensions ===
-In the Euclidean plane, let point <math>p</math> have Cartesian coordinates <math>(p_1,p_2)</math> and let point <math>q</math> have coordinates <math>(q_1,q_2)</math>. Then the distance between <math>p</math> and <math>q</math> is given by:<ref name=cohen>{{citation|title=Precalculus: A Problems-Oriented Approach|first=David|last=Cohen|edition=6th|publisher=Cengage Learning|year=2004|isbn=978-0-534-40212-9|page=698|url=https://books.google.com/books?id=_6ukev29gmgC&pg=PA698}}</ref>
+In the Euclidean plane, let point <math>p</math> have Cartesian coordinates <math>(p_1,p_2)</math> and let point <math>q</math> have coordinates <math>(q_1,q_2)</math>. Then the distance between <math>p</math> and <math>q</math> is given by:
 <math display=block>d(p,q) = \sqrt{(q_1-p_1)^2 + (q_2-p_2)^2}.</math>
 This can be seen by applying the Pythagorean theorem to a right triangle with horizontal and vertical sides, having the line segment from <math>p</math> to <math>q</math> as its hypotenuse. The two squared formulas inside the square root give the areas of squares on the horizontal and vertical sides, and the outer square root converts the area of the square on the hypotenuse into the length of the hypotenuse.
-It is also possible to compute the distance for points given by polar coordinates. If the polar coordinates of <math>p</math> are <math>(r,\theta)</math> and the polar coordinates of <math>q</math> are <math>(s,\psi)</math>, then their distance is<ref name=cohen /> given by the law of cosines:
+It is also possible to compute the distance for points given by polar coordinates. If the polar coordinates of <math>p</math> are <math>(r,\theta)</math> and the polar coordinates of <math>q</math> are <math>(s,\psi)</math>, then their distance is given by the law of cosines:
 <math display=block>d(p,q)=\sqrt{r^2 + s^2 - 2rs\cos(\theta-\psi)}.</math>
@@ Line 28: / Line 28: @@
 In three dimensions, for points given by their Cartesian coordinates, the distance is
 <math display=block>d(p,q)=\sqrt{(p_1-q_1)^2 + (p_2-q_2)^2 + (p_3-q_3)^2}.</math>
-In general, for points given by Cartesian coordinates in <math>n</math>-dimensional Euclidean space, the distance is<ref>{{citation|title=Geometry: The Language of Space and Form|series=Facts on File math library|first=John|last=Tabak|publisher=Infobase Publishing|year=2014|isbn=978-0-8160-6876-0|page=150|url=https://books.google.com/books?id=r0HuPiexnYwC&pg=PA150}}</ref>
+In general, for points given by Cartesian coordinates in <math>n</math>-dimensional Euclidean space, the distance is
 <math display=block>d(p,q) = \sqrt{(p_1- q_1)^2 + (p_2 - q_2)^2+\cdots+(p_i - q_i)^2+\cdots+(p_n - q_n)^2}.</math>
@@ Line 55: / Line 55: @@
 |caption2=A paraboloid, the graph of squared Euclidean distance from the origin
 }}
-In many applications, and in particular when comparing distances, it may be more convenient to omit the final square root in the calculation of Euclidean distances. The value resulting from this omission is the square of the Euclidean distance, and is called the '''squared Euclidean distance'''.<ref name=spencer /> As an equation, it can be expressed as a sum of squares:
+In many applications, and in particular when comparing distances, it may be more convenient to omit the final square root in the calculation of Euclidean distances. The value resulting from this omission is the square of the Euclidean distance, and is called the '''squared Euclidean distance'''. As an equation, it can be expressed as a sum of squares:
 <math display=block>d^2(p,q) = (p_1 - q_1)^2 + (p_2 - q_2)^2+\cdots+(p_i - q_i)^2+\cdots+(p_n - q_n)^2.</math>

← Older revision	Revision as of 19:49, 25 October 2021
(No difference)