How do you flatten the complex, folded surface of a human brain onto a flat map without distorting the size of its functional regions? How do you divide a continuous probability distribution into a set of discrete "representative" points while ensuring each point captures exactly the right amount of mass?
These problems, spanning medical imaging, computer graphics, and machine learning, are increasingly solved through a shared framework: Semi-discrete Optimal Transport (OT). By partitioning a continuous domain into a specialized geometric structure known as a Power Voronoi Diagram, researchers can create maps that are mathematically guaranteed to preserve area or mass.
The Core Intuition: Beyond Nearest Neighbors
To understand semi-discrete OT, it helps to start with a standard Voronoi diagram. If you have a set of points (seeds) in a room, a Voronoi diagram assigns every location in the room to its nearest seed. This creates a partition of the space into cells. However, in a standard Voronoi diagram, you have no control over the size of the cells; a seed in a crowded area gets a tiny cell, while a lonely seed gets a huge one.
In many applications, we need the cells to have specific, pre-defined volumes—for example, to match the surface area of a triangle mesh or the probability mass of a data cluster.
As explained by Justin Solomon in Optimal Transport on Discrete Domains, semi-discrete transport solves this by moving from standard Voronoi cells to Power Voronoi Diagrams (also called Laguerre tessellations). In this setup, each seed is assigned a "weight." The boundary between two cells is no longer just the perpendicular bisector; it shifts based on the weights. By carefully tuning these weights, we can "inflate" or "deflate" cells until each one contains exactly the desired amount of mass from the continuous source distribution.
Area-Preserving Maps and Brain Imaging
One of the most impactful applications of this geometry is in medical visualization. The human cortex is a highly curved 2D manifold embedded in 3D. To analyze it, researchers often "parameterize" or flatten it. Traditional methods often preserve angles (conformal mapping) but cause massive area distortion—a small region on the brain might appear huge on the map.
Zhengyu Su, Wei Zeng, and Xianfeng Gu have pioneered methods to fix this. In Area Preserving Brain Mapping, they use Monge-Brenier theory to frame area preservation as an optimal transport problem. By treating the 3D surface as a continuous density and the 2D map as a collection of discrete cells, they use a convex optimization process (Newton's method) to find the unique weights that make the 2D cell areas match the original 3D surface areas.
This isn't just aesthetic; Su et al. demonstrated that these area-preserving maps allow for more accurate feature extraction, leading to significantly higher accuracy in diagnosing Alzheimer’s Disease. Later work in Spherical Parameterization Balancing Angle and Area Distortions extended this to allow researchers to precisely "dial in" the balance between preserving angles and preserving areas.
Bridging Continuous and Discrete Data
The power of semi-discrete OT extends into abstract data spaces. In machine learning, we often want to summarize a complex dataset using a few "archetypes." Braxton Osting and Dong Wang introduced Wasserstein Archetypal Analysis, which uses semi-discrete OT to find representative points that minimize the Wasserstein distance to the data distribution. This approach is more robust to outliers than traditional Euclidean methods because the Power Voronoi geometry naturally accounts for the underlying "shape" of the data density.
Even in adversarial machine learning, this geometric partitioning is a potent tool. Zezeng Li and colleagues developed NoPain, an attack on 3D point clouds. By using semi-discrete OT to map a continuous source to the discrete points of a cloud, they identify "singular boundaries"—the edges of the Power Voronoi cells. These boundaries represent the most sensitive transitions in the data distribution, allowing them to generate adversarial samples that fool models without needing access to the model's internal gradients.
Computational Efficiency and Convergence
Historically, Optimal Transport was computationally prohibitive. However, the semi-discrete case offers unique mathematical advantages. Because the problem can be framed as minimizing a convex energy function related to the volumes of Power Voronoi cells, it can be solved using efficient second-order optimization methods.
Recent theoretical work has further solidified this foundation:
- Speed: Sharath Raghvendra and Pankaj K Agarwal developed algorithms in Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings that use cost-scaling and hierarchical structures to achieve near-linear runtimes.
- Statistical Reliability: Aram-Alexandre Pooladian and Jonathan Weed proved in Minimax estimation of discontinuous optimal transport maps that even when the underlying transport map is discontinuous (which happens at the cell boundaries), estimators for semi-discrete OT converge at a rate that is independent of the dimension of the space, making it highly effective for high-dimensional data.
By turning the abstract problem of "moving mass" into the concrete geometric task of "building a weighted Voronoi diagram," semi-discrete optimal transport provides a robust bridge between the continuous world of surfaces and distributions and the discrete world of meshes and points.