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.

  • $\begingroup$ 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... $\endgroup$ – Joseph O'Rourke Oct 24 '11 at 15:27
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 24 '11 at 15:55
  • $\begingroup$ 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...) $\endgroup$ – Dima Pasechnik Oct 24 '11 at 18:23
  • $\begingroup$ I've edited the question to clarify this issue. $\endgroup$ – Dima Pasechnik Oct 24 '11 at 18:27
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 2
    $\begingroup$ 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? $\endgroup$ – David Eppstein Oct 24 '11 at 6:01
  • $\begingroup$ 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? $\endgroup$ – Dima Pasechnik Oct 24 '11 at 6:17
  • $\begingroup$ @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. $\endgroup$ – Igor Pak Oct 24 '11 at 6:19
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 24 '11 at 6:36
  • $\begingroup$ Oh, right... Not sure how to fix that. $\endgroup$ – Igor Pak Oct 24 '11 at 7:41

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.