Kinetic Data Structures

Intro

Kinetic data structures (KDS) are discrete data structures evolving over time. The basic idea is to verify the data structure at each increment and if this fails update it.

As per usual mathematicians brought in some machinery to generalize this - they can't help themselves.

Tessellation

Consider an example of the convex hull tessellation of points changing position in time. In 2D when the tessellation changes the winding breaks. So for each triangle we can test if its winding has changed and then update the mesh if this has happened.

So updating is linear complexity plus the cost of updating the underlying data structure.

This test uses the determinant test to see if the triangles winding has changed.

The use of half spaces can also detect changes in the geometric relations. This test generalizes (can't help myself either) to any dimension. The simplex can not see any of its points if the surface half spaces point outwards. If this is broken then the mesh is broken.

For the linked simplex mesh the details of re-tessellation are non trivial. For example my first idea was to delete a point and then reinsert it into the mesh.

If the reinsert is done in constant time (and why not because we know the area where the point is being deleted, assuming that the mesh change is small) then the update algorithm is linear in time.

If somehow we know which points would break then the update could be made constant in time.