Let $D$ be a compact subset of $\mathbb R ^d$, $L>0$ a Lipschitz constant, $\lVert \cdot \rVert$ a norm on $\mathbb R ^d$, and $f \colon D \to \mathbb R$ an $L$-Lipschitz function with respect to $\lVert \cdot \rVert$. It is known that the extension $\bar{f} \colon \mathbb R ^d \to \mathbb R, \boldsymbol x \mapsto \sup_{\boldsymbol y \in D} \bigl( f(\boldsymbol y) - L \lVert \boldsymbol x - \boldsymbol y \rVert \bigr)$ satisfies
- $\bar{f}(\boldsymbol x) = f(\boldsymbol x)$ for all $\boldsymbol x \in D$;
- $\bar{f}$ is $L$-Lipschitz with respect to $\lVert \cdot \rVert$;
- $\max(\bar{f}) = \max(f)$.
At a high level, I can see how $\bar{f}$ is shaped: it coincides with $f$ on $D$, then it decreases linearly (or rather, conically), with a slope $L$, outside of $D$. This leads me to believe that the sets of (approximate) maximizers of the two functions are similar, as I now make precise.
For a continuous function $g \colon E \subseteq \mathbb R ^d \to \mathbb R$ that attains its maximum at a point $\boldsymbol x^\star \in E$, we define, for each $\varepsilon >0$, the set of its $\varepsilon$-maximizers by $\varepsilon\text{-opt}(g) := \bigl\{ \boldsymbol x \in E : g(\boldsymbol x ^\star) - g(\boldsymbol x) \le \varepsilon \bigr\}$.
I am trying to see when the volume $\mathrm{vol}$ (i.e., the $d$-dimensional Lebesgue measure) of the set of the $\varepsilon$-maximizers of $f$ is close to that of $\bar{f}$. Formally, if it is true that there exists a constant $C>0$ such that, for all $\varepsilon >0$, one has $\mathrm{vol} \bigl( \varepsilon\text{-opt}(\bar{f}) \bigr) \le C \mathrm{vol} \bigl(\varepsilon\text{-opt}(f) \bigr)$.
I see that this is not true in general, because if $D$ has zero volume, then also $\mathrm{vol} \bigl(\varepsilon\text{-opt}(f) \bigr) = 0$, while the LHS is positive. I then came up with this assumption to tame the geometry of $D$. (Below, $B_r(\boldsymbol x) := \bigl\{\boldsymbol y \in \mathbb R ^d : \lVert \boldsymbol x - \boldsymbol y \rVert \le r \bigr\}$.)
Assumption 1. There exists $c>0$ such that, for all $\boldsymbol x \in D$ and all $r>0$, we have $\mathrm{vol} \bigl( D \cap B_r(\boldsymbol x) \bigr) \ge c r^d$.
At a high level, Assumption 1 says that a constant fraction of each ball centered at $D$ is contained in $D$. My question now (whose answer I believe to be yes but I could not prove) is the following.
Question: If Assumption 1 holds, is true that there exists a constant $C>0$ such that, for all $\varepsilon >0$, one has $\mathrm{vol} \bigl( \varepsilon\text{-opt}(\bar{f}) \bigr) \le C \mathrm{vol} \bigl(\varepsilon\text{-opt}(f) \bigr)$?
Edit: the reason why I believe Assumption 1 would help is that, for all $\varepsilon >0$, $\varepsilon\text{-opt}(f) \subseteq \varepsilon\text{-opt}(\bar{f}) \subseteq \varepsilon\text{-opt}(f) + B_{\varepsilon/L}(\boldsymbol 0)$, and the difference between the first and the last set is essentially a bunch of balls centered at the boundary of $D$, which under the assumption take up approximately the same amount of space of the same balls intersected with $D$.