25
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Intuitively, it seems that you should be able to move them closer together and thereby decrease volume, right? Do you have an example where moving them along the line connecting their centers closer doesn't do this? $\endgroup$ – Joel David Hamkins Dec 13 '18 at 0:19
  • 3
    $\begingroup$ @JoelDavidHamkins The intuition is exactly that, I agree. As for "centers", if you meant "move the centers of mass along the line connecting them" (the bodies are not necessarily symmetric), I honestly don't know though I thought a bit of this and a few other movement options, just couldn't come to any conclusions about them in high dimensions. If you meant just "take any two points in the bodies and move along the line connecting them", then yes, there are counterexamples. $\endgroup$ – fedja Dec 13 '18 at 0:39
  • 1
    $\begingroup$ Yes, I had meant the centroids --- the other kind of counterexamples seem easy to make. But now I'm not sure about the centroids idea, since perhaps there is a long narrow arm sticking out (but still convex); if the tip of the arm is far from the centroid, it might affect the move-centers-closer strategy. $\endgroup$ – Joel David Hamkins Dec 13 '18 at 0:47
  • 2
    $\begingroup$ @DeaneYang Definitely not. You can draw two triangles on the plane as a counterexample to this idea. Notice also that the setup is affine invariant while your suggestion isn't, which already makes it a bit suspicious. $\endgroup$ – fedja Dec 13 '18 at 16:59
  • 2
    $\begingroup$ This reminds me a bit of the Kneser–Poulsen conjecture. Also if I have parsed correctly, the title of the question is the reverse of the question in the main text. $\endgroup$ – Timothy Chow Dec 14 '18 at 21:13
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, it is unclear to me why without loss of generality "$x$ is a multiple of $v_1+v_2-v_3-v_4$". I understand that, if $x$ lowers the volume, then its images under all appropriate symmetries will also do. But how does this imply that $x$ itself must be invariant with respect to the symmetries? I also don't understand how this invariance may be related to the convexity in any given direction. $\endgroup$ – Iosif Pinelis Dec 19 '18 at 1:03
  • 1
    $\begingroup$ Looks correct to me. Amazing! I would never think one should search for a counterexample, especially in as low dimension as 3. Thanks, Will! $\endgroup$ – fedja Dec 19 '18 at 14:22
  • 2
    $\begingroup$ @FrancoisZiegler Calculus is hard... $\endgroup$ – Will Sawin Dec 20 '18 at 2:57
  • 2
    $\begingroup$ By the way, this is true for $0<\epsilon<1-\frac{1}{2}\sqrt{3}$. For $\epsilon = 1-\frac{1}{2}\sqrt{3}$ the volume of the convex hull remains exactly constant while moving $K$ and $L$ together. $\endgroup$ – Timothy Budd Dec 20 '18 at 8:48
  • 1
    $\begingroup$ More like Mathematica-fu (might require v11): volume[e_,x_]:=RegionMeasure@ConvexHullMesh@Flatten[{#,{x,0,0}-#[[{1,3,2}]]}& /@{{-1,1,0},{-1,-1,0},{-2e,1/2+e,1/2-e},{-2e,1/2+e,-1/2+e},{-2e,-1/2-e,1/2-e},{-2e,-1/2-e,-1/2+e}},1] $\endgroup$ – Timothy Budd Dec 21 '18 at 10:32
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So a local minimum would have to be a global minimum. (If there is a local minimum which isn't global, look at the line joining it to the global minimum and you have a convex function on $\mathbb{R}$ with two local minima, contradiction.) This seems like good progress because it feels like the global minimum should involve $K \cap (L+x)$ being large, but I can't prove it. $\endgroup$ – David E Speyer Dec 14 '18 at 1:45
  • $\begingroup$ There is a large literature on finding the minimum of $F(t)$ numerically, but so far I found no general properties of this minimum. $\endgroup$ – Alexandre Eremenko Dec 14 '18 at 2:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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