Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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 '12 at 16:05
1  
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 '12 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 '12 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 '12 at 7:09
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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) –  Suresh Venkat Sep 6 '12 at 7:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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