Euclidean distance

Using the Pythagorean theorem to compute two-dimensional Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is a number, the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem. It is occasionally called the Pythagorean distance, especially as a way to contrast three-dimensional Euclidean distance with geodesic distance, the length of a shortest curve along some surface such as that of the earth.

The distance between two objects that are not points is usually defined to be the smallest distance between any two points from the two objects. Various formulas are known for computing distances between different types of objects, such as the distance from a point to a line.

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 $p$ and $q$ are two points on the real line, then the distance between them is given by:

$d(p,q)=|p-q|.$

A more complicated formula, giving the same value, but generalizing more readily to higher dimensions, is:

$d(p,q)={\sqrt {(p-q)^{2}}}.$

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 $p$ have Cartesian coordinates $(p_{1},p_{2})$ and let point $q$ have coordinates $(q_{1},q_{2})$. Then the distance between $p$ and $q$ is given by:

$d(p,q)={\sqrt {(p_{1}-q_{1})^{2}+(p_{2}-q_{2})^{2}}}.$

This can be seen by applying the Pythagorean theorem to a right triangle with horizontal and vertical sides, having the line segment from $p$ to $q$ 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 $p$ are $(r,\theta )$ and the polar coordinates of $q$ are $(s,\psi )$, then their distance is

$d(p,q)={\sqrt {r^{2}+s^{2}-2rs\cos(\theta -\psi )}}.$

When $p$ and $q$ are expressed as complex numbers in the complex plane, the same formula used for one-dimensional points expressed as real numbers can be used:

$d(p,q)=|p-q|.$

Higher dimensions

Deriving the $n$-dimensional Euclidean distance formula by repeatedly applying the Pythagorean theorem

In general, for points given by Cartesian coordinates in $n$-dimensional Euclidean space, the distance is

$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}}}.$

Other objects than points

For pairs of objects that are not both points, the distance can be defined as the smallest distance between any two points from the two objects. Formulas for computing distances between different types of objects include:

• The distance from a point to a line, in the Euclidean plane
• The distance from a point to a plane in three-dimensional Euclidean space
• The distance between two lines in three-dimensional Euclidean space

Squared Euclidean distance

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:

$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}.$

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 linear functions to data by finding the function that minimizes the average of the (one-dimensional) squared distances between the observed function values and the values predicted by the fit. In cluster analysis, squared distances can be used to strengthen the effect of longer distances.

Squared Euclidean distance is not a metric, as it does not satisfy the triangle inequality. However it is a smooth, strictly convex function of the two points, unlike the distance, which is non-smooth for 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.

In the terminology of rational trigonometry, squared Euclidean distance is also called "quadrance".

Generalizations

In more advanced areas of mathematics, Euclidean space and its distance provides a standard example of a metric space, called the Euclidean metric. When viewing Euclidean space as a vector space, its distance is associated with a norm called the Euclidean norm. It can be extended to more general vector spaces as the L² norm or L² distance.

Other common distances on Euclidean spaces and low-dimensional vector spaces include:

• 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 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.

History

Euclidean distance is the distance in Euclidean space; both concepts are named after ancient Greek mathematician Euclid, whose Elements became a standard textbook in geometry for many centuries. Concepts of length and distance are widespread across cultures, can be dated to the earliest surviving "protoliterate" bureaucratic documents from Sumer in the fourth millenium BC (far before Euclid), and have been hypothesized to develop in children earlier than the related concepts of speed and time. But the notion of a distance, as a number defined from two points, does not actually appear in Euclid's Elements. Instead, Euclid approaches this concept implicitly, through the congruence of line segments, through the comparison of lengths of line segments, and through the concept of proportionality.

The Pythagorean theorem is also ancient, but it only took its central role in the measurement of distances with the invention of Cartesian coordinates by René Descartes in 1637. And although accurate measurements of long distances on the earth's surface, which are not Euclidean, had again been studied in many cultures since ancient times (see history of geodesy), the idea that Euclidean distance might not be the only way of measuring distances between points in mathematical spaces came even later, with the 19th-century formulation of non-Euclidean geometry. The definition of the Euclidean norm and Euclidean distance for geometries of more than three dimensions also first appeared in the 19th century, in the work of Augustin-Louis Cauchy.

See also

• Euclidean distance matrix
• Mahalanobis distance measures distance between a point and a distribution.
• Pythagorean addition
• Sequential euclidean distance transforms