3D Restricted Kinetic Alpha-Complex – Københavns Universitet

3D Restricted Kinetic Alpha-Complex

Master’s defence by Desiree Malene Schreyer Jørgensen


This thesis introduces a new kinetic algorithm which maintains the Delaunay triangulation and alpha -complex of a point set where moving vertices are restricted to rotate around a fixed axis. Rotational vertex movement resembles atomic rotation around joints in proteins. Certificates for the Delaunay triangulation and alpha -complex are often violated by vertex movement. Based on the geometry of the problem, update conditions are derived and their polynomial complexity is analysed. To assess the performance of the restricted kinetic alpha-complex, two additional methods are implemented and a comparison study is performed based on five experiments. Even though the restricted kinetic alpha -complex takes longer to initialize, it shows potential for increasing point set sizes and number of rotating vertices. Experiments show that performance is highly affected by a numerical method used to compute update conditions for tetrahedra and an analytical solution potentially halves the running time.

Eksaminator: Pawel Winter

Censor: Jesper Larsen, DTU