Take the 2-minute tour ×

I'm designing a game with a multi-dimensional playing board, each dimension has the same length (an n-cube). Each of the dimensions wraps (think Asteroids). My goal is to place the pellets so they are as far apart from each other as possible, including wrapping.

I'm wondering if there is a general solution for where to place k pellets in n-dimensions to maximize this distance.

share|improve this question
"as far apart from each other as possible": is this measured by the minimum distance between pairs of points or something else? –  Henry Feb 2 '12 at 15:47
The way in which you "wrap" the edges will affect your space's topology. Identifying top with bottom, left with right, etc. will leave you with an n-dimensional torus. At this point your problem is to find the densest sphere packing in an n-torus. –  Bill Cook Feb 2 '12 at 15:55
@Henry: The goal is the maximize the minimum distance between any two pairs of points, using the regular Euclidean distance. Bill: The dimensions wrap onto themselves (as you say, top with bottom, etc), and each axis of the space is orthogonal. –  Korbin Reese Feb 2 '12 at 15:58
I believe results in coding theory can answer your question, but I am not familiar enough with that area to turn this hunch into a specific recommendation. One often wants to spread $k$ bit strings of length $n$ far apart for coding purposes. Wraparound is often incorporated. –  Joseph O'Rourke Feb 2 '12 at 21:16

Your Answer



Browse other questions tagged or ask your own question.