2
$\begingroup$

How can we chose to place $k$ points in $[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized?

Is there a more common term for these combinatorial designs than unit hypercube encodings?

Example: For $d=2$ and $k=3$ we could have the points (0.23,0.33), (0.24,0.37), and (0.94, 0.81). The first two points are closest, and this design is far from optimal.

One could also think of this as a Voronoi diagram in the unit hypercube where the minimum distance between any two centroids is maximized.

Here is a the discrete analogue where we force ourselves to use only the value zero or one in each dimension, and Hamming instead of Euclidian distance: http://www.win.tue.nl/~aeb/codes/binary-1.html

Also see, "Sphere Packings, Lattices, and Groups", http://www.springer.com/us/book/9780387985855, which covers dense packings in $R^{n}$, but not packings of points into the unit hypercube from what I can see. In our case the hyperspheres would only be required to have their center point in the unit cube.

SigGraph paper shows success in 2D with uniform sampling then walking each point towards the farthest, http://dl.acm.org/citation.cfm?id=2018345

Improve this question
$\endgroup$
  • 5
    $\begingroup$ What are the restrictions on the $k$ points? How do they have to be related to the $n$ numbers provided as input? Are you trying to pick a subset of the $k$ numbers? And when you say "distance between any two points", do you mean "distance between any two of the $k$ selected points"? This might be the factory location problem, depending on what you mean, and it might be solvable with dynamic programming, again depending on what you mean. Can you edit the question to clarify? Also, what does this have to do with a hypercube? It sounds like your points are all in 1 dimension only. $\endgroup$ – D.W. Jan 5 '17 at 2:29
  • $\begingroup$ No restriction other than all $k$ points must be in the unit hypercube, an $n$ length vector with entries between zero and one. We want to maximize the minimum distance between any two points. (The closest pair of points are as far away as possible). Think of it a floating point valued coding scheme. I want to jitter points without them becoming too close to tell apart. $\endgroup$ – Chad Brewbaker Jan 5 '17 at 18:02
  • $\begingroup$ One heuristic is farthest-point first clustering. en.wikipedia.org/wiki/Farthest-first_traversal, en.wikipedia.org/wiki/Facility_location_problem#Algorithms You might be able to prove that it achieves an approximation factor of 2. $\endgroup$ – D.W. Jan 5 '17 at 18:37
  • 1
    $\begingroup$ If the minimum distance is $\delta$, this is called a $\delta$-separated set (in the unit hypercube). The tradeoff between $\delta$ and $k$ determines the metric entropy of the hypercube. See en.wikipedia.org/wiki/Covering_number $\endgroup$ – Sasho Nikolov Jan 5 '17 at 19:52
  • 1
    $\begingroup$ If instead of the hypercube you pack into a hypersphere, this is called a spherical code: en.wikipedia.org/wiki/Spherical_code $\endgroup$ – domotorp Jan 6 '17 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.