[Solved]: Distribute objects in a cube so that they have maximum distance between each other

Problem Detail: 

I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure that each color assigned to an object is as different from any color on any other object as possible.

In RGB space, we have three planes, all with values between 0 and 255. In this cube $(0,0,0) / (255,255,255)$, I would like to distribute the $n$ colors so that there is as much distance between themselves and others as possible. An additional restriction is that $(0, 0, 0)$ and $(255, 255, 255)$ (or as close to them as possible) should be included in the $n$ colors, because I want to make sure that none of my $(n-2)$ objects takes either color because the background will probably be one of these colors.

Probably, $n$ (including black and while) will not be more than around 14.

Thanks in advance for any pointers on how to get these colors.

Asked By : Matt

Answered By : Patrick87

All colors will be on the surface of the RGB cube, unless I'm mistaken, for the same reason that all electrical charge appears on the surface of electrical conductors. This suggests the following method to determine colors:

• interpret the RGB color space as an XYZ Cartesian space;
• interpret candidate colors as charged particles, e.g., electrons;
• find the low-energy state of the system through e.g. simulated annealing;

For $n \sim 15$, a highly accurate simulation should be fairly quick; you could use a Runge Kutta technique, or even Euler's method with a small time step could probably do it (much easier to implement/understand). I might suggest the series "Numerical Recipes" for numerical integration/quadrature techniques of interest.

Once particles converge, you have the arrangement of colors by interpreting points as colors. Initially, particles can be arranged randomly on the cube's surface, with a little spacing (helps convergence and stability issues). Putting small groups on faces of the cube should work.

To avoid getting stuck in a local (rather than global) minimum, you can "pulse" some small random electric field after convergence and see whether the system goes back to the same configuration, or a different one. It's somewhat unlikely that randomly placed particles will do that in this scenario, but possible.

EDIT:

As pointed out in the comments, the assumption that optimal solutions should lie only on the surface probably doesn't hold for all geometries in the discrete case.

Fortunately, this has little bearing on the rest of the technique described above. Particles can be initially placed anywhere; just leave some room between pairs of particles for stability and covergence, and then iterate the system to convergence, then pulse a few times (possibly with increasing intensity) to see if you can get the system to converge to some different (possibly better) configuration.

Also note that I believe this method will maximize something like "(harmonic?) average distance between pairs of particles". If you want to maximize the minimum distance between pairs of particles, or some other average (geometric?) between pairs of particles, this may not give you the best solution.

In any event, I feel like this technique will give you an easy way to come up with good approximately-optimal sets of colors... getting actual "optimal" solutions is probably not required for your use-case. Naturally, if an exact and provably optimal solution is desired, numerical simulation is probably not the best way to go.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1399