12
$\begingroup$

Let $P$ be a (not necessarily convex or simply-connected) polyhedron, and $\gamma(t)$ a homotopy of $P$, i.e. a continuous displacement of the vertices of $P$ that keeps its faces planar.

I call $\gamma$ a shrinking if, for every $s\geq t$, $\gamma(s) \subset \gamma(t)$. That is, as $t$ increases more and more material is being "shaved" from $P$, without adding any new material.

For example, any convex polyhedron can be shrunk by moving its vertices along line segments towards the centroid.

Here is a shrinking of a polyhedral torus: enter image description here

Not every polyhedron can be shrunk; for instance in the right figure above the torus has shrunk to a zero-volume union of four line segments and no further displacement of the vertices is possible while keeping the polyhedron within that set.

There are examples of unshrinkable polyhedra of nonzero volume. For instance, consider this example inspired by the Schoenhardt polytope:

enter image description hereenter image description here

No shrinking of this polytope exists (every displacement of the vertices causes the polytope to leave the original volume). But even though this example has nonzero volume, one might still object that it is degenerate, i.e. $P$ is not equal to the closure of its interior.

Is there a characterization of when a polytope can be shrunk? (Can all "nondegenerate" polyhedra be shrunk?) How can one compute a shrinking?


EDIT: Responding to the request below to formalize the question more:

Start with a closed, oriented simplicial 2-complex $C$ with $n$ vertices that is locally homeomorphic to the disk. An embedding of $C$'s vertices, $V\in \mathbb{R}^{3n}$, defines an immersion $\partial P(C, V)$ of $C$ in $\mathbb{R}^3$.

Now I call the polyhedron $P(C,V)$ the set of points given by the union of $\partial P(C,V)$ and the points enclosed by $\partial P$.

(This definition requires the polyhedron to have triangular faces, and also doesn't bar polyhedra that self-intersect, but these issues don't change the essence of my question.)

I seek a nontrivial continuous function $\gamma: [0,1] \to \mathbb{R}^{3n}$ with $\gamma(0)=V$, and $P(C, \gamma(s)) \subset P(C, \gamma(t))$ whenever $s > t$.

$\endgroup$

2 Answers 2

3
$\begingroup$

I think one necessary condition is that each vertex must have a star-shaped link (i.e. there must be an interior point near the vertex that can see all the neighbors of the vertex). So for instance this allows your example of a non-shrinkable polygon to be greatly simplified; just take a pyramid over a non-star-shaped hexagon.

My guess is that for polyhedra for which each boundary component has the topology of a sphere this necessary condition is also sufficient — given an interior neighbor for each vertex you can choose a small offset amount for one face plane, and propagate the offsets from face to neighboring face in such a way as to make all the faces surrounding each vertex agree on how far the vertex should be offset towards its interior neighbor. But for non-spherical polyhedra, if you try to make these offset amounts agree with each other locally you will likely get nonlocal disagreements around non-shrinkable cycles on the polyhedron surface, so there will be some extra conditions that a non-spherical polyhedron will need to satisfy in order to be shrinkable.

Update: This was written assuming a different definition of shrinkage in which all vertices need to move to the interior of the polyhedron. In the actual statement of the problem, we only need to find a strict subset of the polyhedron, allowing parts of the boundary to stay fixed. So three star-shaped vertices on a face would prevent that face from moving, but we would need to fix all faces in the same way. Additionally, if the subset of faces that move does not contain any non-shrinkable cycles, we wouldn't necessarily have any problems making offset amounts agree with each other.

$\endgroup$
6
  • $\begingroup$ Interesting... I see that if you have a non-star-shaped vertex $v$, and fix all of $v$'s neighbors, it is impossible to shrink the polyhedron by moving $v$ alone. What's your intuition for why one can't shrink by moving $v$ and the neighbors? $\endgroup$ May 16, 2015 at 3:16
  • $\begingroup$ You defined it as a continuous shrinking process, right? Not a sudden move to somewhere interior. So $v$ has to be able to move instantaneously, and still be connected to neighbors that from its point of view haven't moved much. $\endgroup$ May 16, 2015 at 5:47
  • $\begingroup$ Aah, I understand: if the vertices adjacent to $v$ are $w_i$ and $B_i$ are small neighborhoods around $w_i$, then not only is $v$ the only point in a small neighborhood that can see all the $w_i$, it's also the only point in a small neighborhood that can see at least one point in each $B_i$. So it is impossible to shrink while moving $v$ even if the $w_i$ also move. $\endgroup$ May 16, 2015 at 7:42
  • $\begingroup$ So if $P$ has one non-star-shaped vertex it may still be possible to shrink $P$ by moving everything else; if all vertices are non-star-shaped, though, $P$ must be unshrinkable. $\endgroup$ May 16, 2015 at 7:45
  • 1
    $\begingroup$ FYI this answer has been cited in our paper: cs.columbia.edu/cg/nested-cages/… $\endgroup$ Oct 3, 2015 at 18:03
5
$\begingroup$

Are you familiar with the straight skeleton? It is most used with 2D polygons, but there have been extensions to 3D polyhedra. In 2D, edges move inward, and the vertices track along the "straight skeleton." In 3D, the faces are offset inward. There are subtle issues for arbitrary polyhedra, but they were resolved in the paper below.

Barequet, Gill, David Eppstein, Michael T. Goodrich, and Amir Vaxman. "Straight skeletons of three-dimensional polyhedra." Algorithms-ESA 2008. Springer Berlin Heidelberg, 2008. 148-160. (PDF download.)


VaxmanSK
(Above, the tetrahedron is a cavity inside the cube.)


There is a video explaining the 3D straight skeleton.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the pointer -- offsetting the faces does work in 2D, and in 3D for some cases, such as when all vertices have valence three. But in general, offsetting the faces changes the combinatorial type of the polyhedron $\endgroup$ May 15, 2015 at 16:24
  • $\begingroup$ Yes, the combinatorial type changes. It would help me if you could articulate your definition of exactly what you seek. (Your polyhedral torus example can be viewed as shrinking via the straight skeleton.) $\endgroup$ May 15, 2015 at 19:07
  • $\begingroup$ Certainly; I've attempted to define the problem more precisely above. Please let me know if parts are still unclear. $\endgroup$ May 15, 2015 at 21:35
  • $\begingroup$ @EtienneVouga: Thank you, that helps. $\endgroup$ May 16, 2015 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.