Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Euclidean distance

In mathematics the Euclidean distance or Euclidean metric 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).

Contents

1 Definition

2 Two-dimensional distance

2.1 Approximation

3 Three-dimensional distance

4 See also

Definition

The Euclidean distance for two points x = (x₁,...,x_n) and y = (y₁,...,y_n) in Euclidean n-space is defined as

$d(x,y):=\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}$

Two-dimensional distance

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 dy≥dx, approximated 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 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

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

All Science Fair Projects