# non-rigidity of interior points in polyhedral triangulations?

It's well-known that any compact polyhedron $P$ in $\mathbb{R}^n$ (we talk about piecewise-linear setting there, i.e. $P$ is a finite union of compact convex polytopes) can be triangulated into (geometric) simplices, although sometimes it is necessary to add "extra points" in $P$ to serve as vertices of simplices in the triangulation $\mathcal{T}$. E.g. Schönhardt polyhedron requires such extra points. (Here By $\mathcal{T}$ we mean a partition of $P$ into finitely many simplices $T\in\mathcal{T}$ --- more precisely, the interiors $int(T)$ of $T$'s do not intersect, and the closure of $\cup_{T\in\mathcal{T}}int(T)$ equals $P$. The vertices of $T$'s that are not vertices of $P$ are these "extra points" we talk about.)

It looks correct that one can always construct such a $\mathcal{T}$ so that each extra point in it is "non-rigid", i.e. it can be continuously moved inside an open subset of the face of minimal dimension it is inserted into, so that after such a deformation $\mathcal{T}$ remains a triangulation of $P$. Is this indeed correct, and can anyone point out a reference?

Added: A weaker form of the question: show that each extra poing in $\mathcal{T}$ is not prescribed, i.e. for any vertex $y$ of $\mathcal{T}$ which is not a vertex of $P$ there exists another triangulation of $P$ which does not have $y$ as a vertex. [This still suffices for our purpose, of showing that a part of certain kind of moment generating functions, for moments of a uniform measure supported on $P$, does not depend upon $\mathcal{T}$ ]. This is easy to see that $y$ lying in the interior of $P$ is not prescribed---one can directly construct a new triangulation not using $y$, by choosing the points of intersection of the edges on $y$ with a sufficiently small sphere around $y$ and re-triangulating new convex pieces without using $y$. But it is not obvious for $y$ lying in a proper face of $P$.

The answer for arbitrary polyhedra is no. If a 4-dimensional polyhedron has a 3-dimensional Schönhardt polyhedron as one of its faces, there will need to be a new vertex added somewhere within that face, which will not be free to move in an open set.

I believe that the answer is yes in 3d and yes to higher-dimensional polyhedra all of whose faces are already simplices, but I don't have a proof handy.

• David, could the new vertex be moved within a 3D open set, remaining within the 3-flat containing the face? I think so, at least under some interpretations of what constitutes the Schönhardt polyhedron. So perhaps the dimensionality of the open set needs mention... – Joseph O'Rourke Oct 24 '11 at 15:27
• Sure, but I think that if the points are allowed to move in a set of dimension equal to the lowest dimension of a face they belong to then the problem becomes trivial. – David Eppstein Oct 24 '11 at 15:55
• David, I don't mind my extra points moving in the minimal face they belong to. (I must have been more careful explaining what exactly was meant by an open set, sorry). Although I don't think it's so trivial, and that's why I asked (you start adding these extra points, and in this process your configuration gets progressively more rigid, so one needs to argue that there is always a room left, that one is not forced to add the next point to a prescribed position...) – Dima Pasechnik Oct 24 '11 at 18:23
• I've edited the question to clarify this issue. – Dima Pasechnik Oct 24 '11 at 18:27
• If you don't think it's trivial, perhaps you could give me an example of a triangulation that doesn't have the property you're looking for. Because as far as I can see it would always be true: if T is a triangulation, p is a vertex of T, and we move p within a relatively open set that is small enough to be bounded away from the opposite face of every simplex for which p is a vertex, then nothing can change combinatorially. – David Eppstein Oct 24 '11 at 22:09

I sort of doubt that this is written anywhere, but easy enough to prove directly. What you can do is take a very fine grid of points inside P. Perturb the points a bit to general position. Take a Delaunay triangulation of the vertices + these points. Because the Delaunay condition is open, the (even smaller) perturbations do not change a triangulation.

UPDATE: This arguments has a serious flaw (see below, thx David). It might still be fixable, but more work is needed.

• This needs some more detail if it is to work, I think. How do you guarantee that the Delaunay triangulation contains the faces of the original (possibly non-convex) polyhedron? – David Eppstein Oct 24 '11 at 6:01
• It seems that this only proves that there is a sequence of increasingly fine triangulated polytopes that approximate $P$. One still needs to show that an element of the sequence will refine $P$. Am I missing anything? – Dima Pasechnik Oct 24 '11 at 6:17
• @David - That's right. The standard way would be to make an even finer grid on the faces. All I am saying, is that the answer is most definitely positive. – Igor Pak Oct 24 '11 at 6:19
• But if you make a fine grid on the faces then the points you add to do this won't be free to move within an open set. – David Eppstein Oct 24 '11 at 6:36
• Oh, right... Not sure how to fix that. – Igor Pak Oct 24 '11 at 7:41