dynamic data structures?

Erik Demaine edemaine at mit.edu
Sat Nov 24 18:33:03 PST 2001

On Thu, 15 Nov 2001, Biggi wrote:

> I am looking for all kinds of hierarchical dynamic data structures
> (and even not-so-hierarchical).
> By "dynamic" I mean a scenario where *all* objects (points, lines, etc.)
> move from frame to frame, but they move only by a small amount.
> Right now I don't have a particular problem/application in mind,
> so I am interested in all kinds of datastructures/algorithms that
> work efficient in such a "dynamic" setting.
> I would be happy if you could suggest any "must's", or give me
> pointers or names.

What you describe is closely related to if not the same as
what are called *kinetic data structures*.  You might try a websearch
with that phrase to find some relevant papers.  In particular there has
been interesting work on collision detection by kinetic data structures
in the past few years.

Erik Demaine  |  edemaine at mit.edu  |  http://db.uwaterloo.ca/~eddemain/

The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.

More information about the Compgeom-announce mailing list