Euclidean distance

Last updated

Using the Pythagorean theorem to compute two-dimensional Euclidean distance Euclidean distance 2d.svg
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 the line segment between them. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, and therefore is occasionally called the Pythagorean distance.

Contents

These names come from the ancient Greek mathematicians Euclid and Pythagoras. In the Greek deductive geometry exemplified by Euclid's Elements, distances were not represented as numbers but line segments of the same length, which were considered "equal". The notion of distance is inherent in the compass tool used to draw a circle, whose points all have the same distance from a common center point. 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 spaces, 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, their absolute difference. Thus if and are two points on the real line, then the distance between them is given by: [1]

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

In this formula, squaring and then taking the square root leaves any positive number unchanged, but replaces any negative number by its absolute value. [1]

Two dimensions

In the Euclidean plane, let point have Cartesian coordinates and let point have coordinates . Then the distance between and is given by: [2]

This can be seen by applying the Pythagorean theorem to a right triangle with horizontal and vertical sides, having the line segment from to 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. [3]

It is also possible to compute the distance for points given by polar coordinates. If the polar coordinates of are and the polar coordinates of are , then their distance is [2] given by the law of cosines:

When and are expressed as complex numbers in the complex plane, the same formula for one-dimensional points expressed as real numbers can be used, although here the absolute value sign indicates the complex norm: [4]

Higher dimensions

Deriving the
n
{\displaystyle n}
-dimensional Euclidean distance formula by repeatedly applying the Pythagorean theorem Euclidean distance 3d 2 cropped.png
Deriving the -dimensional Euclidean distance formula by repeatedly applying the Pythagorean theorem

In three dimensions, for points given by their Cartesian coordinates, the distance is

In general, for points given by Cartesian coordinates in -dimensional Euclidean space, the distance is [5]

The Euclidean distance may also be expressed more compactly in terms of the Euclidean norm of the Euclidean vector difference:

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. [6] Formulas for computing distances between different types of objects include:

The distance from a point to a curve can be used to define its parallel curve, another curve all of whose points have the same distance to the given curve. [9]

Properties

The Euclidean distance is the prototypical example of the distance in a metric space, [10] and obeys all the defining properties of a metric space: [11]

Another property, Ptolemy's inequality, concerns the Euclidean distances among four points , , , and . It states that

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. [12] For points in metric spaces that are not Euclidean spaces, this inequality may not be true. 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. [13]

According to the Beckman–Quarles theorem, any transformation of the Euclidean plane or of a higher-dimensional Euclidean space that preserves unit distances must be an isometry, preserving all distances. [14]

Squared Euclidean distance

3d-function-5.svg
A cone, the graph of Euclidean distance from the origin in the plane
3d-function-2.svg
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 ( if and only if ). The value resulting from this omission is the square of the Euclidean distance, and is called the squared Euclidean distance. [15] 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. [16] As an equation, the squared distance can be expressed as a sum of squares:

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, [17] and as the simplest form of divergence to compare probability distributions. [18] 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. [19] In cluster analysis, squared distances can be used to strengthen the effect of longer distances. [15]

Squared Euclidean distance does not form a metric space, as it does not satisfy the triangle inequality. [20] 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. [21]

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. [22]

Generalizations

In more advanced areas of mathematics, when viewing Euclidean space as a vector space, its distance is associated with a norm called the Euclidean norm, defined as the distance of each vector from the 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. [23] 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. [24] It can be extended to infinite-dimensional vector spaces as the L2 norm or L2 distance. [25] The Euclidean distance gives Euclidean space the structure of a topological space, the Euclidean topology, with the open balls (subsets of points at less than a given distance from a given point) as its neighborhoods. [26]

Comparison of Chebyshev, Euclidean and taxicab distances for the hypotenuse of a 3-4-5 triangle on a chessboard Minkowski distance examples.svg
Comparison of Chebyshev, Euclidean and taxicab distances for the hypotenuse of a 3-4-5 triangle on a chessboard

Other common distances in real coordinate spaces and function spaces: [27]

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. [28]

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. [29] Concepts of length and distance are widespread across cultures, can be dated to the earliest surviving "protoliterate" bureaucratic documents from Sumer in the fourth millennium BC (far before Euclid), [30] and have been hypothesized to develop in children earlier than the related concepts of speed and time. [31] 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. [32]

The Pythagorean theorem is also ancient, but it could only take its central role in the measurement of distances after the invention of Cartesian coordinates by René Descartes in 1637. The distance formula itself was first published in 1731 by Alexis Clairaut. [33] Because of this formula, Euclidean distance is also sometimes called Pythagorean distance. [34] 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. [35] 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. [36]

Related Research Articles

In mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry using a coordinate system. This contrasts with synthetic geometry.

<span class="mw-page-title-main">Euclidean geometry</span> Mathematical model of the physical space

Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry, Elements. Euclid's approach consists in assuming a small set of intuitively appealing axioms (postulates) and deducing many other propositions (theorems) from these. Although many of Euclid's results had been stated earlier, Euclid was the first to organize these propositions into a logical system in which each result is proved from axioms and previously proved theorems.

<span class="mw-page-title-main">Euclidean space</span> Fundamental space of geometry

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.

<span class="mw-page-title-main">History of geometry</span> Historical development of geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers (arithmetic).

<span class="mw-page-title-main">Triangle</span> Shape with three sides

A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called vertices, are zero-dimensional points while the sides connecting them, also called edges, are one-dimensional line segments. The triangle's interior is a two-dimensional region. Sometimes an arbitrary edge is chosen to be the base, in which case the opposite vertex is called the apex.

<span class="mw-page-title-main">Similarity (geometry)</span> Property of objects which are scaled or mirrored versions of each other

In Euclidean geometry, two objects are similar if they have the same shape, or if one has the same shape as the mirror image of the other. More precisely, one can be obtained from the other by uniformly scaling, possibly with additional translation, rotation and reflection. This means that either object can be rescaled, repositioned, and reflected, so as to coincide precisely with the other object. If two objects are similar, each is congruent to the result of a particular uniform scaling of the other.

<span class="mw-page-title-main">Triangle inequality</span> Property of geometry, also used to generalize the notion of "distance" in metric spaces

In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. This statement permits the inclusion of degenerate triangles, but some authors, especially those writing about elementary geometry, will exclude this possibility, thus leaving out the possibility of equality. If a, b, and c are the lengths of the sides of a triangle then the triangle inequality states that

<span class="mw-page-title-main">Equilateral triangle</span> Shape with three equal sides

In geometry, an equilateral triangle is a triangle in which all three sides have the same length. In the familiar Euclidean geometry, an equilateral triangle is also equiangular; that is, all three internal angles are also congruent to each other and are each 60°. It is also a regular polygon, so it is also referred to as a regular triangle.

Elliptic geometry is an example of a geometry in which Euclid's parallel postulate does not hold. Instead, as in spherical geometry, there are no parallel lines since any two lines must intersect. However, unlike in spherical geometry, two lines are usually assumed to intersect at a single point. Because of this, the elliptic geometry described in this article is sometimes referred to as single elliptic geometry whereas spherical geometry is sometimes referred to as double elliptic geometry.

<span class="mw-page-title-main">Hyperbolic geometry</span> Non-Euclidean geometry

In mathematics, hyperbolic geometry is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with:

In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts. The basic intuitions are that projective space has more points than Euclidean space, for a given dimension, and that geometric transformations are permitted that transform the extra points to Euclidean points, and vice versa.

<span class="mw-page-title-main">Isometry</span> Distance-preserving mathematical transformation

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure". If the transformation is from a metric space to itself, it is a kind of geometric transformation known as a motion.

In mathematical physics, a pseudo-Riemannian manifold, also called a semi-Riemannian manifold, is a differentiable manifold with a metric tensor that is everywhere nondegenerate. This is a generalization of a Riemannian manifold in which the requirement of positive-definiteness is relaxed.

<span class="mw-page-title-main">Taxicab geometry</span> Type of metric geometry

Taxicab geometry or Manhattan geometry is geometry where the familiar Euclidean distance is ignored, and the distance between two points is instead defined to be the sum of the absolute differences of their respective Cartesian coordinates, a distance function called the taxicab distance, Manhattan distance, or city block distance. The name refers to the island of Manhattan, or generically any planned city with a rectangular grid of streets, in which a taxicab can only travel along grid directions. In taxicab geometry, the distance between any two points equals the length of their shortest grid path. This different definition of distance also leads to a different definition of the length of a curve, for which a line segment between any two points has the same length as a grid path between those points rather than its Euclidean length.

In geometry, parallel lines are coplanar infinite straight lines that do not intersect at any point. Parallel planes are planes in the same three-dimensional space that never meet. Parallel curves are curves that do not touch each other or intersect and keep a fixed minimum distance. In three-dimensional Euclidean space, a line and a plane that do not share a point are also said to be parallel. However, two noncoplanar lines are called skew lines. Line segments and Euclidean vectors are parallel if they have the same direction.

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in an Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.

<span class="mw-page-title-main">Euclidean plane</span> Geometric model of the planar projection of the physical universe

In mathematics, a Euclidean plane is a Euclidean space of dimension two, denoted or . It is a geometric space in which two real numbers are required to determine the position of each point. It is an affine space, which includes in particular the concept of parallel lines. It has also metrical properties induced by a distance, which allows to define circles, and angle measurement.

Geometry is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician who works in the field of geometry is called a geometer. Until the 19th century, geometry was almost exclusively devoted to Euclidean geometry, which includes the notions of point, line, plane, distance, angle, surface, and curve, as fundamental concepts.

<span class="mw-page-title-main">Pythagorean theorem</span> Relation between sides of a right triangle

In mathematics, the Pythagorean theorem or Pythagoras' theorem is a fundamental relation in Euclidean geometry between the three sides of a right triangle. It states that the area of the square whose side is the hypotenuse is equal to the sum of the areas of the squares on the other two sides.

References

  1. 1 2 3 Smith, Karl (2013), Precalculus: A Functional Approach to Graphing and Problem Solving, Jones & Bartlett Publishers, p. 8, ISBN   978-0-7637-5177-7
  2. 1 2 Cohen, David (2004), Precalculus: A Problems-Oriented Approach (6th ed.), Cengage Learning, p. 698, ISBN   978-0-534-40212-9
  3. Aufmann, Richard N.; Barker, Vernon C.; Nation, Richard D. (2007), College Trigonometry (6th ed.), Cengage Learning, p. 17, ISBN   978-1-111-80864-8
  4. Andreescu, Titu; Andrica, Dorin (2014), "3.1.1 The Distance Between Two Points", Complex Numbers from A to ... Z (2nd ed.), Birkhäuser, pp. 57–58, ISBN   978-0-8176-8415-0
  5. Tabak, John (2014), Geometry: The Language of Space and Form, Facts on File math library, Infobase Publishing, p. 150, ISBN   978-0-8160-6876-0
  6. Ó Searcóid, Mícheál (2006), "2.7 Distances from Sets to Sets", Metric Spaces, Springer Undergraduate Mathematics Series, Springer, pp. 29–30, ISBN   978-1-84628-627-8
  7. 1 2 Ballantine, J. P.; Jerbert, A. R. (April 1952), "Distance from a line, or plane, to a point", Classroom notes, American Mathematical Monthly , 59 (4): 242–243, doi:10.2307/2306514, JSTOR   2306514
  8. Bell, Robert J. T. (1914), "49. The shortest distance between two lines", An Elementary Treatise on Coordinate Geometry of Three Dimensions (2nd ed.), Macmillan, pp. 57–61
  9. Maekawa, Takashi (March 1999), "An overview of offset curves and surfaces", Computer-Aided Design, 31 (3): 165–173, doi:10.1016/s0010-4485(99)00013-5
  10. Ivanov, Oleg A. (2013), Easy as π?: An Introduction to Higher Mathematics, Springer, p. 140, ISBN   978-1-4612-0553-1
  11. 1 2 3 4 Strichartz, Robert S. (2000), The Way of Analysis, Jones & Bartlett Learning, p. 357, ISBN   978-0-7637-1497-0
  12. Adam, John A. (2017), "Chapter 2. Introduction to the "Physics" of Rays", Rays, Waves, and Scattering: Topics in Classical Mathematical Physics, Princeton Series in Applied Mathematics, Princeton University Press, pp. 26–27, doi:10.1515/9781400885404-004, ISBN   978-1-4008-8540-4
  13. Liberti, Leo; Lavor, Carlile (2017), Euclidean Distance Geometry: An Introduction, Springer Undergraduate Texts in Mathematics and Technology, Springer, p. xi, ISBN   978-3-319-60792-4
  14. Beckman, F. S.; Quarles, D. A. Jr. (1953), "On isometries of Euclidean spaces", Proceedings of the American Mathematical Society , 4 (5): 810–815, doi: 10.2307/2032415 , JSTOR   2032415, MR   0058193
  15. 1 2 Spencer, Neil H. (2013), "5.4.5 Squared Euclidean Distances", Essentials of Multivariate Data Analysis, CRC Press, p. 95, ISBN   978-1-4665-8479-2
  16. Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in k-dimensional spaces and related problems", SIAM Journal on Computing , 11 (4): 721–736, doi:10.1137/0211059, MR   0677663
  17. Randolph, Karen A.; Myers, Laura L. (2013), Basic Statistics in Multivariate Analysis, Pocket Guide to Social Work Research Methods, Oxford University Press, p. 116, ISBN   978-0-19-976404-4
  18. Csiszár, I. (1975), "I-divergence geometry of probability distributions and minimization problems", Annals of Probability , 3 (1): 146–158, doi: 10.1214/aop/1176996454 , JSTOR   2959270, MR   0365798
  19. Moler, Cleve and Donald Morrison (1983), "Replacing Square Roots by Pythagorean Sums" (PDF), IBM Journal of Research and Development, 27 (6): 577–581, CiteSeerX   10.1.1.90.5651 , doi:10.1147/rd.276.0577
  20. Mielke, Paul W.; Berry, Kenneth J. (2000), "Euclidean distance based permutation methods in atmospheric science", in Brown, Timothy J.; Mielke, Paul W. Jr. (eds.), Statistical Mining and Data Visualization in Atmospheric Sciences, Springer, pp. 7–27, doi:10.1007/978-1-4757-6581-6_2
  21. Kaplan, Wilfred (2011), Maxima and Minima with Applications: Practical Optimization and Duality, Wiley Series in Discrete Mathematics and Optimization, vol. 51, John Wiley & Sons, p. 61, ISBN   978-1-118-03104-9
  22. Alfakih, Abdo Y. (2018), Euclidean Distance Matrices and Their Applications in Rigidity Theory, Springer, p. 51, ISBN   978-3-319-97846-8
  23. Kopeikin, Sergei; Efroimsky, Michael; Kaplan, George (2011), Relativistic Celestial Mechanics of the Solar System, John Wiley & Sons, p. 106, ISBN   978-3-527-63457-6
  24. Matoušek, Jiří (2002), Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer, p. 349, ISBN   978-0-387-95373-1
  25. Ciarlet, Philippe G. (2013), Linear and Nonlinear Functional Analysis with Applications, Society for Industrial and Applied Mathematics, p. 173, ISBN   978-1-61197-258-0
  26. Richmond, Tom (2020), General Topology: An Introduction, De Gruyter, p. 32, ISBN   978-3-11-068657-9
  27. Klamroth, Kathrin (2002), "Section 1.1: Norms and Metrics", Single-Facility Location Problems with Barriers, Springer Series in Operations Research, Springer, pp. 4–6, doi:10.1007/0-387-22707-5_1
  28. Panigrahi, Narayan (2014), "12.2.4 Haversine Formula and 12.2.5 Vincenty's Formula", Computing in Geographic Information Systems, CRC Press, pp. 212–214, ISBN   978-1-4822-2314-9
  29. Zhang, Jin (2007), Visualization for Information Retrieval, Springer, ISBN   978-3-540-75148-9
  30. Høyrup, Jens (2018), "Mesopotamian mathematics" (PDF), in Jones, Alexander; Taub, Liba (eds.), The Cambridge History of Science, Volume 1: Ancient Science, Cambridge University Press, pp. 58–72, archived from the original (PDF) on May 17, 2021, retrieved October 21, 2020
  31. Acredolo, Curt; Schmid, Jeannine (1981), "The understanding of relative speeds, distances, and durations of movement", Developmental Psychology , 17 (4): 490–493, doi:10.1037/0012-1649.17.4.490
  32. Henderson, David W. (2002), "Review of Geometry: Euclid and Beyond by Robin Hartshorne", Bulletin of the American Mathematical Society , 39: 563–571, doi: 10.1090/S0273-0979-02-00949-7
  33. Maor, Eli (2019), The Pythagorean Theorem: A 4,000-Year History, Princeton University Press, pp. 133–134, ISBN   978-0-691-19688-6
  34. Rankin, William C.; Markley, Robert P.; Evans, Selby H. (March 1970), "Pythagorean distance and the judged similarity of schematic stimuli", Perception & Psychophysics , 7 (2): 103–107, doi: 10.3758/bf03210143
  35. Milnor, John (1982), "Hyperbolic geometry: the first 150 years" (PDF), Bulletin of the American Mathematical Society , 6 (1): 9–24, doi: 10.1090/S0273-0979-1982-14958-8 , MR   0634431
  36. Ratcliffe, John G. (2019), Foundations of Hyperbolic Manifolds, Graduate Texts in Mathematics, vol. 149 (3rd ed.), Springer, p. 32, ISBN   978-3-030-31597-9