3
$\begingroup$

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$?

$\endgroup$
  • $\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'Rourke Jan 18 '16 at 2:58
  • $\begingroup$ Yes, corrected. $\endgroup$ – Peter Goncalves Jan 18 '16 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 Rivin Jan 18 '16 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 Solberg Jan 18 '16 at 23:31
4
$\begingroup$

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.

$\endgroup$

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.