Skip to content
Preprint

Partial Optimal Transport on the Circle for All Transported Masses in O(N log N)

Aug 2026 · 0 citations · 32 references
Computer Science

TL;DR

PAWC is proposed: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality.

Abstract

Partial optimal transport compares two measures while leaving part of the mass unmatched, which is what makes it robust to outliers, occlusion, and clutter. The quantity of interest is usually the whole profile - the optimal cost at every transported cardinality - because the right amount to transport is rarely known in advance, and on the real line the PAWL algorithm returns that profile in $O(N\log N)$. Much data is periodic rather than linear: angles, phases, orientations, time of day, hue, and every direction obtained by projecting onto a great circle. On the circle the same problem acquires a global circulation, or equivalently an optimized cut, which the naive exact method handles by running the line algorithm once per support gap, at $O(N^{2}\log N)$. We show that this factor $N$ is unnecessary. The line structure survives in cut-free form, and a free-gap invariant supplies, at every step, a cut at which all previous local updates remain valid line updates. This yields PAWC: an exact $O(N\log N)$ time, $O(N)$ memory algorithm returning all $K+1$ costs, nested active sets and plans in one run, together with a single gap that is simultaneously optimal for every cardinality. Slicing over great circles extends it to $\mathbb{S}^{d-1}$. Empirically the whole profile costs $0.56$ms at $N=4096$ against $1.5$s for a single transported fraction from a general solver; on occluded, cluttered mpeg-7 shapes, holding the descriptor fixed and varying only the cost, it retains $66\%$ of the clean-data retrieval score against $16\%$ for balanced circular OT, and on $\mathbb{S}^{2}$ it halves the fitting error of spherical sliced Wasserstein against contaminated targets, synthetic and real. Code is available at https://github.com/mint-vu/Partial_Wasserstein_on_Circles.

View source

Similar papers

Preprint Aug 2026

Computing All Optimal Partial $p$-Wasserstein Matchings on the Line

An FFT-based data structure for balanced-interval transport queries is provided and an open-source C++ implementation is provided that outperforms the state-of-the-art baseline on a range of synthetic instances and establishes a conditional lower bound for p=\infty.

Sebastian Angrick, Jacobus Conradi, Mónika Csikós et al. · 0 citations
Preprint Aug 2026

A new unconditional lower bound for shoreline search

It is proved that every deterministic search path has competitive ratio at least $C_{\log}\approx 12.5937096701246675$ and Arb ball arithmetic provides a rigorous numerical enclosure of the constant.

A. Temerev · 3 citations

Fr´echet Distance with Speed Limits ∗

An e-cient algorithm is provided that decides in O ( n 2 log n ) time whether the Fr´echet distance with speed limits between two polygonal curves is at most ε, where n is the number of segments in the curves, and ε (cid:62) 0 is an input parameter.

Anil Maheshwari, J. Sack, K. Shahbaz et al. · 2 citations
Preprint Sep 2026

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable

A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings, and a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound are given.

Yuxuan Zhou · 0 citations
Preprint Sep 2026

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

We consider online packing of axis-parallel squares into a unit-width strip under the Tetris and gravity constraints: An incoming square must be lowered from above along a monotonic downwards path until it reaches support from below. Fekete, Kamphans, and Schweer [Algorithmica, 2014] gave an algorithm with asymptotic c...

N. Rasmussen · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.