Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More precisely, does the entire open segment between $X$ and some other vertex lie in the interior of $P$?
Visibility of Vertices in Polyhedra – Combinatorics and Metric Geometry
co.combinatoricsdiscrete geometrymg.metric-geometrypolyhedra
Related Solutions
Wonderful images, Edmund! :-)
A net $P$ can fold to a polyhedron iff there exists what I called in the book you cite an Alexandrov gluing, which is
an identification of its boundary points that satisfies the three conditions of Alexandrov's theorem [the subject of a recent MO question]: (1) The identifications (or "gluings'') close up the perimeter of $P$ without gaps or overlaps; (2) The resulting surface is homeomorphic to a sphere; and (3) Identifications result in $\le 2 \pi$ surface angle glued at every point. Under these three conditions, Alexandrov's theorem guarantees that the folding produces a convex polyhedron, unique once the gluing is specified.
Let me quote two results from the book, informally, the first quite disappointingly negative, the second compensatingly positive:
Theorem 25.1.2 (p.382): The probability that a random net of $n$ vertices can fold to a convex polyhedron goes to $0$ as $n \to \infty$.
Theorem 25.1.4 (p.383): Every convex polygon folds to an uncountably infinite variety of incongruent convex polyhedra.
In particular, for example, a square folds to an infinite number of convex polyhedra, whose space consists of six interlocked continuua, as detailed in our book (Fig.25.43,p.416).
The exact question you pose—Which nets can fold to convex polyhedra?—remains open. Although if you give me a specific net, we have an algorithm that will produce all the convex polyhedra to which it may fold. But note my emphasis on "convex," an adjective you left out in your question. That is Open Problem 25.1 in our book (p.384), on which topic I have written a separate note subsequent to the book's publication: "On Folding a Polygon to a Polyhedron." In a nutshell: every polygon folds to some (generally) nonconvex polyhedron, by a result of Burago and Zalgaller. But their proof is complex enough that I have no understanding what that polyhedron might look like.
Aside from the paper I cite above, you may be interested in this result:
Four of the five Platonic solids may be "unzipped" and "rezipped" to be doubly covered
parallelograms (which may conveniently be placed in your wallet!). See this MSE question for
the (difficult to find) icosahedron net [below]. The holdout here is the
dodecahedron, whose 43,380 edge unfoldings each may only fold back to the dodecahedron.
Adding a "margin" around a polyhedron is computing the offset polyhedron, which is already a difficult problem in 2D; e.g., the CGAL manual, Chapter 23. Here is a paper on offsets in 3D:
Charlie Wang, Dinesh Manocha "GPU-based Offset Surface Computation Using Point Samples," ACM Solid and Physical Modeling, 2012. (Author web page.)
Offsets of filigree model (3rd): positive (1st, 2nd), negative (4th).
But there has been considerable work on collision detection between polyhedra,
as this is a key computation for the graphics community.
For example, here is a snapshot from a video showing a computation of two colliding knots,
each composed of 37,000 triangles:
Video: Interactive Continuous Collision Detection for Non-Convex Polyhedra
Their paper is here:
Zhang, Xinyu, Minkyoung Lee, and Young J. Kim. "Interactive continuous collision detection for non-convex polyhedra." The Visual Computer 22.9-11 (2006): 749-760. (Springer link).
Here is an analogous 2008 paper by Jiménez and Segura:
"Collision detection between complex polyhedra." Computers & Graphics. Volume 32, Issue 4, August 2008, Pages 402–411. (Elsevier link).
If you want to concentrate specifically on polyhedron-polyhedron intersection detection, this problem has been studied since the classic 1980's paper by Dobkin and Kirpatrick (which is mentioned in Chapter 7 of my book):
"Fast detection of polyhedral intersection." 1983. (Elsevier link)
For example, this paper shows that the quadratic feature-vs-feature naive algorithm (which you mention) can actually be made linear in practice:
Ming C. Lin , Dinesh Manocha , Madhav K. Ponamgi. "Fast Algorithms for Penetration and Contact Determination Between Non-Convex Polyhedral Models." IEEE Int. Conf. on Robotics and Automation. 1994. (CiteSeer link).
In summary, I wouldn't plunge in and write collision-detection code without first exploring some of this literature, and investigating some of the existing software libraries, such as SWIFT at UNC.
Best Answer
There are many points in the interior of this polyhedron, constructed (independently) by Raimund Seidel and Bill Thurston, that see no vertices. Interior regions are cubical spaces with "beams" from the indentations passing above and below, left and right, fore and aft. Standing in one of these cubical cells, you are surrounded by these beams and can see little else.
The indentations visible are not holes, in that they do not go all the way through, but rather stop just short of penetrating to the other side. So the three back faces of the surrounding cube—obscured in this view—are in fact square faces of the cube. Thus $P$ is indeed homeomorphic to a sphere.
To follow Tony Huynh's point: This polyhedron $P$ cannot be tetrahedralized, i.e., it cannot be partitioned into tetrahedra all of whose corners are vertices of $P$.