Definition 0. Given a metric space $X$ and subsets $H$ and $S$ thereof, define: $$d(H,S) = \sup_{h \in H} \inf_{s \in S}d(h,s)$$
(This as an asymmetric version of the Hausdorff distance.)
Here's some slightly dodgy intuition about why this definition is interesting: imagine that $S$ is a set of "safety points" and $H$ is the set of "homes where people live." If a disaster strikes and people begin making their way to the nearest safety point, then $d(H,S)$ (read: distance from houses to safety) describes the elapsed time until everyone gets to safety, assuming that everyone leaves immediately and moves with speed $1$.
I'm interested in the following problem: $H$ = "the homes where people live" is given, and we need to place $k$-many safety points in an optimal way, so that the elapsed time before everyone is safe is minimized. More formally:
Problem. Given
- $H$, a bounded subset of $\mathbb{R}^n$, and
- $k$, a natural number
find:
- a subset $S$ of $\mathbb{R}^n$ satisfying $|S| \leq k$, such that for all "competing" subsets $S'$ of $\mathbb{R}^n$ satisfying $|S'| \leq k,$ we have $d(H,S) \leq d(H,S')$.
Question. Have any tools or techniques been developed to solve this problem for sufficiently nice $H$?