Ideas on finding a minimal covering?

Question

A friend and I were thinking about how to approach the following problem:

Given a 3-dimensional cubic grid ([1,7] x [1,7] x [1,7]) in discrete coordinates (343 points total), we want to pick a small number of points in the grid so that *every* point in the grid can be reached from one of the chosen points by traveling along at most 3 unit line segments.

In other words, we want a minimal covering of the grid by octahedra of radius 3. Each octahedron can cover 25 points, so it's clear that at least 14 will be required, but I suspect that overlap will increase that number by a few.

Any ideas about how to go about solving this?

Curt: ah, you're right, 25 is actually the number of points up to distance 2 away from a point. I think that should be 63, making the lower bound not 14 but a mere 6.

All 8 corners have to be covered separately, of course, unless a point is chosen at the midpoint of the grid's edge, but that seems a bit too wasteful of coverage.

Answer 1

I'm not sure I understand your figure of 25, given that the there would seem to be 26 on a cube surrounding your center even before you reach out 2 and 3 "levels" away.

Anyhow, the solving strategy I'd try first is simply to pick 8 points as far away from the corners as I can get while still covering the corners, then see what's left uncovered near the center of each side, then see what's left over near the center of the whole grid.