Editing Euclidean distance (section)

== 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, as the square root does not change the order (<math>d_1^2 > d_2^2</math> if and only if <math>d_1 > d_2</math>). 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 /> For instance, the [[Euclidean minimum spanning tree]] can be determined using only the ordering between distances, and not their numeric values. Comparing squared distances produces the same result but avoids an unnecessary square-root calculation and sidesteps issues of numerical precision.<ref>{{citation
 | last = Yao | first = Andrew Chi Chih | author-link = Andrew Yao
 | doi = 10.1137/0211059
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 677663
 | pages = 721–736
 | title = On constructing minimum spanning trees in {{mvar|k}}-dimensional spaces and related problems
 | volume = 11
 | year = 1982}}</ref> As an equation, the squared distance 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_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> and as the simplest form of [[divergence (statistics)|divergence]] to compare [[probability distribution]]s.<ref>{{citation
 | last = Csiszár | first = I. | author-link = Imre Csiszár
 | doi = 10.1214/aop/1176996454
 | journal = [[Annals of Probability]]
 | jstor = 2959270
 | mr = 365798
 | pages = 146–158
 | title = {{mvar|I}}-divergence geometry of probability distributions and minimization problems
 | volume = 3
 | year = 1975| issue = 1 | doi-access = free
 }}</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|isbn=978-1-4419-4974-5 }}</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>