<p>I have a set of points <span class="math-container">$C_i$</span> on a two dimensional plane and I want to find a point <span class="math-container">$P$</span> such that the maximum distance from <span class="math-container">$P$</span> to any of the points is minimised, i.e. minimise(max(<span class="math-container">$||P-C_i||$</span>)).</p>

<p>I've found that the centroid of <span class="math-container">$C_i$</span> gives a reasonable approximation, but does not find the optimal solution for <span class="math-container">$P$</span>. I've also tried a few other options like finding the centroid of the convex hull of <span class="math-container">$C_i$</span> and they have all produced comparable or worse results.</p>

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

CC BY-SA 4.0
2019-03-07T07:37:58.390Z
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.
DDobie
CC BY-SA 4.0
2019-03-07T07:55:28.390Z
https://en.wikipedia.org/wiki/Smallest-circle_problem
David Eppstein
CC BY-SA 4.0
2019-03-07T08:30:09.573Z
@DavidEppstein Perfect, that's exactly what I needed. Thanks a lot!
DDobie
<ds.algorithms>
Minimising the maximum distance to the centre of a cluster of points
DDobie
# Minimising the maximum distance to the centre of a cluster of points

(Asked by: username_0 on 2019-03-07)

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.

**Tags:** ds.algorithms
> **Comments:**
> **username_0**: 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.  
> **username_1**: https://en.wikipedia.org/wiki/Smallest-circle_problem  
> **username_0**: @DavidEppstein Perfect, that's exactly what I needed. Thanks a lot!  

---

## 0 answers

