Multiresolution Density-Equalizing Transformation for Scatterplots

Abstract

Scatterplots are a fundamental method for visual data analysis, but they often suffer from severe overplotting. Density-equalizing transformations can mitigate this by redistributing points to a uniform density. While Optimal Transport (OT) provides a robust mathematical framework for density equalization, existing numerical solvers are often computationally expensive, complex to implement, and difficult to adapt for specific application constraints. We present a scalable, multiresolution algorithm for scatterplot regularization that approaches the high-quality structural preservation of exact OT solvers. Our method constructs a displacement field by merging local, analytically solved 2×2 patch optimizations into a globally consistent mesh, repeating this process across multiple resolutions. We systematically evaluate local solvers, interpolation schemes, and scheduling strategies to balance transport cost, distortion errors, and runtime efficiency. The approach is straightforward to implement, supports local constraints, and generalizes mathematically to higher dimensions. Our efficient GPU implementation processes millions of points at interactive frame rates, significantly outperforming existing OT solvers. Quantitative and qualitative comparisons demonstrate that our method enhances uniformity while minimizing distortion, even under extreme density variations. We further demonstrate the method’s versatility through applications in constrained regularization, scatterplot gridification, and image contrast enhancement.