Arriving at any point in a polyhedron by continuously taking the arithmetic mean of the current point and any vertex of the polyhedron

Question

For example, if I have a cube with the vertices $(0, 0, 0)$, $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$, $(1, 1, 0)$, $(1, 0, 1)$, $(0, 1, 1)$, and $(1, 1, 1)$, and I want to get to $(0.75, 0.25, 0.25)$, I'd start at $(0, 0, 0)$, then average with $(1, 1, 1)$ to get $(0.5, 0.5, 0.5)$, and then average with $(1, 0, 0)$ to reach my target of $(0.75, 0.25, 0.25)$.

Is it:

1. Possible to get to every point inside of a polyhedron by averaging a current point and a vertex?
2. Easy to determine which point to choose next?
3. Easy to determine if a point is not reachable? i.e. outside the polyhedron or simply not reachable if 1 is not true?

Answer 1

So, first of all, your points are limited to ones with dyadic rational coordinates: points $(x,y,z) = (\frac{a}{2^k}, \frac{b}{2^k}, \frac{c}{2^k})$, where $a,b,c,k$ are integers. You'll never be able to get to $(\frac13, \frac13, \frac13)$, because you can't ever get a factor of $3$ into the denominator.

But maybe that's not very interesting, since you can get arbitrarily close to $(\frac13, \frac13, \frac13)$. In fact, for a cube, you can approximate any coordinate. This is not true for any polyhedron. For example, if your polyhedron is the tetrahedron, then you'll never be able to reach a point outside a 3D version of the Sierpinski triangle:

To see this, consider that if at one stage you're at an arbitrary point inside the tetrahedron, then in the next stage you can only be inside any of the $4$ scaled copies of the tetrahedron (scaled down by a factor of $\frac12$ fixing any of the $4$ vertices). Then in the second stage you can only be in one of the $4$ scaled copies of that region, and so on. Iterating this process produces the fractal above, and since we start within that fractal (at one of the $4$ corners) we can never leave.

As a general criterion, if in $d$ dimensions you have a polytope with fewer than $2^d$ vertices ($8$ vertices in $3$ dimensions) then the same argument shows that there are points in the polytope you can never get close to, because $k$ copies of the polytope, scaled by a factor of $\frac12$, have total volume $\frac{k}{2^d}$ of the original polytope. Of course, if $2^d$ or more vertices are poorly arranged, you might not be able to get everywhere either.

In the cube, there is a clear algorithm for approaching any point. The $x$-, $y$-, and $z$-coordinates are modified by averaging esssentially independently: at each step, we can average each coordinate with $0$ or with $1$. To do this strategically, look at the target point $(x,y,z) \in [0,1]^3$, write a $k$-bit binary representation of each of $x$, $y$, and $z$, and look at the bits from least to most significant to decide which point to average with.

For example, to get to $(0.75, 0.25, 0.25) = (0.11_2, 0.01_2, 0.01_2)$, we take the $\frac14$'s bits of all three coordinates (averaging with $(1,1,1)$) and then the $\frac12$'s bits of all three coordinates (averaging with $(1,0,0)$).

---

Suppose that, in general, we have a shape $S$ with vertices $v_1, v_2, \dots, v_k$. Let $S_1, S_2, \dots, S_k$ be copies of $S$, scaled down by a factor of $2$ through the point $v_1, v_2, \dots, v_k$ respectively.

Given a point $p^{(0)} = (x,y,z)$ that you want to get to (approximately or exactly), first find find some $S_i$ containing $(x,y,z)$. (If no such $S_i$ exists, then it's impossible to get to $(x,y,z)$.)

Then the strategy to get to $p^{(0)}$ is to:

• First, get to the point $p^{(1)} = 2p^{(0)} - v_i$ (again, exactly or approximately).
• Then, average $p^{(1)}$ with $v_i$, getting $\frac{p^{(1)}+ v_i}{2} = \frac{2p^{(0)}-v_i + v_i}{2} = p^{(0)}$.

We can iterate working backwards like this, with the logic "to get to $p^{(0)}$, we must get to $p^{(1)}$... to get to $p^{(1)}$, we must get to $p^{(2)}$... to get to $p^{(2)}$, we must get to $p^{(3)}$...". Eventually, one of three things will happen:

• The latest "goal" $p^{(i)}$ of this recursive procedure is one of the original vertices. This means that, starting at that vertex, you can perform the steps you found, in the reverse order, to get to the original target $p^{(0)}$.
• You decide that you're going to settle for an approximation. Then you can pick any starting vertex (but the closer to $p^{(i)}$, the better), and perform the steps you found, in the reverse order. This will get you close to the original target $p$; the longer you kept going, the closer you'll get.
• The point $p^{(i)}$ is not in $S_1 \cup S_2 \cup \dots \cup S_k$. In that case, you can't get even arbitrarily close to $p^{(0)}$.