Let $x_0,\dots,x_n$ be a collection of variable points in $\mathbb{R}^2$ and let $c>0$ be a fixed constant. Is there any way I could compute an upper bound of the volume of the region in $\mathbb{R}^{2(n+1)}$ consisting of all points where $$\|x_0\|+\sum_{i=0}^{n-1}\|x_i-x_{i+1}\|\leq c$$and $$\|x_i\|\leq 1$$ for each $i$?
-
$\begingroup$ There seem to be no variables: $x_0,\dots,x_n$ and $c$ are fixed. Or do you mean that $x_0,\dots,x_n$ are variable and only $c$ is fixed? $\endgroup$– Joseph O'RourkeJan 18, 2016 at 2:58
-
$\begingroup$ Yes, corrected. $\endgroup$– Peter GoncalvesJan 18, 2016 at 3:44
-
1$\begingroup$ The second set of conditions seems to indicate that the volume is bounded above by $\pi^{n+1}.$ $\endgroup$– Igor RivinJan 18, 2016 at 10:45
-
$\begingroup$ See the first answer to this question mathoverflow.net/questions/182729/… , which looks similar to the answer shown below although there is a $(2n)!$. $\endgroup$– Tom SolbergJan 18, 2016 at 23:31
1 Answer
Let $V$ be the volume of the configuration space that you describe in the question. I'll record here the two trivial upper bounds for $V$ arising from dropping either the second set of inequalities $\|x_i\|\leq 1$ or from dropping the first inequality. For $c$ sufficiently large or small, these bounds become tight, as I explain below.
Let $r_i=\|x_i-x_{i-1}\|$ for $i=0$ to $n$ with the convention that $x_{-1}=0$. Of course, $r_i\geq0$ for all $i$, so $\vec{r}=(r_0,\dots,r_n)\in\mathbb{R}^{n+1}$ must lie in the "nonnegative orthant" of $\mathbb{R}^{n+1}$.
Your first inequality states that:
$\sum_{i=0}^nr_i\leq c$.
This implies that $\vec{r}$ lies in an "orthogonal $(n+1)$-simplex" in $\mathbb{R}^{n+1}$ whose $n+2$ vertices consist of the $n+1$ vectors $(c,0,\dots,0)$, $(0,c,0,\dots,0)$, etc. as well as the origin $(0,\dots,0)$. (See e.g. the discussion here.) Let's call this simplex $S$.
In general the second set of inequalities $\|x_i\|\leq1$ do not play well with these $r_i$ variables.
However, note that
$$\|x_0\|+\|x_1-x_0\|+\cdots+\|x_{i}-x_{i-1}\|$$ $$\geq \|x_0+x_1-x_0+\cdots+x_i-x_{i-1}\|=\|x_i\|,$$
by the triangle inequality. We thus can see that
$$\|x_0\|\leq\|x_1\|\leq\cdots\|x_n\|\leq c.(*)$$
(At this point perhaps I should remark that the first inequality suggests that your linkage is a polygonal chain joining the origin in $\mathbb{R}^2$ $\rightarrow$ $x_0$ $\rightarrow$ $x_1$ $\cdots$ $x_n$ where the sum of the lengths at most $c$ and the second set of inequalities requires that all points $x_i$ lie within the unit disk.)
The above chain of inequalities $(*)$ implies that when $c\leq 1$, we lose nothing by dropping the second set of inequalities. In this case we can parametrize your configuration space by first fixing the $r_i$ variables so that $\vec{r}$ lies in $S$ and then picking a solution to the set of equations $\|x_i-x_{i-1}\|=r_i$.
Geometrically, your configuration space is then a bundle over $S$ where the fiber over the point $\vec{r}$ is a Cartesian product of $(n+1)$ circles with radii $r_0,\dots,r_n$ (i.e. the set of solutions to $\|x_i-x_{i-1}\|=r_i$). This has volume $(2\pi)^{n+1}\prod_{i=0}^nr_i$. Thus the total volume of the configuration space when $c\leq1$ is the following integral
$$I=(2\pi)^{n+1}\int_{S}\prod_{i=0}^n dr_ir_i.$$
We have $I=V$ for $c<1$ and $I\geq V$ in general. See the note below the line for a potential approach to computing $I$.
We can easily bound $I$ to get:
$$V\leq(2\pi)^{n+1}c^{2n+2}/(n+1)!,$$
since $c^{n+1}/(n+1)!$ is the volume of $S$ and $r_i\leq c$ for all $i$.
For $c$ sufficiently large one can do better with the even easier upper bound
$$V\leq \pi^{n+1},$$
which one gets by dropping your first inequality.
In fact, this silly bound becomes tight for $c\geq(2n+1)$. The right hand side is the maximum sum of the distances between the adjacent $x_i$ when they are constrained to lie within the unit disk of $\mathbb{R}^2$ -- place $x_{2i}$ at $(1,0)$ and $x_{2i-1}$ at $(-1,0)$ for $i\leq n/2$ so that $\|x_0\|=1$ and $\|x_i-x_{i-1}\|=2$ for $i=1$ to $n$.
Aside:
It may be possible to evaluate the integral $I$ more precisely, using techniques described in this nice answer of Igor Rivin to another MO question. See part II-1 of the notes by Baldoni, Berline and Vergne that he referenced.
I made an attempt below but as you can see, I did not get very far.
Explicitly, let us write for the vertices of $S$, $\vec{s}_{n+1}=(0,\dots,0)\in\mathbb{R}^{n+1}$ and $\vec{s}_i=(0,\dots,c,\dots,0)\in\mathbb{R}^{n+1}$ (with the $c$ in the $i+1$th coordinate) for $i=0$ to $n$. Note that the volume of $S$ is $\frac{c^{n+1}}{(n+1)!}$ as it is a corner of the hypercube $[0,c]^{n+1}$.
The key idea is that $\int_S r_0\cdots r_n dV$ (where $dV=\prod_{i=0}^n$ is the volume measure in $\mathbb{R}^{n+1}$) is equal to the coefficient of $\xi_0\cdots\xi_n$ in
$\int_S \exp\left(\langle\vec{\xi},\vec{r}\rangle\right) dV$.
(Where $\vec{\xi}=(\xi_0,\dots,\xi_n)$ and $\vec{r}=(r_0,\dots,r_n)$ lie in $\mathbb{R}^{n+1}$).
Then Brion's formula gives that $\int_S \exp\left(\langle\vec{\xi},\vec{r}\rangle\right) dV=(-1)^{n+1}(n+1)!(vol(S))\sum_{i=0}^{n+1}\frac{\exp(\langle\vec{\xi},\vec{s_i}\rangle)}{\prod_{j\neq i}\langle\vec{\xi},\vec{s_j}-\vec{s_i}\rangle}$.
The right hand side simplifies to
$(-c)^{n+1}\left(\sum_{i=0}^n\frac{\exp(c\xi_i)}{c^{n+1}\prod_{j\neq i}(\xi_j-\xi_i)}+\frac{1}{c^{n+1}\prod_{i=0}^n\xi_i}\right)=\left(\sum_{i=0}^n\frac{\exp(c\xi_i)}{\xi_i^{n+1}\prod_{j\neq i}(1-\xi_j/\xi_i)}+\frac{(-1)^{n+1}}{\prod_{i=0}^n\xi_i}\right)$.
Only the sum from $i=0$ to $n$ can contribute to the coefficient of $\xi_0\cdots\xi_n$. However, I was not immediately able to compute the relevant coefficient of $\frac{\exp(c\xi_i)}{\xi_i^{n+1}\prod_{j\neq i}(1-\xi_j/\xi_i)}$ in closed form.