2021/06/28 by Philip Claude Caplan, Caplan, Philip Claude
Computer Science · #Computational Engineering #Computational Geometry (cs.CG) #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #Finance #Topological and Geometric Data Analysis #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2106.14730
openalex publication_date 2021/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Efficient algorithms for solving optimal transport problems are important for measuring and optimizing distances between functions. In the L2 semi-discrete context, this problem consists of finding a map from a continuous density function to a discrete set of points so as to minimize the transport cost, using the squared Euclidean distance as the cost function. This has important applications in image stippling, clustering, resource allocation and in generating blue noise point distributions for rendering. Recent algorithms have been developed for solving the semi-discrete problem in 2d and 3d, however, algorithms in higher dimensions have yet to be demonstrated, which rely on the efficient calculation of the power diagram (Laguerre diagram) in higher dimensions. Here, we introduce an algorithm for computing power diagrams, which extends to any topological dimension. We first evaluate the performance of the algorithm in 2d-6d. We then restrict our attention to four-dimensional settings, demonstrating that our power diagrams can be used to solve optimal quantization and semi-discrete optimal transport problems, whereby a prescribed mass of each power cell is achieved by computing an optimized power diagram.