1
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – algori
    Sep 4, 2012 at 16:05
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 4, 2012 at 18:15
  • $\begingroup$ I am working on $R^n$ and distance metric $d$ is $l_1$ or $l_{\infty}$. Thanks for the answers. $\endgroup$
    – Gokhan
    Sep 5, 2012 at 7:12
  • $\begingroup$ 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. $\endgroup$ Sep 6, 2012 at 7:09

1 Answer 1

4
$\begingroup$

This sort of thing is considered under the name "minimax facility location problem". See http://en.wikipedia.org/wiki/Facilities_location.

$\endgroup$
1
  • $\begingroup$ This is not quite facility location because you're not "searching" for facilities in the OP's question - you're given the facilities (the set A) $\endgroup$ Sep 6, 2012 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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