0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$ – Gamow Aug 7 '20 at 11:49
  • $\begingroup$ @Gamow thanks a lot for the direction $\endgroup$ – Marc Grec Aug 7 '20 at 13:13

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.