Can we always shift two disjoint convex bodies a little bit to decrease the volume of their convex hull?

Question

Let $K,L\subset\mathbb R^d$ be two disjoint compact convex sets with non-empty interiors. Can $x=0$ be a point of local minimum for the function $F(x)=\text{vol}_d(\text{conv(K,L+x))}$?

I was asked this question by Dan Florentin a few weeks ago and I still cannot answer it in high dimensions (for $d=1,2$ the answer is "No"). Any ideas will be appreciated.

Answer 1

This fails already for $d=3$.

Consider a tetrahedron, e.g. the convex hull of the points $v_1,v_2,v_3,v_4$. Let $K$ be the closed subset consisting of $\sum_{i=1}^4 a_i v_i$ with $\sum_{i=1}^4 a_i=1$ and $a_3 +a_4 \leq 1/2-\epsilon$. Let $L$ be defined similarly, but $a_1+a_2 \leq 1/2-\epsilon$. Clearly the convex hull of $K$ and $L$ is this tetrahedron.

Consider a shift vector $x$ which lowers the volume of the convex hull. By the convexity described in Alexandre's answer, we can assume $x$ is invariant under all symmetries of the situation. By the symmetry switching $v_1$ and $v_2$ and the one switching $v_3$ and $v_4$, $x$ is a multiple of $v_1+v_2-v_3-v_4$. It suffices to handle the case where it is a small positive multiple. (For a negative multiple, there would just be a local minimum further out.)

The chance in volume for small $x$ is the sum of, for each triangular face of the tetrahedron, the integral of the dot product of the surface normal of the face with any vector describing the change in the boundary of the polyhedron. The dot product of the surface normal of each face with $x$ is the same, up to sign. If we normalize so this is $1$, then this dot product will lie between $0$ and $1$ on the faces spanned by $v_1,v_2,v_3$ and $v_1,v_2,v_4$, and between $0$ and $-1$ on the spaces spanned by $v_1,v_3,v_4$ and $v_2,v_3,v_4$.

On the face $v_1,v_2,v_3$, this is the maximal convex function that is $0$ at $v_1$ and $v_2$, $1$ on $L$ (which are the points $av_1+bv_2+cv_3$ with $c \geq 1/2 +\epsilon$). In particular, with $c < 1/2+\epsilon$, its value is $c/(1/2+\epsilon)$. Clearly the integral depends continuously on $\epsilon$, so we will evaluate in the case $\epsilon=0$. So the integral of this function divided by the area of the face is $$\frac{ \int_0^{1/2} (1-x) (2x) dx + \int_{1/2}^1 (1-x)dx }{ \int_0^1 (1-x) dx} = \frac{ 1/4 - 1/12 +1/2 - 3/8 }{1/2} = \frac{7}{12}$$

The same is true for the face $v_1,v_2,v_4$.

On the face $v_2,v_3,v_4$, this is the maximal concave function that is $-1$ on $v_3$ and $v_4$ and $0$ whenever $a \geq 1/2+\epsilon$, in other words when $a < 1/2+\epsilon$ it is $ -( (1/2+\epsilon)-a )/(1/2+\epsilon)$. Again there is a continuity and we can take $\epsilon=0$. Then the integral is

$$ - \frac{ \int_{0}^{1/2} (1-x) (1-2x) dx } { \int_0^{1} (1-x) dx} =+ \frac{1/2 -3/8 + 1/12}{1/2}= - \frac{5}{12}$$

Because $\frac{7}{12}-\frac{5}{12}>0$, the change in the $x$ direction is positive, and it remains so for $\epsilon$ sufficiently small.

---

I thought I would add some motivation for this answer after a friend asked me about it. Why this construction?

The first thing to notice when looking for a counterexample is that, for any disjoint compact convex bodies $K,L$, if we expand $K$ and $L$ to larger convex bodies $K',L'$ while keeping them within $\operatorname{conv}(K, L)$, then we haven $\operatorname{conv} (K',L') = \operatorname{conv} (K, L)$ so $$\operatorname{vol}_d ( \operatorname{conv} (K',L') )= \operatorname{vol}_d ( \operatorname{conv} (K, L)),$$ but $\operatorname{conv} (K',L'+x) \supseteq \operatorname{conv} (K,L+x) $ so $$\operatorname{vol}_d ( \operatorname{conv} (K',L'+x) )= \operatorname{vol}_d ( \operatorname{conv} (K, L+x)).$$

Thus if $0$ was a local minimum before it is still a local minimum after, and growing $K$ and $L$ in that way might make it a minimum if it wasn't before. So if we're looking for an example we should certainly keep growing $K$ and $L$ until there is no room left. This is accomplished when we separate the convex body $\operatorname{conv}(K,L)$ by a hyperplane, and let $K$ and $L$ each almost fill one of the two separated pieces.

So the question is a bit of a trick question: It's asking for two convex bodies, but you should really be looking for one convex body, cut in half (or, perhaps, divided unevenly).

Which convex body should you cut in half? Well, if convex body is a cylinder, so the two sides are identical, it will certainly not give an example as we can just push the two sides into each other on an equal axis. Even an approximate cylinder will not be an example for this reason. So we should make the two sides as different from each other as possible. In three dimensions, our best hope is to make one side tall and thin and the other side short and wide, which gives a tetrahedron.

Then it's a matter of calculating to see if the tetrahedron suffices.

Answer 2

I think this may help:

Lemma. For any two convex sets, and any vector $x$, the function $F(t)={\mathrm{Vol}}\left(\mathrm{conv}\left(K\cup(L+xt)\right)\right)$ is convex, as a function of real variable $t$.

This is cited in https://math.bme.hu/~ghorvath/surveyonconvhullvolumebeamer1.pdf

with the reference to

Fary, I., Redei, L. Der zentralsymmetrische Kern und die zentralsymmetrische Hulle von konvexen Korpern. Math. Annalen. 122 (1950), 205-220.