## 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
$\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}$
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).

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

$\sqrt{(px-qx)^2 + (py-qy)^2}$

### 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.)

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

$\sqrt{(px-qx)^2 + (py-qy)^2 + (pz-qz)^2}$

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