MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Distance calculation in metric space

Dear All,

I want to calculate the distance between two sets in which the maximum distance between the sets are minimized. Formally problem defined as,

$\displaystyle \min_{a \in A} \max_{b \in B}$ d(a,b)

This problem looks similar to Hausdorff distance, but the order of $min$ and $max$ are swapped. While a lot of studies can be found about Hausdorff distance, I could not find any study about my problem.

• Is there any specific name of my problem that I missed?
• Do you have any solution advises for the problem except for the complete enumeration? Since the complexity of the complete enumeration is $O(|A| \cdot |B|)$, in my case it is not acceptable as a solution method.

Best Regards

-
Gokhan -- this is not a metric. For instance, the distance from $S^1$ to $S^1$ is 2 where $S^1$ is the unit circle in the plane. – algori Sep 4 at 16:05
If you want a faster way to calculate the quantity you wrote it might help to say what kind of a metric $d$ is. Are you working in Euclidean space? In $\mathbb{R}$ there is certainly a faster algorithm. – Trevor Wilson Sep 4 at 18:15
I am working on $R^n$ and distance metric $d$ is $l_1$ or $l_{\infty}$. Thanks for the answers. – Gokhan Sep 5 at 7:12
If you're in a low dimensional space, then your problem reduces to performing a set of point location queries in a farthest-point Voronoi diagram under the appropriate metric. – Suresh Venkat Sep 6 at 7:09