Matching points, comparing distributions, or even generating distributions "in between" several distributions are challenges encountered in computer graphics, machine learning, and many other fields. Optimal transport is a mathematical theory that addresses these problems. For example, it allows matching two sets (such as points, people, or objects) while minimizing the total cost of this matching (e.g., the sum of distances between points, affinities between people, or similarities between objects). However, the computational complexity of algorithms solving the optimal transport problem is often too high, making them impractical for very large problems (such as millions of points) or high-dimensional data. A common approach is to reduce the problem to a series of one-dimensional optimal transport problems, which are much easier to compute, this is referred to as a "sliced" transport method. This involves projecting the data onto lines, sorting the points along these lines, and matching them in the order of the sort. While this approach is efficient, it remains highly approximate.

In a best paper award-winning study presented at ACM SIGGRAPH Asia 2025, researchers from the LIRIS lab proposed a method that is equally efficient but far more accurate. One way to sort points along a line is to split the line in two, distributing the points on either side, and repeating the process on the two resulting segments. Instead, the researchers suggest choosing a new random line each time the previous line is split. This creates a structure called a Binary Space Partitioning (BSP) tree, whose construction has the same algorithmic complexity as a simple sort. By simultaneously building a BSP tree on both sets of points to be matched—and ensuring that each subset contains the same number of points, an acceptable matching can be achieved. Moreover, by repeating the process with different random directions, multiple matchings can be obtained and efficiently combined to reduce the transport cost, achieving near-optimal results in many situations.

The potential applications are numerous, ranging from color processing in images to shape morphing, as well as sampling 3D surfaces or images. For these applications, BSP transport can be several orders of magnitude faster than exact optimal transport calculations and several orders of magnitude more accurate than sliced transport.

More informations: 

• HAL : https://hal.science/hal-05316444v1 
• Code : https://github.com/baptiste-genest/BSP-OT 
• Page de l'article : https://baptiste-genest.github.io/publications/#bsp-ot