Mathematical Definition

A metric is a function $ d(x, y) $ which returns a nonnegative number expressing the distance between $ x $ and $ y $ which satisfies the three conditions:

• $ d(x, y) \geq 0 $,
• $ d(x, y) = 0 $ if and only if $ x = y $, and
• $ d(x, z) \leq d(x, y) + d(y, z)$.

The last condition is referred to as the triangle inequality. In words, the triangle inequality says path directly connecting two points must be shorter than or equal to an out-of-the-way path visiting a third point. This is shown in Figure 1.

Figure 1. Demonstration of the triangle inequality.

An example where the triangle inequality does not hold are street distances. For example, if one starts at the corner of University Ave. and Northfield Dr. (Point A in Figure 2), following University Ave. to the corner of University Ave. and King St. (Point B) is 7.7 km; meanwhile, following Northfield Dr. to King St. and following King St. to University Ave. is only 5.3 km.

Figure 2. The longer direct route from University Ave. and Northfield Dr. to University Ave. and King St. along University Ave. (maps.google.ca)

Figure 3. The shorter indirect route from University Ave. and Northfield Dr. to University Ave. and King St. along Northfield Dr. and then King St. (maps.google.ca)

The 1-, 2-, or ∞-norms may be used to define a metric on an n-dimensional vector space of real numbers. This is therefore an implicitly defined relation between any two points in the space.

Examples

Real numbers are a metric space with the function $ d(x,y) = |x - y|$.

2-dimensional vectors form a metric space with the function $ d({\bf x}, {\bf y}) = ||{\bf x} - {\bf y}||_2 = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2}$.

Note that while the real numbers (including integers and rational numbers) do form a metric space, it is usually much better to think of real numbers as being linearly ordered and using a data structure which implements the Abstract Sorted List.

Alternatively, 2- or higher-dimensional vectors of real numbers may be lexicographically ordered and yet, this is seldom the appropriate means of storing data.

Additional Operations on Vector Spaces

The most common additional operations which may be performed on a vector space include:

• Finding the nearest point/vector to a given point/vector (which may or may not be in the container), and
• Find all points/vectors within a specified (usually convex) region.

In either case, a lexicographical ordering is inappropriate and will result in unnecessarily slow run times. The most common means of storing points/vectors in a n-dimensional vector space is to recursive divide the space into two or more partitions yielding the:

• The Abstract Space Partitioning

There are cases, such as with Conway's Game of Life which is restricted to a 2-dimensional vector space, the possible points are restricted to those vectors with integral values and it is only necessary to know whether or not objects exist within a infinity-norm of 1. This allows even faster implementations.