# Determine whether this d is a metric?

Suppose we have a function $d:\mathbb{Z}^{2}\times\mathbb{Z}^{2}\rightarrow\mathbb{R}$ where $\forall(x_{0},y_{0}),(x_{1},y_{1})\in \mathbb{Z}^{2}$, we have..

$d\left( \left( x_{0},y_{0} \right), \left( x_{1},y_{1} \right) \right)\;\;=\;\;\left| \left| x_{1}-x_{0} \right| - \left| y_{1}-y_{0} \right| \right|\;\;+\;\;\sqrt{2}\cdot \min \left \{ \left | x_{1}-x_{0} \right | , \left | y_{1}-y_{0} \right |\right \}$

I am trying to determine whether $d$ is a metric in $\mathbb{Z}^{2}$ and I am a bit stuck on the triangle inequality.

Graphically, I think of this d as somewhere in-between a Euclidean and Manhattan distance;

I've created a model of this function in geogebra:

The bold text will switch to saying "Counter-example" once the inequality fails when we move the 3 points around. The geogebra file is uploaded here (8kb). So far, no counter-example have been found.

The algebraic problem aside, I will be using this $d$ as a heuristic in an A* search algorithm, so what would be the significance, if any, of $d$ being a metric (if it is) (as opposed to an arbitrary assignment of numbers for a heuristic, say)?

Hint: let $d_1$ and $d_2$ be two metrics on the same metric space $X$, with $\lambda>0$.

Then

$$\lambda d_1, \lambda d_2~~\text{are both metrics }.$$ $$d_1+d_2~~\text{is a metric }.$$

In particular, $d:=d_1+\lambda d_2$ is a metric.

• $d_{1} := ||x_{1}-x_{0}|-|y_{1}-y_{0}||$ is not a metric because it is not positive definite (in particular, take any 2 points along $y=x$ or $y = -x$, distinct, but $d_{1}$ evaluates to 0). But I'll try it on different formulations and see what I get. – Sylin Mar 16 '14 at 13:20

We reformulate the function as folows:
The first term (the difference between the 2 side lengths of the rectangle formed by the 2 points) can be expressed as the difference between the maximum of the 2 side lengths and the minimum. $$d_{K}((x_{0},y_{0}),(x_{1},y_{1})) = \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} - \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + \sqrt{2} \cdot \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ $$d_{K} = \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (\sqrt{2} - 1) \cdot \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ Using $\min \{ a, b\} = a + b - \max \{ a ,b\}$: $$= \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (\sqrt{2} - 1) \cdot (|x_{1}-x_{0}| + |y_{1}-y_{0}| - \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \})$$ $$= (\sqrt{2} - 1) \cdot d_{M} + \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (1 - \sqrt{2}) \cdot \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ $$= (\sqrt{2} - 1) \cdot d_{M} + (2 - \sqrt{2}) \cdot \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ where $d_{M}$ is the Manhattan metric.
Note $\sqrt{2} - 1 > 0$ and $2-\sqrt{2} > 0$
It suffices to show that $d((x_{0},y_{0}),(x_{1},y_{1})) := \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$ is a metric.

Symmetry and positive definiteness is easy.
We show triangle inequality by case analysis. Goal: $$d((x_{0},y_{0}),(x_{2},y_{2})) \leq d((x_{0},y_{0}),(x_{1},y_{1})) + d((x_{1},y_{1}),(x_{2},y_{2}))$$ $$\max \{ |x_{2}-x_{0}|,|y_{2}-y_{0}| \} \leq \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + \max \{ |x_{2}-x_{1}|,|y_{2}-y_{1}| \}$$ We first show that $\max \{ a+b, c+d \} \leq \max \{ a,c \} + \max \{ b,d \}$ for non-negative $a,b,c,d$. This is the case analysis. Then the rest easily follows.

.
For each $\max \{ .. \}$, we get 2 cases, so the above gives us $2^{3}$ cases.
2 will turn out to be satisfied with equality
and the rest are satisfied with $\leq$.
So then $d_{K}$ is a linear combination of 2 metrics, so it is a metric.