4
$\begingroup$

Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am interested in finding a minimal (or at least reasonably small) and preferably "nice" decomposition of $X$ into interior-disjoint subsets $X_j$ that are themselves unions of translated unit cubes and such that each $X_j$ is completely determined by its coordinate projections (or perhaps better if possible, $n-1$ projections that are not coordinate-aligned). By "nice" above, I do not require that the $X_j$ are connected.

For example, consider $X$ given by a union of 21 cubes corresponding to a 3x3x3 array of cubes with the middle cube of each "face" removed. (Note that projections cannot distinguish $X$ from a large cube.) Certainly taking $X_1$ and $X_3$ to be "tori" of 8 cubes and $X_2$ to be a "checkerboard" of 5 cubes will work: is there a valid decomposition of this $X$ into two subsets?

Has this (or any sufficiently similar question) been studied? I would also be interested in any generalization or variation for decompositions of a wider class of bodies (e.g., pure simplicial complexes), or references on this sort of problem.

(The closest thing I could find on MO is Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always circular? but I would guess that there are more relevant questions/answers out there: pointers in this regard would also be appreciated.)

**

I believe there is a valid decomposition of size 2 for the 21-cube example if non-coordinate aligned projections are used. Here is an (updated for more symmetry) picture that to me suggests as much (each row of panels corresponds to one of the 2 subsets):

enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ In $\mathbb{R}^3$, these objects are called polycubes. (Polycubes are also known as lattice animals.) Certainly you can slice with unit-separated parallel planes between the cubes, and the slabs between adjacent planes are determined by their projections. But perhaps this is not "reasonably small"? $\endgroup$
    – Joseph O'Rourke
    Commented May 23, 2016 at 16:41
  • $\begingroup$ @JosephO'Rourke -- Clearly such a "slab" decomposition always works (and is in fact what I gave as the 3-element decomposition in my example) but I am interested in doing better. Suppose that one has a voxel approximation to a smooth body and a limit is taken in which the voxels shrink, with $N$ voxels on a side. Is it generically possible to use $O(1)$ instead of $O(N)$ subsets in the decomposition? $\endgroup$
    – Steve Huntsman
    Commented May 23, 2016 at 17:22
  • 1
    $\begingroup$ @JosephO'Rourke - glancing at your linked MO question, I would guess that something like the following could lead to a very good heuristic: fix a number $J$ for the desired size of the decomposition, and assign cubes to one of the subsets uniformly at random. Then somehow measure the number of "failures" or "uncertainties" in cube assignments for $n-1$ random projections and perturb either $J$ or the subsets depending on the size of this number. $\endgroup$
    – Steve Huntsman
    Commented May 23, 2016 at 17:42
  • $\begingroup$ Cool idea, Steve, to use random assignments, and then adjust. $\endgroup$
    – Joseph O'Rourke
    Commented May 23, 2016 at 17:59

0

Reset to default

You must log in to answer this question.