9
$\begingroup$

Let $C\subset \mathbb{R}^n$ be a compact, convex set. In any convex analysis course, it would be a standard homework exercise to prove that the functions $f(x)=\max_{y\in C} \|x-y\|$ and $f(x)=\min_{y\in C} \|x-y\|$ are convex (although the proof of the latter is a little harder than that of the former, for all proofs I've seen). I'm interested in a generalization of these functions: say that $C$ has volume $1$, define $a\in(0,1)$, and define $$f_a(x)=\min\{r:\mathrm{vol}(B_r(x)\cap C)=a \}$$ where $B_r(x)$ is the ball of radius $r$ about $x$. The two functions I described above would correspond to the limiting cases where $a=1$ and $a\to0$ respectively. (I'm not sure if such functions have a name, like "partial distance", "threshold distance", or something to that effect)

I was able to convince myself that (for fixed $a$), the function $f_a(x)$ is convex, although I had to appeal to Minkowski sums and treat $f_a(x)$ as a jointly convex function $f_a(x,S)$ over the set of all measurable subsets of $C$. This seems like a really complicated way to prove this fact; is there something more direct that I was missing?

$\endgroup$

1 Answer 1

4
$\begingroup$

Lemma. Let $B_r(x), B_s(y)$ be two balls in $\mathbb{R}^n$, $A \subseteq B_r(x)$, $B \subseteq B_s(y)$ convex sets such that $\mathrm{vol}(A), \mathrm{vol}(B) \geq a$, and $C = \mathrm{Conv}(A,B)$. Then, for every $t \in [0,1]$, $$ \mathrm{vol}(C \cap B_{(1-t)r+ts}((1-t)x+ty)) \geq a $$

Proof. Fix $t$. From the triangle inequality, it is easy to see that the set $$ (1-t)A + tB = \{ (1-t)z+tw : z\in A, w \in B\} $$ is contained in $B_{(1-t)r+ts}((1-t)x+ty)$. Using that, for $s \geq 0$ and $E \subseteq \mathbb{R}^n$, $$ \mathrm{vol}(sE) = s^n \mathrm{vol}(E) $$ and the Brunn–Minkowski inequality (see here), one gets $$ \mathrm{vol}((1-t)A + tB)^{1/n} \geq (1-t) \mathrm{vol}(A)^{1/n} + t \mathrm{vol}(B)^{1/n} \geq (1-t)a^{1/n} + ta^{1/n} = a^{1/n}, $$ hence $$ \mathrm{vol}(C \cap B_{(1-t)r+ts}((1-t)x+ty)) \geq \mathrm{vol}((1-t)A + tB) \geq a. $$

Now it is easy to prove convexity by taking $(x,r), (y,s)$ in the epigraph of your function $f_a$ and using the Lemma with $A = C \cap B_r(x)$, $B = C \cap B_s(y)$ to prove that $((1-t)x+ty, (1-t)r+ts)$ belongs to the epigraph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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