<p>Your algorithm is correct.  If the best circle contains one point, your post-processing step will find it.  If the best circle contains two or more points, then there is a way to shift it around so it contains the same set of points and also two of them are on the perimeter; thus, in this case your algorithm will also find it.</p>

<p>There may be other algorithms that are even faster, but your algorithm shows that the problem can be solved in <span class="math-container">$O(n^2)$</span> time.</p>

CC BY-SA 4.0
2019-01-28T03:18:41.553Z
2019-01-28T03:18:41.553Z
D.W.
<p><a href="https://i.sstatic.net/bqYXR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bqYXR.png" alt="Visualisation of problem"></a></p>

<p>Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points. </p>

<p>I tried solving it by taking each pair of points and if it is possible, generate the two circles that pass trough those two points and have radius r. 
<a href="https://i.sstatic.net/sDWaR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/sDWaR.png" alt="Kinda like this"></a> </p>

<p>Here I found 2 possible circles that have points a and b on their perimeter with radius 2. One circle contains most points so that would be the solution of this problem.</p>

<p>However, I am not sure that this works. One easy counter example is when we have only one point. No pairs can be generated so no circles can be generated. In my code, I just added a circle for every point in addition to my circle generating nonsense from before. But that also fails to give me the correct result.</p>

<p>How do I really go about solving this?</p>

CC BY-SA 4.0
2019-01-27T20:14:40.233Z
This is a well-studied problem in computational geometry. You may for instance start reading the paper by Mark de Berg, Sergio Cabello, Sariel Har-Peled:
"Covering Many or Few Points with Unit Disks", Theory Comput. Syst. 45(3): 446-469 (2009), and follow some of the references there.
Gamow
CC BY-SA 4.0
2019-02-27T04:14:31.167Z
@Gamow that reference focuses on the harder problem of using $m$ circles to cover the max number of points, and mentions that $m=1$ is solvable in $O(n^2)$ time, as D.W.'s solution points out the OP's solution is.
JimN
<computational-geometry>
Select circle with given radius that contains most points
user51847
# Select circle with given radius that contains most points

(Asked by: username_0 on 2019-01-27)

[![Visualisation of problem](https://i.sstatic.net/bqYXR.png)](https://i.sstatic.net/bqYXR.png)

Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points.

I tried solving it by taking each pair of points and if it is possible, generate the two circles that pass trough those two points and have radius r.
[![Kinda like this](https://i.sstatic.net/sDWaR.png)](https://i.sstatic.net/sDWaR.png)

Here I found 2 possible circles that have points a and b on their perimeter with radius 2. One circle contains most points so that would be the solution of this problem.

However, I am not sure that this works. One easy counter example is when we have only one point. No pairs can be generated so no circles can be generated. In my code, I just added a circle for every point in addition to my circle generating nonsense from before. But that also fails to give me the correct result.

How do I really go about solving this?

**Tags:** computational-geometry

> **Comments:**
> **username_1**: This is a well-studied problem in computational geometry. You may for instance start reading the paper by Mark de Berg, Sergio Cabello, Sariel Har-Peled: "Covering Many or Few Points with Unit Disks", Theory Comput. Syst. 45(3): 446-469 (2009), and follow some of the references there.  
> **username_2**: @username_1 that reference focuses on the harder problem of using $m$ circles to cover the max number of points, and mentions that $m=1$ is solvable in $O(n^2)$ time, as username_3's solution points out the OP's solution is.  

---

## 1 answers

### Answer by username_3 on 2019-01-28. Score: 2

Your algorithm is correct. If the best circle contains one point, your post-processing step will find it. If the best circle contains two or more points, then there is a way to shift it around so it contains the same set of points and also two of them are on the perimeter; thus, in this case your algorithm will also find it.

There may be other algorithms that are even faster, but your algorithm shows that the problem can be solved in $O(n^2)$ time.


---

