I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)).

I've found that the centroid of $C_i$ gives a reasonable approximation, but does not find the optimal solution for $P$. I've also tried a few other options like finding the centroid of the convex hull of $C_i$ and they have all produced comparable or worse results.

I've come to the realisation that there's almost certainly not an analytic solution to my case, so I'm looking for an algorithm that would be faster than just doing a grid search around the area near the centroid.

  • $\begingroup$ This is not an assignment problem.I'm an astrophysicist trying to optimise our observing strategy for observing galaxies that are near one another on the sky. It's also not a trivial problem - I've asked a few of my colleagues around the department and none have come up with a better solution than using the centroid or brute forcing via grid search. $\endgroup$ – DDobie Mar 7 at 7:37
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Smallest-circle_problem $\endgroup$ – David Eppstein Mar 7 at 7:55
  • $\begingroup$ @DavidEppstein Perfect, that's exactly what I needed. Thanks a lot! $\endgroup$ – DDobie Mar 7 at 8:30

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.