Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a hypercube of width W, how can I figure out the maximum number of points I can place inside the hypercube such that each point is at least equal to or further than euclidean distance X away from each other.

My ultimate goal is to go backwards and be able to specify the max number of points and generate the required distance.

share|improve this question
    
Key word: (hyper)sphere-packing mathworld.wolfram.com/HyperspherePacking.html –  leonbloy Jul 7 '11 at 14:18
add comment

2 Answers

up vote 2 down vote accepted

The following construction may be useful. It is not guaranteed to be optimal, because there are border effects, shaping effects and such. IIRC the densest lattice packing is the $D_4$-lattice (our library wanted their copy of Conway & Sloane back, so I cannot check). Here's the description. Specify a scale parameter $d$. Select points with coordinates $d(n_1,n_2,n_3,n_4),$ where $n_1,n_2,n_3,n_4$ are integers subject to the constraint that their sum must be even. Then the closest distance between two such points is $X=\sqrt{2}d$. The number of points $N$ in your hypercube would then be $N\approx \frac12 \left(\frac Wd\right)^4$.

Caveats: I may remember some things wrong, and the $D_4$ lattice is optimal with respect to some other figure of merit. Also, for some choices of $X$ (particularly when $d$ is relatively large with respect to $W$) you may benefit from jiggling the points around a bit and/or rotating the lattice. If my basic recollection is correct, then I doubt you can win much by such tricks, so if this simple, relatively easy to implement construction is good enough for your purposes, you may consider using it.

In full generality your problem probably cannot be answered. I mean, if you specify $W$ and $X$ (resp. $N$), the answer to the question of best $N$ (resp. $X$) may be unknown (read: very difficult).

share|improve this answer
    
How did I read the problem to be 4D only? Well, Conway & Sloane is your friend for constructions in various dimensions. –  Jyrki Lahtonen Jul 8 '11 at 12:48
add comment

If two points are $X$ or more apart, and you put a hypersphere of radius $X/2$ around each, they don't intersect, so the volumes of these hyperspheres must add up to at most the volume of a hypercube of side $W+X$. That will give you a bound, maybe not a terribly good one. But if you type "packing spheres" into a search engine, you will probably find some good sites that discuss the problem in detail. I think you'll find there are a lot of open questions.

EDIT: By the way, everyone should bookmark David Eppstein's Geometry Junkyard, http://www.ics.uci.edu/~eppstein/junkyard/ From there it's just a few clicks to Erich's Packing Center, http://www2.stetson.edu/~efriedma/packing.html or to sphere-packing links at http://www.ics.uci.edu/~eppstein/junkyard/spherepack.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.