4
$\begingroup$

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; metric d

I've created a model of this function in geogebra:
enter image description here
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)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ $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. $\endgroup$ – Sylin Mar 16 '14 at 13:20
2
$\begingroup$

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
2 are contradictions,
and the rest are satisfied with $\leq$.


So then $d_{K}$ is a linear combination of 2 metrics, so it is a metric.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.