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

<p>Is there a more common term for these combinatorial designs than unit hypercube encodings? </p>

<p>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.</p>

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

<p>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: <a href="http://www.win.tue.nl/~aeb/codes/binary-1.html" rel="nofollow noreferrer">http://www.win.tue.nl/~aeb/codes/binary-1.html</a></p>

<p>Also see, "Sphere Packings, Lattices, and Groups", <a href="http://www.springer.com/us/book/9780387985855" rel="nofollow noreferrer">http://www.springer.com/us/book/9780387985855</a>, 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.</p>

<p>SigGraph paper shows success in 2D with uniform sampling then walking each point towards the farthest, <a href="http://dl.acm.org/citation.cfm?id=2018345" rel="nofollow noreferrer">http://dl.acm.org/citation.cfm?id=2018345</a> </p>

CC BY-SA 3.0
2017-01-05T02:29:09.993Z
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.
D.W.
CC BY-SA 3.0
2017-01-05T18:02:05.940Z
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.
Chad Brewbaker
CC BY-SA 3.0
2017-01-05T18:37:37.087Z
One heuristic is farthest-point first clustering.  https://en.wikipedia.org/wiki/Farthest-first_traversal, https://en.wikipedia.org/wiki/Facility_location_problem#Algorithms  You might be able to prove that it achieves an approximation factor of 2.
D.W.
CC BY-SA 3.0
2017-01-05T18:50:23.323Z
Machine learning application where I need to encode a discrete unordered set into a vector of reals. If no tables of optimal designs exist I was gong to generate them using a spring force model, or use Z3 to find optimal designs within some epsilon. I was also going to look at designs of points on the surface of the unit hypersphere so hyperlane cutting methods can single out any point easily. The "one hot" encoding explodes the dimensionality far too much, https://www.quora.com/What-is-one-hot-encoding-and-when-is-it-used-in-data-science .
Chad Brewbaker
CC BY-SA 3.0
2017-01-05T19:52:52.713Z
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 https://en.wikipedia.org/wiki/Covering_number
Sasho Nikolov
CC BY-SA 3.0
2017-01-06T08:40:59.373Z
If instead of the hypercube you pack into a hypersphere, this is called a spherical code: https://en.wikipedia.org/wiki/Spherical_code
domotorp
CC BY-SA 3.0
2017-01-06T19:56:43.040Z
@SashoNikolov Thanks. Terry Tao (linked from wikipedia) has a good blog post on metric entropy: https://terrytao.wordpress.com/2014/03/19/metric-entropy-analogues-of-sum-set-theory/

Sadly I still can't find a table of $k$ point configurations in the unit hypercube that have near maximal r-seperation under the Euclidian distance metric.
Chad Brewbaker
<coding-theory><encoding>
Unit hypercube encodings
Chad Brewbaker
# Unit hypercube encodings

(Asked by: username_0 on 2017-01-05)

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>

**Tags:** coding-theory, encoding
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: One heuristic is farthest-point first clustering.  https://en.wikipedia.org/wiki/Farthest-first_traversal, https://en.wikipedia.org/wiki/Facility_location_problem#Algorithms  You might be able to prove that it achieves an approximation factor of 2.  
> **username_0**: Machine learning application where I need to encode a discrete unordered set into a vector of reals. If no tables of optimal designs exist I was gong to generate them using a spring force model, or use Z3 to find optimal designs within some epsilon. I was also going to look at designs of points on the surface of the unit hypersphere so hyperlane cutting methods can single out any point easily. The "one hot" encoding explodes the dimensionality far too much, https://www.quora.com/What-is-one-hot-encoding-and-when-is-it-used-in-data-science .  
> **username_2**: 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 https://en.wikipedia.org/wiki/Covering_number  
> **username_3**: If instead of the hypercube you pack into a hypersphere, this is called a spherical code: https://en.wikipedia.org/wiki/Spherical_code  
> **username_0**: @SashoNikolov Thanks. Terry Tao (linked from wikipedia) has a good blog post on metric entropy: https://terrytao.wordpress.com/2014/03/19/metric-entropy-analogues-of-sum-set-theory/  Sadly I still can't find a table of $k$ point configurations in the unit hypercube that have near maximal r-seperation under the Euclidian distance metric.  

---

## 0 answers

