$ L_p$ metrics

The most important family of metrics over $ {\mathbb{R}}^n$ is given for any $ p
\geq 1$ as

$\displaystyle \rho(x,x^\prime) = \bigg( \sum_{i=1}^n \vert x_i - x_i^\prime\vert^p \bigg)^{1/p} .$ (5.1)

For each value of $ p$, (5.1) is called an $ L_p$ metric (pronounced ``el pee''). The three most common cases are
  1. $ L_2$: The Euclidean metric, which is the familiar Euclidean distance in $ {\mathbb{R}}^n$.
  2. $ L_1$: The Manhattan metric, which is often nicknamed this way because in $ {\mathbb{R}}^2$ it corresponds to the length of a path that is obtained by moving along an axis-aligned grid. For example, the distance from $ (0,0)$ to $ (2,5)$ is $ 7$ by traveling ``east two blocks'' and then ``north five blocks''.
  3. $ L_\infty$: The $ L_\infty$ metric must actually be defined by taking the limit of (5.1) as $ p$ tends to infinity. The result is

    $\displaystyle L_\infty(x,x^\prime) = \max_{1 \leq i \leq n} \{ \vert x_i - x^\prime_i\vert \},$ (5.2)

    which seems correct because the larger the value of $ p$, the more the largest term of the sum in (5.1) dominates.
An $ L_p$ metric can be derived from a norm on a vector space. An $ L_p$ norm over $ {\mathbb{R}}^n$ is defined as

$\displaystyle \Vert x\Vert _p = \bigg( \sum_{i=1}^n \vert x_i\vert^p \bigg)^{1/p} .$ (5.3)

The case of $ p = 2$ is the familiar definition of the magnitude of a vector, which is called the Euclidean norm. For example, assume the vector space is $ {\mathbb{R}}^n$, and let $ \Vert\cdot\Vert$ be the standard Euclidean norm. The $ L_2$ metric is $ \rho(x,y) = \Vert x-y\Vert$. Any $ L_p$ metric can be written in terms of a vector subtraction, which is notationally convenient.

Steven M LaValle 2012-04-20