25
$\begingroup$

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$?

$\endgroup$
38
$\begingroup$

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.


      SeidelPolyhedron Figure from: Discrete and Computational Geometry. (Book link).
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$.

$\endgroup$
  • $\begingroup$ This is an interesting example but does not exactly answers the question, as the polyhedron is assumed to be homeomorphic to the sphere. $\endgroup$ – Benoît Kloeckner Jun 8 '14 at 14:38
  • 5
    $\begingroup$ @BenoîtKloeckner: That polyhedron is homeomorphic to a sphere. Those indentations do not go all the way through, but rather stop just short of penetrating to the other side. Admittedly, that is not obvious from the figure. $\endgroup$ – Joseph O'Rourke Jun 8 '14 at 14:40
  • $\begingroup$ Tried to clarify this point... $\endgroup$ – Joseph O'Rourke Jun 8 '14 at 14:46
  • 1
    $\begingroup$ I get it, nice! $\endgroup$ – Benoît Kloeckner Jun 8 '14 at 14:49
19
$\begingroup$

I have a simpler example and I see that its idea is similar to the above one.

Example of a polyhedron

Cut the vertices of a cube to form 8 small triangles and suppose the triangles are rigid but the faces are not. Then rotate the triangles, 4 of them clockwise and the rest counter-clockwise, in an alternating manner.

Animating the above example

The images are drawn using Geogebra 3D.

$\endgroup$
  • 2
    $\begingroup$ Nice animation! $\endgroup$ – Joseph O'Rourke Jun 12 '14 at 12:00
12
$\begingroup$

Note that the answer is yes in 2 dimensions, since any polygon can be triangulated (without adding additional vertices). Thus, every point in the interior sees at least 3 vertices of $P$.

One can attempt to do the same thing in 3 dimensions, but somewhat surprisingly there exist polyhedra that cannot be decomposed into tetrahedra (without adding additional vertices). See here, where they show that the problem of deciding if a 3-dimensional polyhedra can be decomposed into tetrahedra is NP-complete. The references in that paper might be helpful.

$\endgroup$
  • 2
    $\begingroup$ So, by taking a slice through the point, every point in the interior sees points in the $n-2$-skeleton. $\endgroup$ – Douglas Zare Jun 8 '14 at 16:33
3
$\begingroup$

Here's an orthogonal variation on Ali Khezeli's example, which T.S. Michael calls1 the octoplex. The point at the very center of the polyhedron is not visible to any vertex.


         
          (Figure by Emmely Rogers.)


1Michael, T.S. How to Guard an Art Gallery and other Discrete Mathematical Adventures. Baltimore: Johns Hopkins U Press, 2009. (JHU book link.)

$\endgroup$
2
$\begingroup$

It turns that given any convex compact nonplanar $X\subseteq\mathbb{R}^3$ its boundary ${\partial}X$ can be approximated arbitrarily closely (simultaneously in shape and surface area) by a polyhedron $P$ homeomorphic to $S^2$ whose set $N_P$ of points not visible from any of $P$ 's vertices has a boundary that likewise approximates $P$ and ${\partial}X$ in the sense that every point of ${\partial}N_P$ is within $\epsilon$ of some point of ${\partial}X$ and vice versa.

$\endgroup$

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.