1
$\begingroup$

I know that quadtree could be used in collision detection. But most articles I found are related with quadtree construction and retrieval. I wonder if there are some circumstances which involve both a great number of insert and remove operations? If any, please list out the papers.

I am planning to develop the quadtree structure which supports fast insertion and deletion. I am wondering whether there are applications that need this feature.

Improve this question
$\endgroup$
5
  • $\begingroup$ What's your motivation for asking? What research have you done? $\endgroup$
    – D.W. ♦
    Aug 12 '15 at 4:00
  • $\begingroup$ @D.W. I am planning to develop the quadtree structure which supports fast insertion and deletion, while I do not know whether there are applications which need it. $\endgroup$
    – chain ro
    Aug 12 '15 at 4:08
  • $\begingroup$ OK. What research have you done? Have you started by investigating whether any of the applications listed in Wikipedia's list of common uses of quadtrees needs fast insertion/deletion? That seems like a basic starting point that you should explore before asking here. We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. See cs.stackexchange.com/help/how-to-ask. $\endgroup$
    – D.W. ♦
    Aug 12 '15 at 4:12
  • $\begingroup$ Incidentally, I believe the standard algorithm is already fast ($O(\lg n)$ under some reasonable assumptions about "balance"), so there are limits to how much faster it could be. You might already be aware of this. $\endgroup$
    – D.W. ♦
    Aug 12 '15 at 4:16
  • $\begingroup$ @D.W. Thanks! Sorry that I have not noticed the guide yet. $\endgroup$
    – chain ro
    Aug 12 '15 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.