Efficient represention for growing circles in 2D space?

[DanWaterworth]

http://stackoverflow.com/questions/9031778/efficient-represention-for-growing-circles-in-2d-space

[akg]

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.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.

[ajuc → akg]

Well, growing 2d circles are just static sliced cones in 3d.

So maybe some 3d space partitioning technique will do.

EDIT: but I can't really think of any suitable for indexing big long cones. So it's no really useful idea :/

[mchouza]

You can try posting your question in http://cstheory.stackexchange.com/