# Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$

Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D.

Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ running time that can find the point set $Q \subseteq P$ containing those points of $P$ that are inside the circle with center $(a,b)$ and radius $r$?

(That is, I want to find all points in $P$ with coordinates $(i,j)$ such that $(i-a)^2 + (j-b)^2 \leq r^2$.)

[I originally asked about a solution with running time $O(\log n)$, but as Pål GD correctly points out, the answer to that question was "not possible".]

• But the answer to the revised question is still "Obviously, no." You still have to look at all the points to see which ones are in the solution set and the solution set could very well be empty. – David Richerby Mar 8 '15 at 16:56
• Do you have the luxury to first index $P$ in an offline stage? – Tolga Birdal Apr 28 '16 at 20:46

A better question is probably an output-sensitive version of the problem: Can you solve it in $O(\log n + |S|)$ where $S$ is the solution. That is, logarithmic in the input, and linear in the output.
• But it's obviously not possible in time $O(\log n + |S|)$, since the answer could be $S=\emptyset$, which you'd have to compute in time $O(\log n)$, which can't be done. Also, your answer appears to be just an endorsement of my answer, plus a suggestion of how to improve the question. That should be an upvote and a comment, not an answer. – David Richerby Mar 8 '15 at 17:01
Obviously not. You must inspect all the points and, on a classical, deterministic computer, you can't possibly look at $n$ points in only $O(\log n)$ time.
Note that this answer applies equally to the original question (is it possible in $\log n$ time?) and the revised one (is it possible in $|Q|+\log n$ time?). The answer could well be $Q=\emptyset$, but you can't figure that out in time $o(n)$.