Looking for an efficient structure for checking which circles enclose a point

Question

I have a large set of overlapping circles each at a random location with a specific radius.

type Circle =
    struct 
      val x: float
      val y: float
      val radius: float
    end

Given a new point with type

type Point =
    struct
      val x: float
      val y: float
    end

I would like to know which circles in my set enclose the new point. A linear search is trivial. I'm looking for a structure that can hold the circles and return the enclosing circles with better than O(N) for the presented point.

Ideally the structure should be fast for insertion of new circles and removal of circles as well.

I would like to implement this in F# but ideas in any language are fine.

For your information I'm looking to implement

http://takisword.wordpress.com/2009/08/13/bowyerwatson-algorithm/

but it would be an O(N^2) if I use the naive approach of scanning all circles for every new point.

What about some sort of modified quadtree. Then you could probably do O(log n) — John Palmer, Apr 04 '13 at 08:46
Yeah but a quad tree is for points not overlapping geometric objects. I'm not sure how to proceed. — bradgonesurfing, Apr 04 '13 at 08:47
You could at least narrow things down to some small subset of the circles overlap a region. — John Palmer, Apr 04 '13 at 08:48
I put effort into this problem for spheres a while back, it turns out you can (or I could) only beat linear if the max radius is small compared to the coordinate range. Can you assert anything about the ranges? — agentp, Apr 04 '13 at 16:03
Yeah the circles are the circumcircles of a delaunay triangulation so in general they are limited in how many other circles overlap. — bradgonesurfing, Apr 04 '13 at 16:22
I think I might be looking for this http://en.wikipedia.org/wiki/R-tree — bradgonesurfing, Apr 04 '13 at 17:15
An an implementation in F# using bounding boxes. http://stackoverflow.com/questions/8066314/any-r-tree-implementation-in-f-or-c — bradgonesurfing, Apr 04 '13 at 17:32

score 2 · Answer 1 · answered Apr 04 '13 at 09:01

If we assume that circles are distributed over some rectangle with area 1 and the average area of a circle is a then a quadtree with m levels will leave you with an area with size 1/2^m. This leaves

O(Na/2^m)

as the expected number of circles left in the remaining area.

However, we have done O(log(m)) comparisons to get to this point. This leaves the total number of comparisons as

O(log(m)) + O(N/2^m)

The second term will be constant if log(m) is proportional to N.

This suggests that a quadtree can cut things down to O(log n)

score 2 · Answer 2 · answered Apr 04 '13 at 09:03

Quadtree is a structure for efficient plane search. You can use it to hold subdivision of the plane.

For example you can create quad tree with such properties: 1. Every cell of quadtree contains indices of circles, overlapping it. 2. Every cell does contain not more than K circles (for example 10) // may be broken 3. Height of tree is bounded by M (usually O(log n))

You can construct quadtree, by iterating overlapped cells, and if number of circles inside cell exceedes K, then subdivide that cell into four (if not exceeding max height). Also something should be considered in case of cell inside circles, because its subdivision is pointless.

When finding circles you should localise quadtree, then iterate through overlapping circles and find, those which contains point.

In case of sparse circle distribution search will be very efficient.

I have a bachelor thesis, where I adapted quadtree, for closest segment location, with expected time O(log n), I think similar approach could be used here

The circle distribution will be that the overlapping circles are the circumcircles of a delaunay triangulation. Does this make a difference. — bradgonesurfing, Apr 04 '13 at 14:31
@bradgonesurfing Why can't you locate at delaunay triangulation? I think having triangle at triangulation you could find containing circumcircles among circumcircles of faces, sharing points with your triangle. — kassak, Apr 04 '13 at 14:48
@bradgonesurfing Also I think your case not that bad for algorithm in answer. Maximal subdivision would be reached at vertices of triangulation of degree > K. But that is ok, near that vertices you could not do nothing better than iterate throug incident circles =) — kassak, Apr 04 '13 at 14:57

score 1 · Answer 3 · answered Apr 04 '13 at 13:14

Actually you search for triangles whose circumcircles include the new point p. Thus your Delaunay triangulation is already the data structure you need: First search for the triangle t which includes p (google for 'delaunay walk'). The circumcircle of t certainly includes p. Then start from t and grow the (connected) area of triangles whose circumcircles include p.

Implementing it in a fast an reliable way is a lot of work. Unless you want to create a new library you may want to use an existing one. My approach for C++ is Fade2D [1] but there are also many others, it depends on your specific needs.

[1] http://www.geom.at/fade2d/html/

Looking for an efficient structure for checking which circles enclose a point

3 Answers3