<p>Given <span class="math-container">$n$</span> circles all with radius <span class="math-container">$r$</span> and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions.</p>
<p>The simple approach would be to iterate through each circle and then apply the good old circle equation, that is: check whether the distance between the center of the circle and the point is less than the radius of the circle. One query would be of complexity <span class="math-container">$O(n)$</span>. Is there a faster algorithm?</p>

CC BY-SA 4.0
2020-08-07T11:49:41.470Z
The term you are looking for is "range search", or more precisely "dynamic range search".  This area has been very active in the 1980s and 1990s, and there are hundreds of papers that you may want to study. (These papers will also teach you how to properly formulate your question, so that the number of queries, number of insertions, number of deletions show up in the time complexity.)
Gamow
CC BY-SA 4.0
2020-08-07T13:13:57.933Z
@Gamow thanks a lot for the direction
Marc Grec
<computational-geometry>
What is the best way to find circles that contain a given point (in 2D)?
Marc Grec
# What is the best way to find circles that contain a given point (in 2D)?

(Asked by: username_0 on 2020-08-07)

Given $n$ circles all with radius $r$ and one point on a 2D plane, what is the best algorithm to find all circles that contain the given point. The circles and the point can change their positions.

The simple approach would be to iterate through each circle and then apply the good old circle equation, that is: check whether the distance between the center of the circle and the point is less than the radius of the circle. One query would be of complexity $O(n)$. Is there a faster algorithm?

**Tags:** computational-geometry

> **Comments:**
> **username_1**: The term you are looking for is "range search", or more precisely "dynamic range search".  This area has been very active in the 1980s and 1990s, and there are hundreds of papers that you may want to study. (These papers will also teach you how to properly formulate your question, so that the number of queries, number of insertions, number of deletions show up in the time complexity.)  
> **username_0**: @username_1 thanks a lot for the direction  

---

## 0 answers

