2026-08-03T23:57:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12175 2024-03-06T10:49:37Z ddc:004 open_access

Parallel Computation of Alpha Complexes for Biomolecules Masood, Talha Bin Ray, Tathagata Natarajan, Vijay Delaunay triangulation parallel algorithms biomolecules GPU 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Talha Bin Masood and Tathagata Ray and Vijay Natarajan 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.17 urn:nbn:de:0030-drops-121758 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode