Of course, closely related is NP-completeness and undecidability of packing and tiling with non-square shapes and no matching rules. See e.g. mathoverflow.net/questions/344559/…

Done. Regarding your first remark, I think the point is that a triangular bipyramid will have one more degree of freedom than a quadrilateral pyramid because of the extra constraint that the four points on the quadrilateral faces be coplanar.

You can also get the same answer from the vertex coordinates: 3v before rotation (3), translation (3) and scaling (1).

@YaakovBaruch Maybe because like the wireframe CM, the vertex CM can also be shifted to an arbitrary position in the polyhedron with arbitrarily small effect on the higher dimensional CMs and on the polyhedron itself.

Beside the fact that the locally efficient packing structures suggested by the regular tetrahedron and the regular icosahedron cannot be extended to the entire space (as pointed out by the comments above), it also seems like you made a mistake in calculating the volume ratio associated with these structures. The fraction of a regular tetrahedron covered by balls centered on its vertices is 77.96% (this is known as the Rogers bound). The fraction of the regular icosahedron covered by balls centered at its vertices and its center is 75.47%.

I think the same argument should rule out a solution in the case of the dodecahedron too. That is, I don't think you can deform the dodcehadron into the GSD without a vertex passing through the plane of a neighboring face.

On the other question's comment thread Sam Nead asked whether you can invert a cube following the same rules. I think the answer is no: take a face F and a vertex V not on that face, then V has to pass the plane spanned by F at some point. When it does, then the two vertices sharing a face with V and two vertices of F must also lie on the same plane. And by the same argument so must the last cube vertex, so the cube is no longer 3-dimensional.

The reduction in my comment above should also work with minor modifications for the problem in your "further question" about minimum union.

I think a similar maximum intersection problem for subsets of the cyclic group under translations would be reducible to your problem (e.g. take the convex hull of the unit disk with $\{((1+h)\cos 2 \pi i/N, (1+h)\sin 2 \pi i/N): i \in A\}$ with very small h for each subset A). Then I think the greedy method fails e.g. for {1, 3, 20, 40, 60}, {2, 4, 20, 40, 60} and {1, 2, 3, 4}.

For reflection symmetric convex planar shapes, I would guess at least one of these pentagon tilings is a counter example: commons.wikimedia.org/wiki/File:P5-type4_p4g.png commons.wikimedia.org/wiki/File:P5-type3_p3m1.png commons.wikimedia.org/wiki/File:P5-type5_p6m.png

@NandakumarR That's right. If orientation of all units is the same then an affine transformation makes the packing into a sphere packing so can't have larger density than fcc. The paper I referenced shows that even ellipsoids that are nearly spherical can pack more densely than spheres.

Does this answer your question? Fast turn-around times [YK: automatically generated comment after voting to close as duplicate]