Let $A$ and $B$ be origin-centered centrosymmetric polyhedra in $\mathbb{R}^3$: "for every point $(x, y, z)$ [...] there is an indistinguishable point $(-x, -y, -z)$." Say that $A$ and $B$ are threadable (my terminology) iff there is a scaling and rotation of $B$ to $B'$ such that (a) Every vertex of $A$ is exterior to $B'$, and (b) Every vertex of $B'$ is exterior to $A$. (I am exploring this notion of "threadability" as a measure of shape similarity.)

Two examples. (1) For $A$ a cube (blue) and $B$ a cuboctahedron (red), $(A,B)$ is threadable, e.g.:

Note that $A$ and $B$ are not duals; for duals, threadability is obvious.

(2) For $A$ a truncated icosahedron (red) and $B$ a vertically stretched pentagonal bipyramid (blue), I believe (but have not proved) it is not possible to scale & rotate $B$ to thread with $A$:

Computing whether or not $A$ and $B$ are threadable seems quite difficult, only achievable exactly via an $O(n^k)$ algoithm for $n$-vertex polyhedra, for $k$ an exponent that captures all the combinatorial possibilities. Perhaps $k=6$ would be necessary; I haven't thought that through carefully, but certainly it would a high computational complexity.

So, here, finally, is my question.

Q. Are there succinct sufficiency criteria for when a pair $(A,B)$ are guaranteed to be threadable?

What I have in mind here is something like this: "If the diameter/width ratio of $A$ and $B$ is approximately (or even: exactly) the same, then $A$ and $B$ are threadable." I don't believe this, but it gives the flavor of sufficiency conditions I seek. I have a sense that no such "simple" sufficiency conditions exist, because of the seeming dependence upon the micro- combinatorial structure of $A$ and $B$. But perhaps others can see more clearly through this thicket than I ... ?


It seems to me that two convex polyhedras are threadable if and only if (after scaling and rotation) they can be inscribed in the same strictly convex domain: If $A$ and $B$ are both inscribed in a strictly convex $D$ and two vertices do not meet, then $A$ and $B$ are threaded. If two vertices do coincide, then I guess that by moving $A$ or $B$ a little bit, one should obtain a threading. Conversely, given a threading of $A$ and $B$, one can take the convex hull of the vertices and it should be possible to make it strictly convex by blowing some air in it keeping the vertices fixed.

In particular, two polyhedras which can be inscribed in a sphere, or in a given ellipsoid, are threadable.

Is this the kind of condition that you are looking for?

| cite | improve this answer | |
  • $\begingroup$ Thanks for your cogent observations, Pierre! Your iff hypothesis is attractively plausible, and definitely a step beyond my own thoughts. $\endgroup$ – Joseph O'Rourke Feb 16 '14 at 2:43

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.