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?
2007-11-23
15:45:00
·
1 answers
·
asked by
gremlinn007
2