2
$\begingroup$

I have a set of colored points (say 10 colors with 50 points of each color) in a 100-dimensional space. I want to choose one point of each color so that the 10 points are as close to each other as possible. A brute-force solution of testing every combination would require checking 50^10 possible sums. Is there a better way to solve this?

I thought maybe I could visit each black point and look for the nearest point of each of the remaining nine colors, and see which of those sums was the lowest. But I'm not sure this gives me an optimal solution.

Improve this question
$\endgroup$
1
  • $\begingroup$ One way that involves much fewer cases is the following: Group all the points in a large ball, and do a repeated random bisection to see if you can find a small to medium-sized ball that has a point of every color. If things aren't too bizarre, you will end up with a small feasible radius. Now with a ball twice that radius, for each of the fifty black points at the center and the subcollection of points in that ball, do a repeat or an exhaustive search on the hopefully much smaller search space. Gerhard "Divide And Conquer Really Works" Paseman, 2016.04.08. $\endgroup$
    – Gerhard Paseman
    Apr 8, 2016 at 16:55

0

Reset to default

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.