CODEWITHSUNDEEP
javascriptoptimizationd3.jssimulationforce-layout
VividD
VividD

Reputation: 10536

10 points within unit circle - finding optimal distribution with D3 force layout?

Related to some packing problems, following problem arose:

Distribute 10 points within a square of sides 1, so that minimal distance between them is maximized.

With the help of D3 force layout simulation, or any other method, please provide example of such distribution, with graphical representation of square and points, and value of minimal distance between points for such distribution.

The answer with distribution with largest minimal distance wins the "answer badge"! :)

(This problem so far to my knowledge couldn't be solved by pure mathematics, so I am coming here for valuable and desperately needed help regarding simulations etc.)

Upvotes: 2

Views: 221

Answers (1)

Lars Kotthoff
Lars Kotthoff

Reputation: 109232

TL;DR One optimal solution is as follows:

[{x: 0,       y: 0},
 {x: 0,       y: 0.22222},
 {x: 0,       y: 0.44444},
 {x: 0,       y: 0.66667},
 {x: 0,       y: 0.88889},
 {x: 0.11111, y: 1},
 {x: 0.33333, y: 1},
 {x: 0.55556, y: 1},
 {x: 0.77778, y: 1},
 {x: 1,       y: 1}]

Long explanation: You can solve this problem as a mixed integer program (although the name is slightly misleading in this case as there are no integers). The basic model is very simple:

dists

where P is the set of points. The individual points need to be constrained to lie within the unit square:

sq

The objective is then:

obj

There are many equivalent solutions for this problem, you can for example get another solution from one solution by rotating the square. To make solving it easier, we can break some of the symmetries by imposing an order on the points: the coordinates of each point must be at least as high as the ones of its predecessor.

symm

This means that we can now use Manhattan distance instead of Euclidean and don't have to worry about negative numbers when computing the difference between coordinates, which removes the nasty squares:

dists

Input the model into your favourite MIP system and out comes a solution like the above with smallest Manhattan distance between points at 0.22222. Note that, as I've mentioned, you can rotate the square to get a different, but equivalent solution.

Upvotes: 1

Related Questions