PowerBin: fast adaptive data binning with Centroidal Power Diagrams
Michele Cappellari · Monthly Notices of the Royal Astronomical Society · 2025
ABSTRACT Adaptive binning is a crucial step in the analysis of large astronomical data sets, such as those from integral-field spectroscopy, to ensure a sufficient signal-to-noise ratio ($\mathcal {S/N}$) for reliable model fitting. However, the widely used Voronoi-binning method and its variants suffer from two key limitations: they scale poorly with data size, often as $\mathcal {O}(N^2)$, creating a computational bottleneck for modern surveys, and they can produce undesirable non-convex or disconnected bins. I introduce PowerBin, a new algorithm that overcomes these issues. I frame the binning problem within the theory of optimal transport, for which the solution is a Centroidal Power Diagram (CPD), guaranteeing convex bins. Instead of formal CPD solvers, which are unstable with real data, I develop a fast and robust heuristic based on a physical analogy of packed soap bubbles. This method reliably enforces capacity constraints even for non-additive measures like $\mathcal {S/N}$ with correlated noise. I also present a new bin-accretion algorithm with $\mathcal {O}(N\log N)$ complexity, removing the previous bottleneck. The combined PowerBin algorithm scales as $\mathcal {O}(N\log N)$, making it about two orders of magnitude faster than previous methods on million-pixel data sets. I demonstrate its performance on a range of simulated and real data, showing it produces high-quality, convex tessellations with excellent $\mathcal {S/N}$ uniformity. The public python implementation provides a fast, robust, and scalable tool for the analysis of modern astronomical data.