# Solving Semi-Discrete Optimal Transport Problems: star shapedeness and Newton's method

arXiv: https://arxiv.org/abs/2310.07489 · HTML: https://mlsanity.com/paper/2310.07489/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2023.

## Built on by (most cited first, 1 of 1)

- [Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems](https://mlsanity.com/paper/2607.09139/) (2026)

## Abstract (arXiv)

In this work, we propose a novel implementation of Newton's method for solving semi-discrete optimal transport (OT) problems for cost functions which are a positive combination of p-norms, 1<p<∞. It is well understood that the solution of a semi-discrete OT problem is equivalent to finding a partition of a bounded region in Laguerre cells, and we prove that the Laguerre cells are star-shaped with respect to the target points. By exploiting the geometry of the Laguerre cells, we obtain an efficient and reliable implementation of Newton's method to find the sought network structure. We provide implementation details and extensive results in support of our technique in 2-d problems, as well as comparison with other approaches used in the literature.