Welcome to MathOverflow

Question

1

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

flag	asked Sep 4 at 15:34 Gokhan 13●2

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 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 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

Robert Israel · Accepted Answer · 2012-09-04 19:17:43Z UTC

4

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

answered Sep 4 at 19:17

Robert Israel
10.8k●8●22

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 at 7:07

Distance calculation in metric space

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.