Unifying Discrete and Semi-Discrete Optimal Transport via Dual Potentials — E8 Intelligence Research

FINDING: Discrete optimal transport (OT) on grids reduces to solving dual potentials via discrete harmonic equations, with network simplex providing exact solutions; semi-discrete OT bridges discrete measures to continuous ones via Laguerre tessellations, whose cell volumes encode dual potentials. | MATH: Kantorovich dual: \(maxφ,ψ ∑_i a_i φ_i + ∑_j b_j ψ_j\) s.t. \(φ_i + ψ_j ≤ cᵢⱼ\). Discrete dual potentials satisfy \(Δ φ = ρ - σ\) (discrete Poisson equation) on the grid, where \(Δ\) is the graph Laplacian. Network simplex pivots on spanning trees; complexity \(O(n^3 log n)\) worst-case, but parallel implementations exploit grid structure. Semi-discrete: \(ψ_j = min_i (|x - x_i|^2/2 - φ_i)\); cell volumes \(V_i(φ) = ∫L_i(φ) dx\) must match \(a_i\), solved by Newton iterations on \(φ\). | CONNECTION: The dual potentials on a regular grid are discrete harmonic functions — their discrete Laplacian zero modes cor Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com