Project: Dynamic Algorithms

Overview

The term dynamic algorithm refers to algorithms (or data structures) that permit changes to the data set whose properties they compute.  A closely related term "kinetic algorithms" refers to algorithms that compute a property of continuously moving objects.   For example, a dynamic convex hull algorithm maintains the convex hull of a data set that changes over time; a kinetic convex-hull algorithm computes the convex hull of a set of moving points.    The idea behind these algorithms is to maintain some structured information about the data so that the property of interest can be updated efficiently as the data changes.  Traditionally, these algorithms are designed on a problem-specific basis.  Using techniques developed in our work on self-adjusting computation, we have developed algorithms for various dynamic and kinetic problems,  including dynamic trees, dynamic and kinetic convex hulls, and dynamic and kinetic meshing.   In addition to reproducing some known results, using this approach, we have also been able to solve some open problems specifically on convex hull and meshes.  

Publications

See our publications.

Software

You can find download an implementation of our dynamic mesher.

People
Funding
  • This research is partially supported by funds from Intel Labs, Microsoft Research, and Jane Street Capital.