Bounding the Modified Hausdorff Distance I'm doing a summer research project on model validation metrics for applications in oil spill modeling.  The idea is to change a single variable in a model one at a time until a certain "metric" is minimized between the model and the observation.  Repeating the process for all relevant variables results in a strong approximation of the observed data.  There's no standard yet since the modelling technique is new, and hopefully significantly improves over the older HYCOM models.  My role is to develop and compare metrics that are sufficiently accurate for our needs.
Currently, I've had good success with the so-called Modified Hausdorff Distance as given by Dubuisson and Jain (http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=576361&tag=1):
\begin{equation*}
d_{MH}(A,B) = \max\left\{\frac{1}{|A|}\sum_{a\in A}d(a,B), \frac{1}{|B|}\sum_{b\in B}d(b,A)\right\},
\end{equation*}
where $A,B\subset\mathbb{R}^n$ such that $|A|,|B|<\infty$.  Also, $d(a,B)=\min_{b\in B}\|a-b\|$, and similarly for $d(b,A)$.
The metric has performed very well in various tests, showing the desired monotonicity with respect to various standard homotopies (translation, scaling, noise).  Additionally, it scored quite well on a facial recognition test I ran using grayscale images from the AT$\&$T Database of Faces (http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html).
The problem, as stated by the authors, is that the function isn't a topological metric on the space of all finite subsets of $\mathbb{R}^n$ since it fails the triangle inequality.  For the pursposes of our applications, this doesn't seem to be a huge problem since it's done so well in practice.  However, I'd like to at least develop some bounds on this bad behavior.  Namely, I'm stuck on two things:
(1)   I need a good counterexample to the triangle inequality.  Any ideas?  I've had trouble coming up with one, and the authors don't cite any.
(2)   My intuition tells me the counterexample(s) will involve sets with small numbers of points, and if this is the case I'd like to see if I can develop an approximation of the form $d(A,C)\leq d(A,B)+d(B,C)+\epsilon(n)$, where $n=\max(|A|,|B|)$ and $\epsilon:\mathbb{Z}^+\to\mathbb{R}$ monotonically decreases.  Thus for large sample sizes, $d_{MH}$ is essentially a true topological metric.
Any suggestions on how to proceed?  I'm a bit stuck.. any suggestions would be very helpful.
Jon
EDIT 1: After further testing, it turns out the suggested value of $K=3/2$ is too small.  I've yet to achieve values of $K>3/2$ in MATLAB simulations in $\mathbb{R}^n$ for $n\in\{2,3,4\}$, however values around $K=3$ are required for $n\not\in \{2,3\}$.

The above plot shows one such simulation.  For each $k=1,...,10$, I plotted random sets of points $A,B,C\subset\mathbb{R}^k$ and computed $d_{MH}(A,B),d_{MH}(B,C)$, and $d_{MH}(A,C)$ $10^5$ times.  I then found the maximum value of $K$ to force the proposed inquality to hold.  The $x$-axis indicates the dimension, and the $y$-axis indicates the $K$ values.  I'm not quite sure what to make of this yet.  I think it's clear that if such a bounding of the Modified Hausdorff Distance exists, it must be a multiplicative one.  Based on significant empirical evidence, I find it doubtful the function is unbounded.  The behavior on $\mathbb{R}^k$ for $k=1,2,3$ makes sense, but why the increasing behavior for higher dimensions??
EDIT 2: As requested, here's an example in $\mathbb{R}$ that forces $K>2$:
\begin{align*}
A &= \{4,11\}\\
B &= \{2,13,14,18,20,26,61\}\\
C &= \{5,53,58,65,79,81\}.
\end{align*}
Then $d_{MH}(A,B)=12.5714,d_{MH}(B,C)=10.2857,$ and $d_{MH}(A,C)=47$.  Thus the smallest $K\in\mathbb{R}$ such that $d_{MH}(A,C)\leq K(d_{MH}(A,B)+d_{MH}(B,C))$ is $K=2.0563$.
The plot isn't terribly illuminating, but I'll include it as requested:

Edit 3: The following bounds have been disproved:
\begin{align*}
1.& d_{MH}(A,C)\leq d_{MH}(A,B)+d_{MH}(B,C)+\epsilon;\\
2.& d_{MH}(A,C)\leq K(d_{MH}(A,B)+d_{MH}(B,C));\\
3.& d_{MH}(A,C)\leq K\cdot\max\{d_{MH}(A,B),d_{MH}(B,C)\}. 
\end{align*}
Counterexamples to 1 and 2 can be found below.  For 3, choose $A,B,C$ as in (6).  Then, letting $\delta$ denote the minimal distance from a point in $N_{n,r}$ to $N$ for $N\in\{1,2\}$, we have:
\begin{equation*}
d(A,C)\leq\frac{n}{n+1}(n\delta+1), ~~~ d(A,B)\geq\frac{n\delta+1}{n+1},~~~ d(B,C)\geq \delta.
\end{equation*}
Hence
\begin{align*}
d(A,C)\leq K\cdot\max\{d(A,B),d(B,C)\} &\Leftrightarrow K\geq\frac{d(A,C)}{\max\{d(A,B),d(B,C)\}}\\
&\Leftrightarrow K\geq \frac{1+r}{1/n+\delta}\rightarrow \infty
\end{align*}
as $r\rightarrow 0$ and $n\rightarrow\infty$.
 A: A simple counterexample is 
$$A=\{1,2\}, B=\{2,3\}, C=\{3,4\} \tag1$$ all considered as subsets of $\mathbb R$. Indeed, $d_{MH}(A,B)=1/2=d_{MH}(B,C)$,  but $d_{MH}(A,C)=3/2$. 
There are some issues with the proposed inequality $$d(A,C)\leq d(A,B)+d(B,C)+\epsilon(n) \tag{2}$$ 


*

*Scaling by $\lambda>0$. Replacing $A,B,C$ by $\lambda A=\{\lambda x: x\in A\}$, $\lambda B$ and $\lambda C$ results in all distances multiplied by $\lambda$. But the term $\epsilon(n)$ does not scale, and this is going to break the inequality (2). For example, putting $A=\{\lambda,2\lambda\}$, $B=\{2\lambda,3\lambda\}$, and $C=\{3\lambda,4\lambda\}$ in (2) we get 
$$\frac32\lambda \leq \lambda+\epsilon(2) \tag{3}$$ 
which can't be true with $\epsilon(2)$ independent of $\lambda$.

*Duplication of points. From a counterexample with small sets such as (1) I can construct counterexamples with almost the same MH-distances and arbitrarily large sets. One way to do this is to replace each set in (1) with the union of its translates by tiny amounts, such as
$$\bigcup_{k=0}^{1000}(A+k\cdot 10^{-6})=\{1,1+10^{-6},\dots, 1+10^{-3}, 2,2+10^{-6},\dots, 2+10^{-3}\} \tag4$$ 
Now each set  has $2000$ elements, and none of the MH-distances changed by more than $10^{-3}$.
What might be true is an inequality with universal multiplicative constant $K>1$, that is,
 $$d(A,C)\leq K(d(A,B)+d(B,C)) \tag{5}$$ 
Example (1) shows that $K$ must be at least $3/2$. So far I have not found any examples that require  $K>3/2$.
Added: Unfortunately, (5) does not hold either, for any universal constant $K$. To describe a counterexample, I use notation $a_{n,r}$ which means  $n$ distinct points placed in the $r$-neighborhood of point $a$. For example, the set in (4) could be written as $\{1_{1000,1/1000}, 2_{1000,1/1000}\}$. Consider the sets
$$A=\{1\},\ B=\{1_{n,r},2\}, \ C=\{1, 2_{n,r}\} \tag6$$
Here 
$$\begin{split}d_{MH}(A,B)&\le \frac{1}{n+1}(nr+1) \le r+\frac{1}{n}\\
 d_{MH}(B,C) &\le \frac{1}{n+1}(n+1)r = r\\
 d_{MH}(A,C) &\ge \frac1{n+1}n(1-r) \end{split} \tag7$$
As $n\to\infty$ and $r\to 0$, the first two distances tend to $0$ while $d(A,C)\to 1$. 
