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.

What is the maximum number of points that can be within a unit cube (no points on cube vertices, faces, or edges) such that no two points are within 1 of each other?

I'm asking because I'm creating a grid-based acceleration structure for a program I'm writing, and I need to know how much memory to give each "cube".

share|improve this question
    
This problem appears to translate pretty trivially to sphere packing in 3d space (given your minimum radius between points). See en.wikipedia.org/wiki/Kepler_conjecture; it seems a efficient method would have your points in the cannonball stack arrangement. –  occulus Jun 12 '13 at 10:32
add comment

1 Answer

I believe the maximum is six points. An example of six such points plus the distances between them is shown below:

a= (0.001953125,0.001953125,0.5) b= (0.875,0.001953125,0.001953125) c= (0.001953125,0.875,0.001953125) d= (0.998046875,0.998046875,0.5) e= (0.125,0.998046875,0.998046875) f= (0.998046875,0.125,0.998046875) ab= 1.00511767253617 ac= 1.00511767253617 ad= 1.40868929064508 ae= 1.12044365406458 af= 1.12044365406458 ba= 1.00511767253617 bc= 1.23467473121245 bd= 1.12044365406458 be= 1.59590272810661 bf= 1.01117942309147 ca= 1.00511767253617 cb= 1.23467473121245 cd= 1.12044365406458 ce= 1.01117942309147 cf= 1.59590272810661 da= 1.40868929064508 db= 1.12044365406458 dc= 1.12044365406458 de= 1.00511767253617 df= 1.00511767253617 ea= 1.12044365406458 eb= 1.59590272810661 ec= 1.01117942309147 ed= 1.00511767253617 ef= 1.23467473121245 fa= 1.12044365406458 fb= 1.01117942309147 fc= 1.59590272810661 fd= 1.00511767253617 fe= 1.23467473121245

As an explanation: I used the back of an envelope to develop the principle, then an excel spreadsheet to produce the numbers. For principle: if you start with points a=(0,0,0),b=(1,0,0),c=(0,1,0) and d=(1,1,1),e=(1,0,1), f=(0,1,1) then they are all exactly 1 unit apart and all on the vertices, so fail on all requirements. Now push the points a and d along the z axis (away from the vertices) by distance p. Then push points b,c, along the x or y axis (so they move closer to a) by distance p^3, (similarly with points e and f so they move closer to point d). Finally move each point distance p^9 along each axis as required to move it away from the edge it is on. The points will all be inside the cube so meet the first specification. I can't do Latex, so it is hard to explain why the distances are always greater than 1, but in principle, each distance_squared will be of the form 1+u*p^m-v*p^n(+/-)other terms in p to higher powers. By choosing p, p^3 and p^9 it is always the case that the index m is smaller than the index n, so for a sufficiently small p, the positive term u*p^m will always be greater than the largest negative term v*p^n (and any other -ve terms) so the length^2 will be greater than 1. In practice it works for p in the range (0+..0.52+) and I chose 0.5 because it produced a nice symmetry. The solution would probably also work for increments p, p^(2+delta), and maybe p^(4+3*delta), fore any delta > 0 but I haven't checked that. As to my belief that 6 is the maximum, that is just a guess (it is definitely less than 8) so unless someone can find a solution with 7 points...

share|improve this answer
1  
Mathematica? :-) More generally, how did you get to this answer? –  Marnix Klooster Jun 12 '13 at 4:24
    
See edited bit in the answer - I need to learn Latex. –  MikeFee Jun 12 '13 at 4:49
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.