<p>See</p>

<p>Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", <em>Algorithmica</em> 41 (3): 147–157, <a href="http://doi.org/10.1007/s00453-004-1123-0">doi:10.1007/s00453-004-1123-0</a>.</p>

CC BY-SA 3.0
2017-01-19T07:31:54.000Z
2017-01-19T07:31:54.000Z
David Eppstein
<p>This is a N algorithm </p>

<ol>
<li>Given a set of N points P, draw a line that have at least M points at one side of it.</li>
<li>Name this subspace with at least M points as S</li>
<li>Pick a point that lays in S and call it center</li>
<li>Calculate the most distant point from center and call the distance as ray.</li>
</ol>

<p>There you go, you have circle with a center and a ray.</p>

<p>Obs. the way you chose the center is what determinates the size of your circle</p>

CC BY-SA 3.0
2017-01-18T10:38:40.763Z
Why the negative vote?
Henrique Almeida Marcomini
CC BY-SA 3.0
2017-01-18T11:54:54.523Z
There is no reason why this algorithm gives the circle with the smallest radius.
Sasho Nikolov
CC BY-SA 3.0
2017-01-17T12:09:33.903Z
2017-01-17T12:09:33.903Z
Henrique Almeida Marcomini
<p>You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?</p>

<p>algorithm for code</p>

<p>I searched for smallest enclosing circle problem but that was not for at least m?</p>

<ds.algorithms>
Circle graph algorithm
anu singh
# Circle graph algorithm

(Asked by: username_0 on 2017-01-17)

You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?

algorithm for code

I searched for smallest enclosing circle problem but that was not for at least m?

**Tags:** ds.algorithms

---

## 2 answers

### Answer by username_1 on 2017-01-19. Score: 5

See

Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", *Algorithmica* 41 (3): 147–157, [doi:10.1007/s00453-004-1123-0](http://doi.org/10.1007/s00453-004-1123-0).


---

### Answer by username_2 on 2017-01-17. Score: -5

This is a N algorithm

1. Given a set of N points P, draw a line that have at least M points at one side of it.
2. Name this subspace with at least M points as S
3. Pick a point that lays in S and call it center
4. Calculate the most distant point from center and call the distance as ray.

There you go, you have circle with a center and a ray.

Obs. the way you chose the center is what determinates the size of your circle

> **Comments:**
> **username_2**: Why the negative vote?  
> **username_3**: There is no reason why this algorithm gives the circle with the smallest radius.  

---

