Currently i am studying Kinetic Data Structure thesis by Julian Basch. I am feeling stuck in some points. Are there any other resources to understand it properly ??

Edit:- I am very new to this data structure. Are there any blogs or video tutorial to understand an introduction to the concept which is a bit more in depth than the Wikipedia page.

  • 1
    $\begingroup$ (Does said thesis provide references?) $\endgroup$
    – greybeard
    Dec 8, 2021 at 6:10
  • $\begingroup$ This sounds pretty broad to me. Any community votes? Generally we're looking for specific questions. The resources might depend on what specifically you are trying to understand. $\endgroup$
    – D.W.
    Dec 8, 2021 at 8:27
  • $\begingroup$ This indeed sounds pretty broad. Perhaps the question can be changed to ask for an introduction to the concept that is a bit more in depth than the Wikipedia page. $\endgroup$
    – Discrete lizard
    Dec 8, 2021 at 8:46

1 Answer 1


First, we should consider a dynamic data structure. Such a data-structure keeps some sort of record during a sequence of modifications, usually insertions and deletions. The main idea is that this data structure only needs to do a little bit of work for each insertion and deletion, and therefore is more efficient than recomputing a static data structure after each modification.

A kinetic data structure is a variant on a dynamic data structure, where the modifications are of a geometrical nature. Often, the underlying data is a pointset in $\mathbb{R}^d$ and the modifications correspond to small movement of these points. Again, the idea is to ensure these small modifications only require a small number of changes in the data structure, such that we are much faster than recomputing the data structure after each movement step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.