Optimizing Voronoi-based quantifications for reaching interactive analysis of 3D localizations in the million range

Over the last decade, single-molecule localization microscopy (SMLM) has revolutionized cell biology, making it possible to monitor molecular organization and dynamics with spatial resolution of a few nanometers. Despite being a relatively recent field, SMLM has witnessed the development of dozens of analysis methods for problems as diverse as segmentation, clustering, tracking or colocalization. Among those, Voronoi-based methods have achieved a prominent position for 2D analysis as robust and efficient implementations were available for generating 2D Voronoi diagrams. Unfortunately, this was not the case for 3D Voronoi diagrams, and existing methods were therefore extremely time-consuming. In this work, we present a new hybrid CPU-GPU algorithm for the rapid generation of 3D Voronoi diagrams. Voro3D allows creating Voronoi diagrams of datasets composed of millions of localizations in minutes, making any Voronoi-based analysis method such as SR-Tesseler accessible to life scientists wanting to quantify 3D datasets. In addition, we also improve ClusterVisu, a Voronoi-based clustering method using Monte-Carlo simulations, by demonstrating that those costly simulations can be correctly approximated by a customized gamma probability distribution function