If you have a large domain with a large number of N circles, you could try using a B-Tree like approach. Basically partitioning your domain in a N-Tree (instead

If you have a large domain with a large number of N circles, you could try using a B-Tree like approach. Basically partitioning your domain in a N-Tree (instead of a traditional quad-tree). The wide branching factor per node will give you a shallower tree that's more efficient if you are doing lots of updates to the data-structure. You can also rid yourself of pointers to do really fast traversals through your N-Tree using an approach like (http://www.matmidia.mat.puc-rio.br/tomlew/publication_page.php?pubkey=fastdualoctree_sgp http://www.matmidia.mat.puc-rio.br/tomlew/publication_page.p...). Lewiner et. al. talk about oct-trees there, but it could be generalized. I have some code that implements such a data-structure in 3D (should be easily modifiable to 2D). I can mail you the source if you are interested.