Parallel Computation of Alpha Complexes for Biomolecules

Talha Bin Masood, Tathagata Ray and Vijay Natarajan. Computational Geometry : Theory and Applications, 90, 2020, 1 - 17. [Elsevier link] SoCG 2020: Symposium on Computational Geometry 2020, 17:1 - 17:16.

Abstract

The alpha complex, a subset of the Delaunay triangulation, has been extensively used as the underlying representation for biomolecular structures. We propose a
GPU-based parallel algorithm for the computation of the alpha complex, which exploits the knowledge of typical spatial distribution and sizes of atoms in a
biomolecule. Unlike existing methods, this algorithm does not require prior construction of the Delaunay triangulation. The algorithm computes the alpha
complex in two stages. The first stage proceeds in a bottom-up fashion and computes a superset of the edges, triangles, and tetrahedra belonging to the
alpha complex. The false positives from this estimation stage are removed in a subsequent pruning stage to obtain the correct alpha complex. Computational
experiments on several biomolecules demonstrate the superior performance of the algorithm, up to a factor of 50 when compared to existing methods that are
optimized for biomolecules.