Kinetic Data Structures, Alpha Shapes and Betti Numbers – Københavns Universitet

Kinetic Data Structures, Alpha Shapes and Betti Numbers

Specialeforsvar ved Bo Gotthardt 

Kinetic data structures are a family of methods for solving problems involving moving objects. These methods use the continuity of the movement to develop more efficient algorithms and data structures rather than beginning from scratch at each time slot. Alpha shapes are geometric constructs representing objects at varying levels of coarseness to discern their underlying structure. Betti numbers associated with these alpha shapes can be used to characterize the topology of objects.

This thesis explores the idea of combining these concepts to observe how Betti numbers for a given object (for example a folding protein) changes as it moves kinetically while being represented by alpha shapes at different levels of coarseness.  Efficient kinetic data structures have been developed for Delaunay triangulations. They can be extended to alpha shapes. The topology changes of alpha shapes can then be studied using Betti numbers. To allow easier comparisons of Betti numbers the alpha shapes are filtered, such that only persistent topological changes and not small fluctuations are recorded. The theoretical performance characteristics of this new data structure are then compared with existing kinetic data structures.

Vejleder: Pawel Winter, DIKU
Censor: Jesper Larsen, DTU