Is given point covered by any circle?

Question

Given $N$ circles and $Q$ points. What is the optimal solution for checking "if point is covered by any circle" for every point? The trivial solution would be $O(QN)$.

Answer 1

Let's suppose you have a spatial data structure that can be built over a set $S$ of points on the plane and expose the functions.

Build(S): Build and return the data structure storing all points in S
ds.Delete(q): Deletes point q from the set S
ds.Search(p): Return the closest point in S to point p

Now let's solve the problem backwards, instead of finding if a point is contained by some circle, lets find points for each circle the points it contains.

C: Set of circles
P: Set of points
ds := Build(P) # Build the data structure using points to be queried

for each circle c in C:
   do
      p = ds.Search(c.center)
      if p is inside circle c:
          ds.Delete(p)
   while (ds is not empty and one point was deleted)

All the deleted points from the data structure are the points that belongs to at least one circle, remaining points are not contained in any circle, otherwise they were being found when processing such circle.

Let $N:=|C|$ and $Q:=|P|$

The overall complexity of this algorithm is $$O(Build(Q) + (N + Q) \cdot Search(Q) + Q \cdot Delete(Q))$$

Here $Build(Q)$ is the complexity of building the set of $Q$ points, $Search(Q)$ is the complexity of searching for a point in a set of at most $Q$ points and $Delete(Q)$ is the complexity of deleting a point in a set of at most $Q$ points.

Notice that this cost is amortized, since after a point is recognized to be inside a circle it is deleted from the set.

One data structure that provides good balance for this operations is kd-tree, but I encourage you to find other spatial data structures that provides better complexity for your case.