1
$\begingroup$

Hi everyone. I need to pick a set of 65 points p(x,y,z) in a 3D space of 274625 points; as the set picked should provide the maximum possible minimum Hamming distance. (Consider the Hamming bound for sphere packing). Can anybody please help me with developing an algorithm for naming these 65 discrete points? Thanks, Tan

$\endgroup$
5
  • 2
    $\begingroup$ Have you read the FAQ, by any chance? $\endgroup$
    – David Roberts
    Aug 15, 2012 at 12:26
  • 2
    $\begingroup$ $274625 = 65^3$. If it's just a $65 \times 65 \times 65$ cube then the optimal packing of $65$ points with respect to Hamming distance is clear (see also D.Roberts' comment). $\endgroup$ Aug 15, 2012 at 12:30
  • 1
    $\begingroup$ If the $x,y,z$ are selected from the same set of 65 alternatives, then it seems clear to me that you want to use the 65 points on the 3D-diagonal, i.e. select the points of the form $(x,x,x)$. There are 65 of them, and the minimum Hamming distance between two points within this set is three. As any pair of points has Hamming distance at most three, this cannot be beaten. Or did you want to ask something else? $\endgroup$ Aug 15, 2012 at 13:50
  • $\begingroup$ Lahtonen Thanks for your response. I guess i couldn't express it clearly. There are 65^3 alternatives (not 65) to chose from, and I need to chose the best 65 which satisfy the max minimum Ham.Dist. x,y,z are the dimensions of each point (so 3D). $\endgroup$
    – Tan
    Aug 16, 2012 at 8:31
  • $\begingroup$ Elkies thanks for your response. I get your approach, but the space is not a cube, but a space of 65^3 points in their densest (assumingly a sphere) form. I need to find out the (or one of the) set of 65 points among all within this packing, satisfying the max.minimal ham.dist. So the members of the set should be 1)at a maximum distance from each other, and 2)reside in the packing. Hope this better explains my goal. I also checked the FAQ but couldn't really get D.Roberts' comment. $\endgroup$
    – Tan
    Aug 16, 2012 at 8:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.