In this question we are only interested in convex polyhedra in the Euclidean space $\mathbb R^3$.

Polyhedra $P$ and $P'$ are said to be combinatorially equivalent iff there is a bijection between them (denoted here as $X\mapsto X'$) preserving the number of vertices, edges and faces and their relations (i.e. edge $E$ connects vertices $A$ and $B$ and separates faces $G$ and $H$ in $P$ iff edge $E'$ connects vertices $A'$ and $B'$ and separates faces $G'$ and $H'$ in $P'$). Note that we ignore possible chirality, and thus every polyhedron is combinatorially equivalent to its mirror image.

Recall that a subset $S$ of $\mathbb R^3$ is dense iff there is a point from $S$ in every neighborhood of every point of $\mathbb R^3$. For example, the set of all points with rational coordinates is dense.

Question: Is it true that for every dense subset $S$ and every polyhedron $P$ there is a combinatorially equivalent polyhedron whose all vertices belong to $S$?

  • 2
    $\begingroup$ It's kinda obvious for me that it is always possible to find a combinatorially equalent skeleton, but I have doubts about faces can always be made planar. $\endgroup$ – Vladimir Reshetnikov Feb 19 '16 at 19:47
  • $\begingroup$ Is there some obvious counterexample that tells us, that $S = \mathbb Z^3$ doesn't work? It seems to me that it might be enough and if that's the case, your question follows from this in a straightforward fashion. $\endgroup$ – Stefan Mesken Feb 19 '16 at 19:50
  • $\begingroup$ @Stefan $\mathbb Z^3$ is not dense in $\mathbb R^3$ $\endgroup$ – Vladimir Reshetnikov Feb 19 '16 at 20:11
  • $\begingroup$ Sure, but it seems to me that your claim might hold for $S = \mathbb Z^3$ and if one can prove that, the result for dense subsets follows easily. $\endgroup$ – Stefan Mesken Feb 19 '16 at 23:50
  • 1
    $\begingroup$ @Stefan Thanks. In your (deleted) answer you mentioned that by adding additional vertices any polyhedron can be transformed into a polyhedron with only triangular faces. You further assumed that those vertices can be safely removed later, after we "snap vertices to grid", restoring combinatorial properties of the original polyhedron. I think there is a problem with this step. If we started with a quadrilateral face, then after the transformation its 4 vertices might be not coplanar anymore, so they cannot become the vertices of a quadrilateral face in the transformed polyhedron. $\endgroup$ – Vladimir Reshetnikov Feb 21 '16 at 2:26

Your comment guided me onto the right track.

Claim. There is a dense subset $S \subseteq \mathbb R^3$ that doesn't contain $4$ distinct, coplanar points.

Proof. Fix a countable basis $\mathcal B = \{ O_n \mid n \in \mathbb N \}$ for the topology of $\mathbb R^3$ not containing $\emptyset$ as an element. We recursively construct a sequence $(S_n \mid n \in \mathbb N_0)$ such that for all $m,n \in \mathbb N_0$ with $m < n$

  • $S_m$ is finite,
  • $S_m \subseteq S_n$,
  • if $0 < m$, then $S_m \cap O_m \neq \emptyset$,
  • no $3$ distinct points of $S_m$ are colinear and
  • no $4$ distinct points of $S_m$ are coplanar.

If we manage to construct such a sequence, then $S = \bigcup \{ S_n \mid n \in \mathbb N_0 \}$ is countable, dense and doesn't contain $4$ distinct coplanar points. Towards this end let $S_0$ be any set of $4$ points that are not coplanar and such that no $3$ points of $S_0$ are colinear (e.g. $S_0 = \{(0,0,0), (1,0,0), (0,1,0), (0,0,1) \}$).

Given $S_n$ let $[S_n]^3$ be the set of all subsets of $S_n$ that contain precisely $3$ distinct points. Since no $3$ points of $S_n$ are colinear, any $s \in [S_n]^3$ spans a two dimensional, affine subspace of $\mathbb R^3$ which we denote by $P_s$. Let $[S_n]^2$ be the set of all subset of $S_n$ that contain precisely $2$ distinct points. For each $s \in [S_n]^2$ let $L_s$ be the affine line spanned by $s$. Let $X = \bigcup \{ P_s \mid s \in [S_n]^3 \} \cup \bigcup \{ L_s \mid s \in [S_n]^2 \}$. Since $X$ is a finite union of sets with Lebesgue measure $0$, we know that $X$ has Lebesgue measure $0$. In particular, this yields $O_n \setminus X \neq \emptyset$. Choosing some $s_n \in O_n \setminus X$, we let $S_{n+1} = S_n \cup \{s_n\}$. $\square$

If $S$ is as in the claim, there is no polyhedra with vertices in $S$ that is combinatorially equivalent to the 'unit cube'. So your question indeed has a negative answer - contrary to my initial instinct.


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.