Encyclopedia > Euclidean distance

  Article Content

Euclidean distance

The Euclidean distance of two points x = (x1,...,xn) and y = (y1,...,yn) in Euclidean n-space is computed as
<math>\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (x_n-y_n)^2} = \sqrt{\sum_{i=1}^n (x_i-y_i)^2}</math>
It is the "ordinary" distance between the two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. By using this formula as distance, Euclidean space becomes a metric space (even a Hilbert space).

Two-dimensional distance

For two 2D points P=[px,py] and Q=[qx,qy], the distance is computed as

<math>\sqrt{(px-qx)^2 + (py-qy)^2}</math>

Approximation

A fast approximation of 2D distance based on an octagonal boundary can be computed as follows. Let dx = |px-qx| (absolute value) and dy = |py-qy|. If dydx, aproximated distance is 0.41dx+0.941246dy. (If dy<dx, swap these values.) The difference from the exact distance is between -6% and +3%; more than 85% of all possible differences are between -3% to +3%.

The following Waterloo Maple code implements this approximation and produces the plot on the right, with a true circle in black and the octagonal approximate boundary in red:
fasthypot :=
  unapply(piecewise(abs(dx)>abs(dy), 
                    abs(dx)*0.941246+abs(dy)*0.41,
                    abs(dy)*0.941246+abs(dx)*0.41),
          dx, dy):
hypot := unapply(sqrt(x^2+y^2), x, y):
plots[display](
  plots[implicitplot](fasthypot(x,y) > 1, 
                      x=-1.1..1.1, 
                      y=-1.1..1.1,
                      numpoints=4000),
  plottools[circle]([0,0], 1),
  scaling=constrained,thickness=2
);

Other approximations exist as well. They generally try to avoid the square root, which is an expensive operation in terms of processing time, and provide various error:speed ratio. Using the above notation, dx + dy - 2*min(dx,dy) yields error in interval 0% to 12%. (Attributed to Alan Paeth.)

Three-dimensional distance

For two 3D points P=[px,py,pz] and Q=[qx,qy,qz], the distance is computed as

<math>\sqrt{(px-qx)^2 + (py-qy)^2 + (pz-qz)^2}</math>



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Reformed churches

... of Faith[?], Westminster Shorter Catechism[?], Westminster Larger Catechism[?], Theological Declaration of Barmen[?], Confession of 1967[?], and A Brief Statement of ...

 
 
 
This page was created in 33.9 ms