3

I read the book Convex Optimization Algorithms and Complexity, The Lemma 2.2:

Let $\mathcal{K}$ be a centered convex set, i.e., $\int_{x \in \mathcal{K}} x dx = 0$, then for any $w \in \mathbb{R}^n, w \neq 0$, how to prove

$$\mathrm{Vol} \left( \mathcal{K} \cap \{x \in \mathbb{R}^n : x^{\top} w \geq 0\} \right) \geq \frac{1}{e} \mathrm{Vol} (\mathcal{K}) $$

I thought $x^{\top} w \geq 0$ would evenly separate the convex body into two parts, so $$\mathrm{Vol} \left( \mathcal{K} \cap \{x \in \mathbb{R}^n : x^{\top} w \geq 0\} \right) = \frac{1}{2} \mathrm{Vol} (\mathcal{K}) $$ What is wrong with my thoughts?

Dan Li
  • 93
  • 2
    Concerning your second question: If you consider a equilateral triangle and cut through its center of mass, it will not be cut in half. – gerw Sep 13 '23 at 09:08
  • @gerw In that case, the minimum area of the small part is 1/3 of the total area, (which is separated by a line passing through the center and parallel to a side)? – Dan Li Sep 13 '23 at 13:26
  • 1
    My calculation gives me $4/9$. – gerw Sep 13 '23 at 13:38
  • @gerw, You are right, 4/9 is correct. I made a mistake. – Dan Li Sep 13 '23 at 13:52
  • 1
    @DanLi. It is not uncommon for the volume of geometric objects in high-dimensional spaces ($n\to\infty$) to approach zero. Think that the volume of an $n$-dimensional simplex with fixed side length tends to zero when $n\to\infty$. On regard to your thoughts, I think that you are assuming that the convex set should be symmetric with respect to the centroid, which is false in general (@gerw provides an example of this). – Julian Sep 14 '23 at 17:56
  • @gerw, if it is an equilateral triangular pyramid, the minimum volume of the small part will be (3/4)^3=27/64. So for $n$ dimension the ratio is $(\frac{n}{n+1})^n$, and $\lim_{n\to\infty}(\frac{n}{n+1})^n=\frac{1}{e}$. – Dan Li Sep 24 '23 at 19:56

1 Answers1

1

This fact is a weaker version of Theorem 2 from Grünbaum, Branko, Partitions of mass-distributions and of convex bodies by hyperplanes, Pac. J. Math. 10, 1257-1261 (1960). ZBL0101.14603. Let me discuss the ideas of this proof.

Let $\operatorname{Vol}(K)$ denote the $n$-dimensional Lebesgue measure of the set $K\in\mathbb{R}^n$. To simplify notation, we denote $m_K(S)=\operatorname{Vol}(S\cap K)$, for all measurable subsets $S\in\mathbb{R}^n$. We define $$\mathcal{C}(K,\lambda)\equiv\{x\in\mathbb{R}^n: m_K(H_x)\geq\lambda m_K (K)\text{ for all halfspaces }H_x\text{ based at }x\}.$$

Note then that a sufficient condition to have your statement is that

Fact 1. $$0\in C(K,(n/(n+1))^n),$$

because in such a case $$\operatorname{Vol}\left(K\cap\underbrace{\{x\in\mathbb{R}^n: x^Tw\geq0\}}_{\equiv H_0(w)}\right)\geq\underbrace{\left(\frac{n}{n+1}\right)^n}_{\equiv\alpha_n}\operatorname{Vol}(K)\geq\frac{1}{e}\operatorname{Vol}(K)$$ for all $w\neq0$. Then, let us proceed showing fact 1 by contradiction. Therefore, there should exist $w\in\mathbb{R}^n$ such that $m_K(H_0(w))<\alpha_n m_K(K).$ Without loss of generality, we may assume that $w=(1,0,\dots,0).$ Let $H^\pm\equiv\{x\in\mathbb{R}^n:\pm x_1\geq0\}$. Therefore, the contradiction hypothesis is now $m_K(H^-)< \alpha_n m_K(K)$.

Now, in order to achieve a contradiction, we will use the spherical symetrization of $K$, that we will denote by $\hat K.$ This set is the union of the $(n-1)$-dimensional spheres obtained by taking for each hyperplane $L_t=\{x\in\mathbb{R}^n:x_1=t\}$ the sphere with center $(t,0,\dots,0)$ and $(n-1)$-dimensional volume equal to the one of $K\cap L_t.$ Note that by construction $\hat K$ is convex, $\int_{\hat K} x dx=0$ (the centroid of $\hat K$ is $0$, as well as the centroid of $K$), $m_K(H^-)=\operatorname{Vol}(H^-\cap\hat K)$ and $m_K(H^+)=\operatorname{Vol}(H^+\cap\hat K)$, because we are staking $(n-1)$-dimensional slices that have the same $(n-1)$-dimensional volume than the slices of $K$. Therefore,

$$\operatorname{Vol}(H^-\cap\hat K)<\alpha_n \operatorname{Vol}(\hat K),$$ and $0\not\in C(\hat K, \alpha_n).$ Now consider the hypercone $D^-$ with base $\hat K\cap L_0$ and vertex $(c,0,\dots,0)\in H^-$ cxhosen in soch a way that $\operatorname{Vol}(D^-)=\operatorname{Vol}(\hat K\cap H^-)$. The hypercone $D$ is defined by extending $D^-$ along its generators into $H^+$ in such a way that $\operatorname{Vol}(D\cap H^+)=\operatorname{Vol}(\hat K\cap H^+)$. Then, $x_1$-coordinate of the centroid of $D^-$ (respectively $D^+=D\cap H^+$) is no greater than the one of $\hat K^-=\hat K\cap H^-$ (respectively $\hat K^+=\hat K\cap H^+$). Then, the centroid of $D$ should be in $H^-$, and the hyperplane parallel to $L_0$ passing through this centroid divides $D$ in two parts in such a way that the part that contains the vertex has a volume smaller than $\alpha_n \operatorname{Vol}(D)$. Nevertheless, the centroid of an hypercone divides its height in a ratio of $1/n$, from where we get that the volume of this part is precisely $\alpha_n \operatorname{Vol}(D)$, from where we get the contradiction.

Julian
  • 418