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".
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...
