Let $\mathbf{S}$ be a $m\times n$ matrix, with $m < n$. We define a subdimensional polytope as the space of $n$-dimensional vectors $\mathbf{x}$ that satisfy the following equation:


subject to the inequalities:


where $\mathbf{a}$ and $\mathbf{b}$ are $n$-dimensional vectors.

Denote by $\Omega$ this space of solutions. The projection of $\Omega$ over the $i$'th coordinate ($0\le i\le n$) is the function:

$$f_{k}\left(x_{k}\right)=\int\delta\left(\mathbf{S}\cdot\mathbf{x}\right)\prod_{i\ne k}\mathrm{d}x_{i}$$

where the integral goes through all the values of $x_i$ for all $i\ne k, 1\le i \le n$, and $\delta(\mathbf{y})$ is the $m$-dimensional Dirac's delta function, given by:


where $\delta(y_j)$ are ordinary one-variable Dirac's delta functions.

I understand that the exact computation of $f_{k}\left(x_{k}\right)$ is NP-hard. But I was wondering if something can be said about its form. I have the intuition that $f_{k}\left(x_{k}\right)$ should be concave, or at least have zero or one maximum. Can you prove this? What other properties $f_{k}\left(x_{k}\right)$ satisfies in general?

  • 1
    $\begingroup$ The words you're looking for are "Brunn-Minkowski theorem". If $S$ is full rank, that is, the section volumes you are taking are $(n-m-1)$-dimensional, then $f_k^{1/(n-m-1)}$ is concave. $\endgroup$ – Yoav Kallus Apr 10 '14 at 13:28
  • $\begingroup$ What about other properties of $f$? Is it a piecewise polynomial? Or something else? $\endgroup$ – becko May 4 '15 at 21:15
  • $\begingroup$ take a look at my revised answer. $\endgroup$ – Yoav Kallus May 5 '15 at 0:56

Assuming that $S$ is full rank, let $u$ be some unit vector not orthogonal to the null space of $S$, and let $\Omega_t =\lbrace x-t u~:~x\in\Omega,~ (x-tu)\cdot u = 0\rbrace$. then you are interested in the $(n-m-1)$-dimensional volumes $f(t)=|\Omega_t|$. Note that convexity of $\Omega$ implies that for $0\le\lambda\le1$, and $t$, $t'$ such that $\Omega_t$, $\Omega_{t'}$ are non-empty, $\lambda\Omega_t+(1-\lambda)\Omega_{t'}\subseteq\Omega_{\lambda t+(1-\lambda) t'}$. By the Brunn-Minkowski theorem we then have $$f(\lambda t+(1-\lambda) t')^{1/(n-m-1)}\ge|\lambda\Omega_t+(1-\lambda)\Omega_{t'}|^{1/(n-m-1)}\ge \lambda f(t)^{1/(n-m-1)}+(1-\lambda)f(t')^{1/(n-m-1)}\text.$$

EDIT: strange to see you came to check the answer one year later, but to answer your further question: yes, $f(t)$ is piecewise polynomial of degree at most $n-m-1$. Between values of $t$ corresponding to vertices, say $t_0$ and $t_1$, the cross section takes the form $\Omega_t = \frac{t-t_0}{t_1-t_0} \Omega_{t_1} + \frac{t_1-t}{t_1-t_0} \Omega_{t_0}$. That the volume is a polynomial in $t$ follows from Steiner's formula (see https://en.wikipedia.org/wiki/Mixed_volume).

  • $\begingroup$ +1 Thanks for pointing out the Brunn-Minkowski theorem, I did not know about it. $\endgroup$ – becko May 4 '15 at 21:15

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.