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

# Partial Optimal Transport on the Circlefor All Transported Masses in 𝑂(𝑁⁢log𝑁)
Source: [https://arxiv.org/html/2608.23910](https://arxiv.org/html/2608.23910)
Soheil KolouriAffiliation:College of Connected ComputingAffiliation:Vanderbilt University, Nashville, TNEmail:[mailto:](mailto:)[soheil\.kolouri@vanderbilt\.edu](mailto:[email protected])

###### 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 thePAWLalgorithm returns that profile inO⁡\(N​log⁡N\)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, atO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)\. We show that this factorNNis 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 yieldsPAWC: an exactO⁡\(N​log⁡N\)O\(N\\log N\)time,O⁡\(N\)O\(N\)memory algorithm returning allK\+1K\+1costs, 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𝕊d−1\\mathbb\{S\}^\{d\-1\}\. Empirically the whole profile costs0\.560\.56ms atN=4096N=4096against1\.51\.5s for a single transported fraction from a general solver; on occluded, clutteredmpeg\-7shapes, holding the descriptor fixed and varying only the cost, it retains66%66\\%of the clean\-data retrieval score against16%16\\%for balanced circular OT, and on𝕊2\\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](https://github.com/mint-vu/Partial_Wasserstein_on_Circles)\.

## 1Introduction

Optimal transport \(OT\) provides a geometry\-aware framework for comparing measures\([Villani, 2009](https://arxiv.org/html/2608.23910#bib.bib25);[Peyré and Cuturi, 2019](https://arxiv.org/html/2608.23910#bib.bib6)\), but exact discrete solvers are generally expensive\. Partial transport extends this framework by allowing only part of the distributions to be matched: conceptually, mass may be transported from the source to the target, destroyed if left unmatched at the source, or created if unmatched at the target, with corresponding transportation, destruction, and creation costs\. In one dimension,[Bai et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib17)exploited the ordering of the supports to develop an exact primal\-dual solver for a fixed choice of these penalties, with worst\-case complexityO⁡\(n​max⁡\{m,n\}\)O\(n\\max\\\{m,n\\\}\), orO⁡\(N2\)O\(N^\{2\}\)for distributions of comparable size\. More recently,[Chapel and Tavenard \(2025\)](https://arxiv.org/html/2608.23910#bib.bib3)showed that the entire solution path indexed by the transported mass can be computed much faster: theirPAWLalgorithm returns exact partial transport plans for every possible transported mass inO⁡\(N​log⁡N\)O\(N\\log N\)time, using nested active sets, neighboring candidate pairs, balanced chains, and a heap of chain marginals\.

Unmatched mass is often part of the problem rather than a modeling nuisance\. A partial correspondence isolates the structure shared by two measures without forcing spurious detections, occluded features, mislocated records, or outliers into geometrically implausible matches\([Nietert et al\., 2022](https://arxiv.org/html/2608.23910#bib.bib26)\)\. The appropriate amount of mass to match, however, is rarely known beforehand and may depend on a downstream robustness or coverage requirement\. The natural object is therefore the entire partial\-transport profilek⟼Ck∘,k\\longmapsto C\_\{k\}^\{\\circ\},whereCk∘C\_\{k\}^\{\\circ\}is the minimum cost of matching exactlykkpairs\. This profile quantifies the tradeoff between coverage and geometric fidelity: it shows which correspondences are retained as the transported mass increases and when admitting additional mass begins to require costly matches\. Computing allCk∘C\_\{k\}^\{\\circ\}at once allows the transported mass to be selected after examining this tradeoff, rather than fixed before solving the transport problem\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\.

Periodic geometry is ubiquitous rather than exceptional\. Angles, phases, orientations, time\-of\-day variables, and hue are naturally represented on the circle, while many sliced constructions for directional data on the sphere produce measures supported on great circles\. However, the cyclic geometry of the circle prevents a direct application of the efficient algorithms available on the line\. The circle retains a cyclic order but has no canonical first point, last point, or zero\-flow boundary\. For balancedW1W\_\{1\}, this missing boundary condition appears as a free additive circulation in the flow formulation, or equivalently as a cut over which a lifted line problem must be optimized\([Delon et al\., 2010](https://arxiv.org/html/2608.23910#bib.bib4);[Rabin et al\., 2011](https://arxiv.org/html/2608.23910#bib.bib7)\)\. Partial transport couples this topological freedom to the transported mass: askkvaries, both the active atoms and the optimal circulation, and hence the optimal cut, may change\. Consequently, no single unwrapping of the circle recovers the full profilek↦Ck∘k\\mapsto C\_\{k\}^\{\\circ\}\. A direct exact reduction cuts the circle at every support gap, runsPAWLon each resulting line, and takes the lower envelope of the resulting profiles\. Although correct, this repeats anO⁡\(N​log⁡N\)O\(N\\log N\)computation acrossO⁡\(N\)O\(N\)cuts and therefore costsO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)\. The central algorithmic challenge is to recover the entire circular partial\-transport profile without paying separately for every possible cut\.

##### Contributions\.

The line structure survives on the circle in cut\-free form \([Section3](https://arxiv.org/html/2608.23910#S3)\): circular\-optimal active sets can be chosen nested, the two atoms activated at each step are cyclic neighbours among the inactive ones, and a*free\-gap invariant*— every current cell always contains an original gap not yet used by any selected cell — supplies a cut at which all previous local updates are simultaneously valid line updates\. This gives an exact greedy rule and a gap that is optimal for*every*cardinality at once, constructed rather than searched for \([Theorems3](https://arxiv.org/html/2608.23910#Thmtheorem3)and[4](https://arxiv.org/html/2608.23910#Thmtheorem4)\), and anO⁡\(N​log⁡N\)O\(N\\log N\)time,O⁡\(N\)O\(N\)memory algorithm returning all costs, nested active sets and plans in one run \([Section4](https://arxiv.org/html/2608.23910#S4)\)\. Slicing over great circles extends it to𝕊d−1\\mathbb\{S\}^\{d\-1\}\([Section5](https://arxiv.org/html/2608.23910#S5)\), and[Section6](https://arxiv.org/html/2608.23910#S6)verifies exactness against an LP oracle, measures the scaling, and gives two applications where the profile is the object that matters — partial matching of shape descriptors onmpeg\-7, and robust fitting on𝕊2\\mathbb\{S\}^\{2\}including a real earthquake catalogue\.

## 2Background

### 2\.1Partial optimal transport on the circle

Let𝕊L1=ℝ/L​ℤ\\mathbb\{S\}^\{1\}\_\{L\}=\\mathbb\{R\}/L\\mathbb\{Z\}with geodesic distanced𝕊1​\(x,y\)=min⁡\{\|x−y\|,L−\|x−y\|\}d\_\{\\mathbb\{S\}^\{1\}\}\(x,y\)=\\min\\\{\|x\-y\|,L\-\|x\-y\|\\\}, and letμ=w​∑i=1nδxi\\mu=w\\sum\_\{i=1\}^\{n\}\\delta\_\{x\_\{i\}\}andν=w​∑j=1mδyj\\nu=w\\sum\_\{j=1\}^\{m\}\\delta\_\{y\_\{j\}\}be uniformly weighted empirical measures; writeN=n\+mN=n\+mandK=min⁡\(n,m\)K=\\min\(n,m\)\. For a transported masss∈\[0,K​w\]s\\in\[0,Kw\], define the circular partial11\-Wasserstein cost by

PW∘\(s\):=minπ∈ℝ\+n×m\{∑i=1n∑j=1md𝕊1\(xi,yj\)πi​j:∑j=1mπi​j≤w,∑i=1nπi​j≤w,∑i,jπi​j=s\}\.\\operatorname\{PW\}\_\{\\circ\}\(s\):=\\min\_\{\\pi\\in\\mathbb\{R\}\_\{\+\}^\{n\\times m\}\}\\Bigl\\\{\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)\\pi\_\{ij\}\\;:\\;\\sum\_\{j=1\}^\{m\}\\pi\_\{ij\}\\leq w,\\;\\sum\_\{i=1\}^\{n\}\\pi\_\{ij\}\\leq w,\\;\\sum\_\{i,j\}\\pi\_\{ij\}=s\\Bigr\\\}\.\(1\)ThusPW∘⁡\(s\)\\operatorname\{PW\}\_\{\\circ\}\(s\)is the minimum cost of transporting exactlyssunits of mass, with at most the full masswwof each atom participating\. Relaxing mass conservation to an inequality and fixing the transported total is the partial problem of[Caffarelli and McCann \(2010\)](https://arxiv.org/html/2608.23910#bib.bib2), who established existence and uniqueness for costsh⁡\(x−y\)h\(x\-y\)withhhconvex and disjoint supports;[Figalli \(2010\)](https://arxiv.org/html/2608.23910#bib.bib5)relaxed disjointness for the quadratic cost and studied the maps↦PW⁡\(s\)s\\mapsto\\operatorname\{PW\}\(s\)\. It is that map, not any single value of it, that we compute\.

\(a\) Fixed\-mass partial OT on𝕊L1\\mathbb\{S\}^\{1\}\_\{L\}

x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}y2y\_\{2\}x3x\_\{3\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}w​d𝕊1​\(x1,y1\)wd\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{1\},y\_\{1\}\)w​d𝕊1​\(x2,y2\)wd\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{2\},y\_\{2\}\)∂d\\partial\_\{\\rm d\}∂d\\partial\_\{\\rm d\}∂c\\partial\_\{\\rm c\}∂c\\partial\_\{\\rm c\}

solid: transported; hollow: unmatched

\(b\) Exact mass and cost accounting

𝒥k​\(M\)=\\displaystyle\\mathcal\{J\}\_\{k\}\(M\)=\{\}w​∑\(i,j\)∈Md𝕊1​\(xi,yj\)⏟transport cost\\displaystyle\\underbrace\{w\\sum\_\{\(i,j\)\\in M\}d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)\}\_\{\{\\color\[rgb\]\{0\.1133,0\.5117,0\.3359\}\\text\{transport cost\}\}\}\+λd​\(n−k\)​w⏟destroyed source mass\+λc​\(m−k\)​w⏟created target mass\.\\displaystyle\+\\lambda\_\{\\rm d\}\\underbrace\{\(n\-k\)w\}\_\{\{\\color\[rgb\]\{0\.1445,0\.3672,0\.6484\}\\text\{destroyed source mass\}\}\}\+\\lambda\_\{\\rm c\}\\underbrace\{\(m\-k\)w\}\_\{\{\\color\[rgb\]\{0\.8398,0\.3555,0\.125\}\\text\{created target mass\}\}\}\.
Figure 1:Partial transport on the circle\. \(a\) solid arcs are geodesic transports between selected atoms; hollow atoms are left unmatched, their mass destroyed at∂d\\partial\_\{\\rm d\}or created at∂c\\partial\_\{\\rm c\}\. \(b\) at a fixed transported cardinality\|M\|=k\|M\|=kthose two amounts are constants, so any fixed penaltiesλd,λc\\lambda\_\{\\rm d\},\\lambda\_\{\\rm c\}contribute a constant and the problem is exactly the cardinality\-constrained matching \([2](https://arxiv.org/html/2608.23910#S2.E2)\)\.###### Assumption 1\(Standing assumptions\)\.

All atoms carry the same massww; the points\{xi\}∪\{yj\}\\\{x\_\{i\}\\\}\\cup\\\{y\_\{j\}\\\}are pairwise distinct; and the ground cost isd𝕊1d\_\{\\mathbb\{S\}^\{1\}\}\.

At an integer masss=k​ws=kw, scaling the feasible set bywwgives the cardinality\-kkbipartite matching polytope\. Its extreme points are integral, and hence

Ck∘:=PW∘\(kw\)=minM:\|M\|=kw∑\(xi,yj\)∈Md𝕊1\(xi,yj\),k=0,…,K,C\_\{k\}^\{\\circ\}:=\\operatorname\{PW\}\_\{\\circ\}\(kw\)=\\min\_\{M:\\,\|M\|=k\}\\;w\\\!\\\!\\sum\_\{\(x\_\{i\},y\_\{j\}\)\\in M\}\\\!\\\!d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\),\\qquad k=0,\\dots,K,\(2\)whereMMranges over matchings, so no atom appears in more than one pair\. We callk↦Ck∘k\\mapsto C\_\{k\}^\{\\circ\}the*profile*and denote byA⁡\(M\)A\(M\)the set of atoms incident toMM, called its*active set*\. Fors∈\[k​w,\(k\+1\)​w\]s\\in\[kw,\(k\+1\)w\], writeλ=\(s−k​w\)/w\\lambda=\(s\-kw\)/w; the value interpolates linearly,

PW∘⁡\(s\)=\(1−λ\)​Ck∘\+λ​Ck\+1∘,\\operatorname\{PW\}\_\{\\circ\}\(s\)=\(1\-\\lambda\)\\,C\_\{k\}^\{\\circ\}\+\\lambda\\,C\_\{k\+1\}^\{\\circ\},\(3\)so the discrete profile\{Ck∘\}k=0K\\\{C\_\{k\}^\{\\circ\}\\\}\_\{k=0\}^\{K\}determinesPW∘⁡\(s\)\\operatorname\{PW\}\_\{\\circ\}\(s\)for everys∈\[0,K​w\]s\\in\[0,Kw\]; see[AppendixI](https://arxiv.org/html/2608.23910#A9)\.

### 2\.2Computing partial transport

Exact solvers for OT and its unbalanced variants are cubic; the standard remedies are entropic regularisation\([Cuturi, 2013](https://arxiv.org/html/2608.23910#bib.bib22)\)and the one\-dimensional quantile formula underlying sliced transport\([Rabin et al\., 2012](https://arxiv.org/html/2608.23910#bib.bib23);[Peyré and Cuturi, 2019](https://arxiv.org/html/2608.23910#bib.bib6)\)\. For partial transport,[Phatak et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib19)compute the full mass profile inO⁡\(n3\)O\(n^\{3\}\);[Bai et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib17)give a quadratic one\-dimensional solver;[Bonneel and Coeurjolly \(2019\)](https://arxiv.org/html/2608.23910#bib.bib18)solve injective partial assignment in quasi\-linear time;[Séjourné et al\. \(2022\)](https://arxiv.org/html/2608.23910#bib.bib20)solve one\-dimensional unbalanced OT quasi\-linearly but cannot prescribe the transported mass; and[Chapel et al\. \(2021\)](https://arxiv.org/html/2608.23910#bib.bib21)obtain a regularisation path\.PAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)is the first to return the entire partial profile on the line inO⁡\(n​log⁡n\)O\(n\\log n\), and is what we extend\.

On the circle, prior work is balanced:[Delon et al\. \(2010\)](https://arxiv.org/html/2608.23910#bib.bib4)and[Rabin et al\. \(2011\)](https://arxiv.org/html/2608.23910#bib.bib7)solveW1W\_\{1\}by optimising a cut or global circulation;[Díaz Martín et al\. \(2024\)](https://arxiv.org/html/2608.23910#bib.bib10)linearise circular OT; and[Bonet et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib8);[Liu et al\. \(2025\)](https://arxiv.org/html/2608.23910#bib.bib9)use circular transport within spherical slicing\. None addresses prescribed\-mass partial transport on the circle\.

##### Why the circle is not the line\.

For a*fixed*active set the circular cost is the minimum of the unwrapped line costs over theNNsupport gaps \([Proposition1](https://arxiv.org/html/2608.23910#Thmproposition1)in[AppendixC](https://arxiv.org/html/2608.23910#A3)\), so the envelope over gaps and cardinalities is an exactO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)reference solver \([Corollary2](https://arxiv.org/html/2608.23910#Thmcorollary2), also there\) — which we use as a baseline in[Section6](https://arxiv.org/html/2608.23910#S6)and as a trusted second opinion in testing\.[Example1](https://arxiv.org/html/2608.23910#Thmexample1)in[AppendixF](https://arxiv.org/html/2608.23910#A6)shows that reusing one fixed cut can be off by an unbounded factor, and[SectionK\.5](https://arxiv.org/html/2608.23910#A11.SS5)measures how often a single cut would in fact have sufficed\.

## 3Structure of circular partial transport

### 3\.1Nested active sets and cyclic neighbours:O⁡\(N\)O\(N\)candidates per step

###### Theorem 1\(Nested optimal extension; proved in[AppendixD](https://arxiv.org/html/2608.23910#A4)\)\.

LetMkM\_\{k\}be any optimal cardinality\-kkmatching,k<Kk<K\. Then there is an optimal cardinality\-\(k\+1\)\(k\+1\)matchingMk\+1M\_\{k\+1\}withA⁡\(Mk\+1\)=A⁡\(Mk\)∪\{x,y\}A\(M\_\{k\+1\}\)=A\(M\_\{k\}\)\\cup\\\{x,y\\\}for a source atomxxand a target atomyy, both previously inactive\.

Nestedness means the profile can be built incrementally: never revisit a decision, only extend\. The second structural fact says where to look for the extension\.

###### Theorem 2\(Cyclic\-neighbour property; proved in[AppendixD](https://arxiv.org/html/2608.23910#A4)\)\.

In such an extension,xxandyyare consecutive in the cyclic ordering of the inactive setAkcA\_\{k\}^\{c\}\.

Deleting the active atoms therefore leaves a circle of inactive atoms, and only theO⁡\(N\)O\(N\)adjacent pairs of*opposite type*are ever candidates\. We call the arc between two consecutive inactive atoms a*current cell*, a cell whose endpoints have opposite types a*candidate*, and write𝔪⁡\(𝒞\)\\mathfrak\{m\}\(\\mathcal\{C\}\)for its*local marginal*: the increase in the cell’s internal line\-transport cost caused by activating its two endpoints \([Definition3](https://arxiv.org/html/2608.23910#Thmdefinition3)in[AppendixE](https://arxiv.org/html/2608.23910#A5)\)\.[Figure2](https://arxiv.org/html/2608.23910#S3.F2)is the whole mechanism — activating a candidate pair rematches the atoms inside its cell and nothing else, so the increment is computable from that cell alone\.

\(a\) Candidate cell

uuvvy1y\_\{1\}x1x\_\{1\}y2y\_\{2\}x2x\_\{2\}𝒞=\[u,v\]↻\\mathcal\{C\}=\[u,v\]\_\{\\circlearrowright\}

\(b\) Before activation

y1y\_\{1\}x1x\_\{1\}y2y\_\{2\}x2x\_\{2\}cℝ​\(𝒞∘\)c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\)

\(c\) After activatingu,vu,v

uuy1y\_\{1\}x1x\_\{1\}y2y\_\{2\}x2x\_\{2\}vvcℝ​\(𝒞\)c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)

𝔪⁡\(𝒞\)=cℝ​\(𝒞\)−cℝ​\(𝒞∘\)\.\\mathfrak\{m\}\(\\mathcal\{C\}\)=c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)\-c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\)\.

Figure 2:A candidate cell and its exact local cost increment\. The inactive endpointsuuandvvare cyclic neighbours of opposite type and the open interior𝒞∘\\mathcal\{C\}^\{\\circ\}is active and balanced\. Before activation the interior atoms are matched in sorted order; activatingu,vu,vrevokes every match inside the cell \(grey dashed\) and replaces it by the new sorted matching \(magenta\), while every match outside the cell is untouched\. The increment is therefore𝔪⁡\(𝒞\)=cℝ​\(𝒞\)−cℝ​\(𝒞∘\)\\mathfrak\{m\}\(\\mathcal\{C\}\)=c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)\-c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\), computable from the atoms of the cell alone — the circular analogue ofPAWL’s chain update\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\.
### 3\.2The free\-gap invariant: one cut for allK\+1K\+1problems

The difficulty specific to the circle is that a local update is only meaningful relative to a cut, and cells are updated at different times\. The following invariant is what makes one cut serve all of them\. Call an original support gap*free*if it lies inside no cell that has been selected so far\.

###### Lemma 1\(Free\-gap invariant; proved in[AppendixF](https://arxiv.org/html/2608.23910#A6)\)\.

Before termination, every current cell contains at least one free original gap\.

\(a\) Before selecting\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}

ppuuvvqq\[p,u\]↻\[p,u\]\_\{\\circlearrowright\}\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}\[v,q\]↻\[v,q\]\_\{\\circlearrowright\}rep\.rep\.rep\.

Every current cell has a balanced active interior and stores one representative free gap \(boxed\)\. Shaded: the selected candidate cell\.

\(b\) Activateu,vu,vand merge the three cells

ppuuvvqq\[p,q\]↻\[p,q\]\_\{\\circlearrowright\}free \(stored\)usedfree \(not stored\)

u,vu,vbecome active interior atoms and leave the inactive list\. Only the gaps*inside*the selected cell become used\. Both flanking arcs keep their free gaps; the merged cell adopts one of them as its stored representative \(here the left\) and simply does not track the other\. Sincep,qp,qhave opposite types \(as here\), the new cell enters the heap\.

Figure 3:Merging two cells after an activation\. The new cell inherits a free gap from one of its parents, so[Lemma1](https://arxiv.org/html/2608.23910#Thmlemma1)is maintained atO⁡\(1\)O\(1\)cost, and that gap is a cut at which every update made so far is a valid line update\.A free gap in a cell is a cut outside every previously selected cell, so unwrapping there leaves all earlier local computations valid; and when two cells merge, the new cell inherits a free gap from a parent \([Figure3](https://arxiv.org/html/2608.23910#S3.F3)\), so the invariant is maintained in constant time\. Combined with a pairwise common\-cut lemma \([Lemma3](https://arxiv.org/html/2608.23910#Thmlemma3)in[AppendixD](https://arxiv.org/html/2608.23910#A4)\), which produces one cut valid for two competing cells at once, this yields the greedy rule\.

###### Theorem 3\(Exact greedy choice; proved in[AppendixF](https://arxiv.org/html/2608.23910#A6)\)\.

If the current active setAkA\_\{k\}is circularly optimal and was produced by successive cell selections, thenCk\+1∘−Ck∘=min𝒞∈ℭk⁡𝔪⁡\(𝒞\)C\_\{k\+1\}^\{\\circ\}\-C\_\{k\}^\{\\circ\}=\\min\_\{\\mathcal\{C\}\\in\\mathfrak\{C\}\_\{k\}\}\\mathfrak\{m\}\(\\mathcal\{C\}\), whereℭk\\mathfrak\{C\}\_\{k\}is the set of current candidate cells, and activating the endpoints of any minimiser yields a circularly optimalAk\+1A\_\{k\+1\}\.

###### Theorem 4\(Simultaneous optimal cut; proved in[AppendixF](https://arxiv.org/html/2608.23910#A6)\)\.

There is an original support gapθ⋆\\theta^\{\\star\}withCk,θ⋆line=Ck∘C\_\{k,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}=C\_\{k\}^\{\\circ\}for everyk=0,…,Kk=0,\\dots,K, and the greedy construction produces one\.

[Theorem4](https://arxiv.org/html/2608.23910#Thmtheorem4)is what removes the outer loop over cuts \([Figure11](https://arxiv.org/html/2608.23910#A6.F11)in[AppendixF](https://arxiv.org/html/2608.23910#A6)illustrates it\): rather than searchNNcuts and take an envelope, the algorithm*constructs*a gap that is optimal for every cardinality, as a by\-product of the free\-gap bookkeeping it already does\. Onceθ⋆\\theta^\{\\star\}is known, every plan is recovered by sorting the active atoms of each type in the unwrapped order and pairing them \([AppendixI](https://arxiv.org/html/2608.23910#A9)\)\. The theorem is not a convenience: cutting once at a gap that is optimal for the full\-mass problem and reusing it is strictly suboptimal at some cardinality on13\.5%13\.5\\%of56005600exact instances, and when it fails the relative excess reaches1\.8×1031\.8\\times 10^\{3\}; other one\-cut rules also fail \([SectionK\.5](https://arxiv.org/html/2608.23910#A11.SS5)\)\.

## 4ThePAWCalgorithm:O⁡\(1\)O\(1\)marginals,O⁡\(N​log⁡N\)O\(N\\log N\)overall

It remains to evaluate candidate marginals cheaply\. FollowingPAWL’s chain machinery, we duplicate the cyclic support into a doubled sequence of length2​N2Nso that every arc becomes an interval, and precompute prefix arrays of differential ranks and signed positions\. A balanced interval’s minimal\-chain cost is then a single table lookup, and the marginal of a candidate cell is calculated via:

###### Corollary 1\(Constant\-time candidate marginal; proved in[AppendixG](https://arxiv.org/html/2608.23910#A7)\)\.

For a candidate cell represented by the balanced doubled interval\[a,b\]\[a,b\],𝔪⁡\(\[a,b\]\)=\(Qb−Qa−1\)−\(Qb−1−Qa\)\\mathfrak\{m\}\(\[a,b\]\)=\(Q\_\{b\}\-Q\_\{a\-1\}\)\-\(Q\_\{b\-1\}\-Q\_\{a\}\), with the second term zero when the interior is empty\. Hence each candidate marginal costsO⁡\(1\)O\(1\)after preprocessing\.

Algorithm 1PAWC: all exact partialW1W\_\{1\}costs on the circle1:Circular source points

x1,…,xnx\_\{1\},\\dots,x\_\{n\}, target points

y1,…,ymy\_\{1\},\\dots,y\_\{m\}, weight

ww, circumference

LL
2:Costs

C0∘,…,CK∘C\_\{0\}^\{\\circ\},\\dots,C\_\{K\}^\{\\circ\}, activation ranks, simultaneous cut

θ⋆\\theta^\{\\star\}
3:Sort the union support cyclically and form labels

σ1,…,σN\\sigma\_\{1\},\\dots,\\sigma\_\{N\}
4:Build the doubled sequence and precompute the prefix tables

R,S,p,QR,S,p,Q\([AppendixG](https://arxiv.org/html/2608.23910#A7)\)

5:Initialize a circular doubly linked list containing all support indices

6:For each initial directed cell, store its unique original gap as its free\-gap representative

7:Insert every opposite\-endpoint initial cell into a min\-heap keyed by

𝔪\\mathfrak\{m\}\([Corollary1](https://arxiv.org/html/2608.23910#Thmcorollary1)\)

8:

C0∘←0C\_\{0\}^\{\\circ\}\\leftarrow 0
9:for

k=0,1,…,K−1k=0,1,\\dots,K\-1do

10:repeat

11:Pop the minimum heap entry

\(u,v,𝔪\)\(u,v,\\mathfrak\{m\}\)
12:until

u,vu,vare inactive,

v=succ⁡\(u\)v=\\operatorname\{succ\}\(u\), and

u,vu,vhave opposite types

13:Record activation rank

k\+1k\+1for

uuand

vv
14:

Ck\+1∘←Ck∘\+𝔪C\_\{k\+1\}^\{\\circ\}\\leftarrow C\_\{k\}^\{\\circ\}\+\\mathfrak\{m\}
15:Let

p←pred⁡\(u\)p\\leftarrow\\operatorname\{pred\}\(u\)and

q←succ⁡\(v\)q\\leftarrow\\operatorname\{succ\}\(v\)before deletion

16:ifonly

u,vu,vare inactivethen

17:

θ⋆←\\theta^\{\\star\}\\leftarrowfree\-gap representative of the complementary cell

\[v,u\]↻\[v,u\]\_\{\\circlearrowright\}
18:Remove

u,vu,vandcontinue

19:endif

20:Remove

u,vu,vand link

ppdirectly to

qq
21:Let the new cell

\[p,q\]↻\[p,q\]\_\{\\circlearrowright\}inherit a free\-gap representative from

\[p,u\]↻\[p,u\]\_\{\\circlearrowright\}or

\[v,q\]↻\[v,q\]\_\{\\circlearrowright\}
22:if

ppand

qqhave opposite typesthen

23:Compute

𝔪⁡\(\[p,q\]↻\)\\mathfrak\{m\}\(\[p,q\]\_\{\\circlearrowright\}\)in

O⁡\(1\)O\(1\)and insert the new candidate into the heap

24:endif

25:endfor

26:if

θ⋆\\theta^\{\\star\}has not been setthen

27:Choose it as the free\-gap representative of any remaining current cell

28:endif

29:return

\{Ck∘\}k=0K\\\{C\_\{k\}^\{\\circ\}\\\}\_\{k=0\}^\{K\}, activation ranks,

θ⋆\\theta^\{\\star\}

###### Theorem 5\(Correctness and complexity; proved in[AppendixH](https://arxiv.org/html/2608.23910#A8)\)\.

Under[Assumption1](https://arxiv.org/html/2608.23910#Thmassumption1),[Algorithm1](https://arxiv.org/html/2608.23910#alg1)returns the exactCk∘C\_\{k\}^\{\\circ\}and an optimal active set for everykk, together with a gapθ⋆\\theta^\{\\star\}valid for allkk, inO⁡\(N​log⁡N\)O\(N\\log N\)time andO⁡\(N\)O\(N\)memory\.

The loop is a textbook greedy with lazy deletion: at mostNNinitial candidates and at most one new candidate per activation, soO⁡\(N\)O\(N\)heap entries in total, each popped once, valid or stale, atO⁡\(log⁡N\)O\(\\log N\); everything else — key evaluation, list surgery, free\-gap inheritance — isO⁡\(1\)O\(1\)\. Sorting dominates\.

## 5Slicing to the sphere

Directional data indddimensions lives on𝕊d−1\\mathbb\{S\}^\{d\-1\}, where exact OT is expensive\. Slicing replaces it by an average over one\-dimensional projections; on the sphere the natural projections are onto great circles\([Bonet et al\., 2023](https://arxiv.org/html/2608.23910#bib.bib8)\)\. ForUUin the Stiefel manifoldVd,2V\_\{d,2\}, the geodesic projectionPU​\(x\)=U​U⊤​x/‖U⊤​x‖P^\{U\}\(x\)=UU^\{\\top\}x/\\\|U^\{\\top\}x\\\|maps𝕊d−1\\mathbb\{S\}^\{d\-1\}onto the great circle spanned byUU, and reading the result in the circle’s own coordinate turns each slice into an instance of \([2](https://arxiv.org/html/2608.23910#S2.E2)\) withL=2​πL=2\\pi\.

U⊤​x=0U^\{\\\!\\top\}x=0𝒞U=span⁡\(U\)∩𝕊d−1\\mathcal\{C\}\_\{U\}=\\mathrm\{span\}\(U\)\\cap\\mathbb\{S\}^\{d\-1\}\(a\) geodesic projection onto a great circleθ⋆\\theta^\{\\star\}\(b\) the circular partial problematom ofμ\\muatom ofν\\nuprojectionPU​\(x\)P^\{U\}\\\!\(x\)transported pairunmatched atomfree gapθ⋆\\theta^\{\\star\}Figure 4:Spherical slicing, after[Bonet et al\. \(2023, Figure 1\)](https://arxiv.org/html/2608.23910#bib.bib8)\. \(a\) atoms ofμ\\mu\(blue\) andν\\nu\(orange\) on𝕊d−1\\mathbb\{S\}^\{d\-1\}, the great circle𝒞U\\mathcal\{C\}\_\{U\}\(dashed behind the sphere\), and the geodesic projection of each onto it\. \(b\) the circular problem that slice induces, with a cardinality\-33matching and a free gapθ⋆\\theta^\{\\star\}\.PAWCreturns the optimal matching for*every*kkin oneO⁡\(N​log⁡N\)O\(N\\log N\)sweep per slice\.###### Definition 1\(Sliced spherical partial Wasserstein;[AppendixJ](https://arxiv.org/html/2608.23910#A10)\)\.

SSPW⁡\(s,μ,ν\)=∫Vd,2PW∘⁡\(s,P\#U​μ,P\#U​ν\)​𝑑σ​\(U\)\\mathrm\{SSPW\}\(s;\\mu,\\nu\)=\\int\_\{V\_\{d,2\}\}\\operatorname\{PW\}\_\{\\circ\}\(s;P^\{U\}\_\{\\\#\}\\mu,P^\{U\}\_\{\\\#\}\\nu\)\\,d\\sigma\(U\), estimated by the average overMMi\.i\.d\. slices\.

[Figure4](https://arxiv.org/html/2608.23910#S5.F4)shows one slice\. BecausePAWCreturns the whole profile per slice, one pass overMMslices gives the estimate at*every*transported mass, at costO⁡\(M⁡\(N​log⁡N\+d​N\)\)O\(M\(N\\log N\+dN\)\)\. The estimator concentrates uniformly over the profile:M≥\(π2​K2​w2/2​ε2\)​log⁡\(2​\(K\+1\)/δ\)M\\geq\(\\pi^\{2\}K^\{2\}w^\{2\}/2\\varepsilon^\{2\}\)\\log\(2\(K\+1\)/\\delta\)slices suffice forε\\varepsilon\-accuracy on the entire curve with probability1−δ1\-\\delta\([Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4)in[AppendixJ](https://arxiv.org/html/2608.23910#A10)\), and ats=K​ws=Kwthe construction collapses to spherical sliced Wasserstein, so the partial version is a strict generalisation of the balanced one\.

## 6Experiments

10210^\{2\}10310^\{3\}10410^\{4\}10510^\{5\}10610^\{6\}10−410^\{\-4\}10−210^\{\-2\}10010^\{0\}10210^\{2\}10410^\{4\}10610^\{6\}N=n\+mN=n\+mtime \(s\), full profile for allkk≈\\approx1\.5⋅106×1\.5\\cdot 10^\{6\}\\timesPAWC \(compiled\)PAWC \(array\)Baseline B \(cuts\)Baseline A \(LP\)Figure 5:Measured cost of the complete profile\. Baseline B is the cut\-envelope solver, Baseline A the LP oracle; dashed segments are extrapolated \(N2​log⁡NN^\{2\}\\log N,N3N^\{3\}\)\. Fitted log–log slopes:1\.031\.03–1\.291\.29forPAWCagainst2\.002\.00for B\.We report thatPAWCcomputes what it claims, at the stated cost, and that the profile is the object applications want\. Full protocols, seeds, and the negative results we found along the way are in[AppendicesK](https://arxiv.org/html/2608.23910#A11)and[L](https://arxiv.org/html/2608.23910#A12); code and records accompany the submission\.

### 6\.1Exactness and scaling

Across504504instances spanning nine adversarial families \(clustered, near\-antipodal, seam\-straddling, tiny\-arc, and others\)PAWCmatches an LP oracle over the cardinality\-kkmatching polytope to4\.7×10−154\.7\\times 10^\{\-15\}and the cut\-envelope solver exactly, and every structural invariant — nestedness, the free\-gap invariant, cell balance, feasibility, and the validity ofθ⋆\\theta^\{\\star\}— holds at every step of every instance \([AppendixK](https://arxiv.org/html/2608.23910#A11)\)\.

[Figure5](https://arxiv.org/html/2608.23910#S6.F5)shows the cost of the entire profile\. The cut\-envelope baseline fits a log–log slope of2\.002\.00;PAWCfits1\.031\.03–1\.291\.29, with the excess over11attributable to cache effects rather than a hidden term: heap operation counts are exactly linear \(0\.81​N0\.81Npops,0\.31​N0\.31Npushes atN=104,105,106N=10^\{4\},10^\{5\},10^\{6\}alike\), and the published line algorithmPAWLmeasures1\.121\.12–1\.251\.25on the same hardware\. In absolute terms, one solve returning*all*transported fractions takes0\.090\.09ms atN=256N=256and0\.560\.56ms atN=2048N=2048, against4\.44\.4ms and1\.541\.54s for a*single*fraction from POT’s general partial solver\([Flamary et al\., 2021](https://arxiv.org/html/2608.23910#bib.bib13)\), and3030ms and11\.411\.4s for the seven fractions used in[Section6\.2](https://arxiv.org/html/2608.23910#S6.SS2)\. The sweep over the transported fraction is free\.

### 6\.2Partial matching of shape descriptors

The outward normal directions of a closed planar curve, sampled uniformly in arclength, form a measure on𝕊L1\\mathbb\{S\}^\{1\}\_\{L\}— the two\-dimensional extended Gaussian image\([Horn, 1984](https://arxiv.org/html/2608.23910#bib.bib14)\)\. It is invariant to translation, scale and starting point and rotates rigidly with the shape, so comparing shapes up to rotation is alignment on the circle, and its two failure modes are exactly the ones partial transport addresses:*occlusion*deletes part of the measure,*clutter*adds mass belonging to nothing\. It keeps no part structure, so it is far weaker than the descriptors built for this benchmark, which score0\.750\.75–0\.850\.85bullseye\([Ling and Jacobs, 2007](https://arxiv.org/html/2608.23910#bib.bib24), Table II\); what follows is not an entry in that benchmark, but a comparison of costs on one fixed descriptor\.

normal angles\(a\) query: 50% visible, 20% clutter0\.000\.250\.500\.751\.000\.00\.20\.4clutter fractionsuccess rate \(<5∘<5^\{\\circ\}\)\(b\) orientation, 50% visiblepawcρ=0\.8\\rho=0\.8full OTEGI correlation0\.00\.20\.40\.60\.80\.500\.701\.00visible fractionbullseye score\(c\) retrieval, 20% clutter

Figure 6:Partial matching of shape descriptors onmpeg\-7\. \(a\) one query: the visible arc of the boundary \(green\), the occluded remainder \(grey\), and the normal\-angle measure the matcher sees, with clutter in red\. \(b\) orientation success against clutter at half the boundary visible and \(c\) retrieval bullseye against the visible fraction at20%20\\%clutter, forPAWCat a fixedρ=0\.8\\rho=0\.8, full circular OT, and the extended\-Gaussian\-image correlation matcher\. OT fails on clutter; correlation fails on occlusion\.Table 1:Shape matching under occlusion and clutter on all14001400mpeg\-7silhouettes:vvis the visible fraction of the boundary,ccthe clutter fraction\.PAWCtransportsρ=1−c\\rho=1\-c, so thec=0c=0rows*are*full circular OT and tie by construction\. Orientation and correspondence average212212shapes per cell, retrieval138138queries against the full database\. “corr\.” is the correlation matcher at its best of three bandwidths; “NN” is mutual nearest neighbours in normal angle\.##### Protocol\.

All14001400silhouettes ofmpeg\-7ce\-shape\-1\([Latecki et al\., 2000](https://arxiv.org/html/2608.23910#bib.bib15)\); contours traced at the0\.50\.5level, resampled to128128points, converted to normal angles\. A query keeps a contiguous fractionvvof the arclength, replaces a fractionccof the survivors by uniform normals, and is rotated by a uniformly random angle\. Every method scores the same grid of360360rotations; only the cost differs\.PAWCtransportsρ=1−c\\rho=1\-c: the mass the task declares genuine\. Three tasks: recover the rotation \(success<5∘<5^\{\\circ\}\); rank the other13991399shapes and report thempeg\-7bullseye score; and score the pairs of the recovered plan against the arclength indices the query was built from \(F1F\_\{1\}; clutter samples have no correct partner\)\.

##### Result\.

[Table1](https://arxiv.org/html/2608.23910#S6.T1)separates the two failure modes\. The clean cell fixes the scale: uncontaminated and fully visible, this descriptor retrieves at0\.4570\.457, and on this representation no cost can do better\. Occlusion alone costs full OT little — withn≠mn\\neq mthe balanced problem already transports onlyK=min⁡\(n,m\)K=\\min\(n,m\)atoms, so size asymmetry supplies the needed partiality — but clutter is fatal to it: at full visibility andc=0\.2c=0\.2its bullseye falls to0\.0710\.071,16%16\\%of that ceiling, wherePAWCholds0\.3020\.302, or66%66\\%of it — a factor of4\.34\.3\(\+0\.231±0\.053\+0\.231\\pm 0\.053paired, ahead on9595of138138queries\), and atc=0\.4c=0\.4its orientation success falls to0\.450\.45wherePAWCis still at1\.001\.00\. The correlation matcher fails the other way round, collapsing from0\.3840\.384to0\.0520\.052in bullseye asvvfalls from11to0\.50\.5, because a truncated density correlates best where the template has most mass rather than where the visible piece belongs\.PAWCatρ=1−c\\rho=1\-cis at least as good as both baselines in all nine cells and strictly better in the six with clutter, and a*single*fixedρ=0\.8\\rho=0\.8used everywhere still beats both wherever there is clutter\. An unbalanced \(KL\-relaxed\) Sinkhorn cost at its best of three relaxation weights tiesPAWCon nearly complete queries and falls behind as the boundary disappears \(0\.710\.71against0\.850\.85atv=0\.35v=0\.35,c=0\.4c=0\.4\), with no single weight competitive across cells and at20×20\\timesthe cost \([AppendixL](https://arxiv.org/html/2608.23910#A12)\)\.

### 6\.3Robust fitting on𝕊2\\mathbb\{S\}^\{2\}

\(a\)ssw\(γ=1\\gamma=1\)

\(b\)sspw\(γ=1\.25\\gamma=1\.25\)

catalogue density inblue, fitted particles in colour

Figure 7:Fitting500500particles to theusgsearthquake catalogue whose minibatches are contaminated atε=0\.3\\varepsilon=0\.3, over a Natural Earth coastline\. The blue background is a kernel estimate of the catalogue’s own density — the target the particles should cover\.ssw\(γ=1\\gamma=1\) scatters particles across the Pacific and the continental interiors, where no earthquakes are; the partial fit stays on the ridges and subduction zones\.Table 2:Spherical fitting against a contaminated target, eight seeds per cell\. Energy distance to clean target samples,×10−3\\times 10^\{\-3\}\.sspwtransports the rule fractionγ=1/\(1−ε\)\\gamma=1/\(1\-\\varepsilon\)rounded to the grid, so theε=0\\varepsilon=0row*is*ssw; “gain” is the reduction fromssw, “wins” counts seeds ahead, and “best” is the gain at the bestγ\\gammaof six on the grid, which atε=0\\varepsilon=0is a selection over noise\.We useSSPW\\mathrm\{SSPW\}as a training loss and compare against the method it generalises, spherical sliced Wasserstein \(ssw\), which is itsρ=1\\rho=1case\. One design point matters: when fitting a model, partiality must sit on the*target*side\. A trimmed model particle receives no gradient and never moves again — and those are precisely the badly placed particles, since they are the expensive ones to match\. We therefore draw target batches of sizem=γ​nm=\\gamma n,γ≥1\\gamma\\geq 1, and transportk=K=nk=K=n: every particle moves, and the1−1/γ1\-1/\\gammaof the target batch the matching declines to use is what partial transport buys\.

500500particles from a uniform start,3232slices redrawn per step,20002000Adam steps, gradients taken with the matching held fixed \(the envelope theorem\) and retracted to the sphere; a fractionε\\varepsilonof every target batch is replaced by a uniform point\. Quality is the geodesic energy distance to40004000*clean*target points, which shares no implementation with the training loss\. Two targets: a five\-component von Mises–Fisher mixture with unequal masses and concentrations, and94 95394\\,953earthquake epicentres of magnitude≥4\.5\\geq 4\.5from theusgscatalogue, 2010–2024\([U\.S\. Geological Survey, 2026](https://arxiv.org/html/2608.23910#bib.bib16)\), held out80/2080/20\.

0\.00\.51\.01\.51\.001\.251\.432\.00target\-batch ratioγ\\gammaenergy distance /sswsynthetic vMF mixture on𝕊2\\mathbb\{S\}^\{2\}ε=0\.0\\varepsilon=0\.0ε=0\.2\\varepsilon=0\.2ε=0\.4\\varepsilon=0\.4Figure 8:Energy distance againstγ\\gammaon the synthetic mixture, each curve divided by its ownγ=1\\gamma=1value\. The optimum moves right as contamination grows; the clean curve leaves the panel at once\.[Figure8](https://arxiv.org/html/2608.23910#S6.F8)shows the shape of the trade\-off: on clean data any trimming costs accuracy, and as contamination grows the optimum migrates towards1/\(1−ε\)1/\(1\-\\varepsilon\)and the curve flattens, so the exact value ofγ\\gammamatters less than being on the right side of11\.[Table2](https://arxiv.org/html/2608.23910#S6.T2)gives the same picture on both targets: fromε=0\.1\\varepsilon=0\.1upward the rule cuts the energy distance to the clean target by4545–6868per cent on the synthetic mixture and5353–7070per cent on the catalogue, every seed agreeing, while theε=0\\varepsilon=0row — wheresswis best — is the control that licenses reading this as robustness rather than a smaller effective step \([Figure7](https://arxiv.org/html/2608.23910#S6.F7)shows the difference geographically\)\. The one cell where the rule underperforms is the catalogue atε=0\.4\\varepsilon=0\.4: with40%40\\%of a heavily clustered target replaced by uniform noise, some noise lands on the fault lines and trimming*less*than the nominal contamination is better\.

## 7Discussion

PAWCcomputes the complete partial\-transport profile on the circle in the same asymptotic cost as sorting, with no search over cuts, and returns a single cut valid for every cardinality\. Three limitations bound the result\. Equal atomic weights make every activation add exactly one source and one target; non\-uniform masses would require event\-driven handling of saturating capacities\. The constant\-time chain oracle relies on theW1W\_\{1\}geodesic cost;p\>1p\>1and general Monge costs need separate analysis\. Degeneracies — coincident supports, antipodal ties, equal candidate marginals — are handled by deterministic tie\-breaking or symbolic perturbation rather than intrinsically\. On the application side the transported fraction is set by a rule rather than inferred;[AppendixL](https://arxiv.org/html/2608.23910#A12)reports what we tried and where inference failed\.

#### Reproducibility statement

[AppendicesK](https://arxiv.org/html/2608.23910#A11)and[L](https://arxiv.org/html/2608.23910#A12)give the full protocols, seeds, machine and package versions for every number reported\. The reference and optimised solvers, the LP and cut\-envelope baselines, the invariant checks, all experiment scripts and the raw records accompany the submission; each figure and table in this paper is generated from those records by a script, not transcribed\.

#### Acknowledgments

This work was supported by NSF CAREER Award \#2339898 and NSF DMS Award \#2603774\.

## References

- R\. K\. Ahuja, T\. L\. Magnanti, and J\. B\. OrlinNetwork flows: theory, algorithms, and applications\.Prentice Hall,Englewood Cliffs, NJ\.Cited by:[§K\.4](https://arxiv.org/html/2608.23910#A11.SS4.p2.1),[§D\.1](https://arxiv.org/html/2608.23910#A4.SS1.p5.1.1),[§I\.2](https://arxiv.org/html/2608.23910#A9.SS2.p2.1.1)\.
- Baiet al\.\(2023\)Y\. Bai, B\. Schmitzer, M\. Thorpe, and S\. KolouriSliced optimal partial transport\.InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,pp\. 13681–13690\.Cited by:[§1](https://arxiv.org/html/2608.23910#S1.p1.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Bardelli and Mennucci \(2017\)E\. Bardelli and A\. C\. G\. MennucciProbability measures on infinite\-dimensional Stiefel manifolds\.Journal of Geometric Mechanics9\(3\),pp\. 291–316\.Cited by:[§J\.1](https://arxiv.org/html/2608.23910#A10.SS1.p2.3)\.
- Bendokatet al\.\(2020\)T\. Bendokat, R\. Zimmermann, and P\.\-A\. AbsilA Grassmann manifold handbook: basic geometry and computational aspects\.arXiv preprint arXiv:2011\.13699\.Cited by:[§J\.1](https://arxiv.org/html/2608.23910#A10.SS1.p2.2)\.
- Bonetet al\.\(2023\)C\. Bonet, P\. Berg, N\. Courty, F\. Septier, L\. Drumetz, and M\. PhamSpherical sliced\-Wasserstein\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=jXQ0ipgMdU)Cited by:[§J\.1](https://arxiv.org/html/2608.23910#A10.SS1.p2.1),[§J\.1](https://arxiv.org/html/2608.23910#A10.SS1.p3.2),[§J\.2](https://arxiv.org/html/2608.23910#A10.SS2.p1.1),[Appendix J](https://arxiv.org/html/2608.23910#A10.p1.1),[§K\.6](https://arxiv.org/html/2608.23910#A11.SS6.SSS0.Px1.p1.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p2.1),[Figure 4](https://arxiv.org/html/2608.23910#S5.F4),[§5](https://arxiv.org/html/2608.23910#S5.p1.1),[Remark 7](https://arxiv.org/html/2608.23910#Thmremark7.p1.1)\.
- Bonneel and Coeurjolly \(2019\)N\. Bonneel and D\. CoeurjollySPOT: sliced partial optimal transport\.ACM Transactions on Graphics38\(4\),pp\. 1–13\.Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Caffarelli and McCann \(2010\)L\. A\. Caffarelli and R\. J\. McCannFree boundaries in optimal transport and Monge–Ampère obstacle problems\.Annals of Mathematics171\(2\),pp\. 673–730\.External Links:[Document](https://dx.doi.org/10.4007/annals.2010.171.673)Cited by:[§2\.1](https://arxiv.org/html/2608.23910#S2.SS1.p1.2)\.
- Chapelet al\.\(2021\)L\. Chapel, R\. Flamary, H\. Wu, C\. Févotte, and G\. GassoUnbalanced optimal transport through non\-negative penalized linear regression\.Advances in Neural Information Processing Systems34,pp\. 23270–23282\.Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Chapel and Tavenard \(2025\)L\. Chapel and R\. TavenardOne for all and all for one: efficient computation of partial wasserstein distances on the line\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=kzEPsHbJDv)Cited by:[§C\.1](https://arxiv.org/html/2608.23910#A3.SS1.p1.1),[§C\.1](https://arxiv.org/html/2608.23910#A3.SS1.p3.1.1),[§C\.1](https://arxiv.org/html/2608.23910#A3.SS1.p6.1.1),[§C\.1](https://arxiv.org/html/2608.23910#A3.SS1.p8.1.1),[§C\.1](https://arxiv.org/html/2608.23910#A3.SS1.p9.2),[§C\.2](https://arxiv.org/html/2608.23910#A3.SS2.p8.2.1),[§D\.1](https://arxiv.org/html/2608.23910#A4.SS1.p1.1),[Figure 12](https://arxiv.org/html/2608.23910#A7.F12),[§G\.1](https://arxiv.org/html/2608.23910#A7.SS1.p4.1.1),[§G\.1](https://arxiv.org/html/2608.23910#A7.SS1.p6.1.1),[Appendix G](https://arxiv.org/html/2608.23910#A7.p1.1),[§I\.2](https://arxiv.org/html/2608.23910#A9.SS2.p2.1.1),[§1](https://arxiv.org/html/2608.23910#S1.p1.1),[§1](https://arxiv.org/html/2608.23910#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1),[Figure 2](https://arxiv.org/html/2608.23910#S3.F2)\.
- Cuturi \(2013\)M\. CuturiSinkhorn distances: lightspeed computation of optimal transport\.Advances in Neural Information Processing Systems26\.Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Delonet al\.\(2010\)J\. Delon, J\. Salomon, and A\. SobolevskiFast transport optimization for Monge costs on the circle\.SIAM Journal on Applied Mathematics70\(7\),pp\. 2239–2258\.External Links:[Document](https://dx.doi.org/10.1137/090772708)Cited by:[§C\.2](https://arxiv.org/html/2608.23910#A3.SS2.p4.2),[§C\.2](https://arxiv.org/html/2608.23910#A3.SS2.p6.2),[§1](https://arxiv.org/html/2608.23910#S1.p3.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p2.1)\.
- Díaz Martínet al\.\(2024\)R\. Díaz Martín, I\. V\. Medri, Y\. Bai, X\. Liu, K\. Yan, G\. Rohde, and S\. KolouriLCOT: linear circular optimal transport\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=49z97Y9lMq)Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p2.1)\.
- Figalli \(2010\)A\. FigalliThe optimal partial transport problem\.Archive for Rational Mechanics and Analysis195\(2\),pp\. 533–560\.External Links:[Document](https://dx.doi.org/10.1007/s00205-008-0212-7)Cited by:[§2\.1](https://arxiv.org/html/2608.23910#S2.SS1.p1.2)\.
- Flamaryet al\.\(2021\)R\. Flamary, N\. Courty, A\. Gramfort, M\. Z\. Alaya, A\. Boisbunon, S\. Chambon, L\. Chapel, A\. Corenflos, K\. Fatras, N\. Fournier, L\. Gautheron, N\. T\.H\. Gayraud, H\. Janati, A\. Rakotomamonjy, I\. Redko, A\. Rolet, A\. Schutz, V\. Seguy, D\. J\. Sutherland, R\. Tavenard, A\. Tong, and T\. VayerPOT: Python Optimal Transport\.Journal of Machine Learning Research22\(78\),pp\. 1–8\.External Links:[Link](http://jmlr.org/papers/v22/20-451.html)Cited by:[§K\.6](https://arxiv.org/html/2608.23910#A11.SS6.SSS0.Px1.p1.1),[§6\.1](https://arxiv.org/html/2608.23910#S6.SS1.p2.1)\.
- Horn \(1984\)B\. K\. P\. HornExtended Gaussian images\.Proceedings of the IEEE72\(12\),pp\. 1671–1686\.Cited by:[§6\.2](https://arxiv.org/html/2608.23910#S6.SS2.p1.1)\.
- Lateckiet al\.\(2000\)L\. J\. Latecki, R\. Lakämper, and U\. EckhardtShape descriptors for non\-rigid shapes with a single closed contour\.InIEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 424–429\.Cited by:[§6\.2](https://arxiv.org/html/2608.23910#S6.SS2.SSS0.Px1.p1.1)\.
- Ling and Jacobs \(2007\)H\. Ling and D\. W\. JacobsShape classification using the inner\-distance\.IEEE Transactions on Pattern Analysis and Machine Intelligence29\(2\),pp\. 286–299\.Cited by:[§6\.2](https://arxiv.org/html/2608.23910#S6.SS2.p1.1)\.
- Liuet al\.\(2025\)X\. Liu, Y\. Bai, R\. Díaz Martín, K\. Shi, A\. Shahbazi, B\. A\. Landman, C\. Chang, and S\. KolouriLinear spherical sliced optimal transport: a fast metric for comparing spherical data\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=fgUFZAxywx)Cited by:[Appendix J](https://arxiv.org/html/2608.23910#A10.p1.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p2.1),[Remark 7](https://arxiv.org/html/2608.23910#Thmremark7.p1.1)\.
- Nietertet al\.\(2022\)S\. Nietert, Z\. Goldfeld, and R\. CummingsOutlier\-robust optimal transport: duality, structure, and statistical analysis\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 11691–11719\.Cited by:[§1](https://arxiv.org/html/2608.23910#S1.p2.1)\.
- Peyré and Cuturi \(2019\)G\. Peyré and M\. CuturiComputational optimal transport: with applications to data science\.Foundations and Trends in Machine Learning, Vol\.11,Now Publishers\.External Links:[Document](https://dx.doi.org/10.1561/2200000073)Cited by:[§L\.2](https://arxiv.org/html/2608.23910#A12.SS2.p1.1),[§1](https://arxiv.org/html/2608.23910#S1.p1.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Phataket al\.\(2023\)A\. Phatak, S\. Raghvendra, C\. Tripathy, and K\. ZhangComputing all optimal partial transports\.InInternational Conference on Learning Representations,Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Rabinet al\.\(2011\)J\. Rabin, J\. Delon, and Y\. GousseauTransportation distances on the circle\.Journal of Mathematical Imaging and Vision41\(1–2\),pp\. 147–167\.External Links:[Document](https://dx.doi.org/10.1007/s10851-011-0284-0)Cited by:[§C\.2](https://arxiv.org/html/2608.23910#A3.SS2.p4.2),[§C\.2](https://arxiv.org/html/2608.23910#A3.SS2.p6.2),[§1](https://arxiv.org/html/2608.23910#S1.p3.1),[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p2.1)\.
- Rabinet al\.\(2012\)J\. Rabin, G\. Peyré, J\. Delon, and M\. BernotWasserstein barycenter and its application to texture mixing\.InScale Space and Variational Methods in Computer Vision \(SSVM 2011\),pp\. 435–446\.Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- Séjournéet al\.\(2022\)T\. Séjourné, F\. Vialard, and G\. PeyréFaster unbalanced optimal transport: translation invariant Sinkhorn and 1\-D Frank\-Wolfe\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 4995–5021\.Cited by:[§2\.2](https://arxiv.org/html/2608.23910#S2.SS2.p1.1)\.
- U\.S\. Geological Survey \(2026\)U\.S\. Geological SurveyANSS comprehensive earthquake catalog \(ComCat\)\.Note:[https://earthquake\.usgs\.gov/fdsnws/event/1/](https://earthquake.usgs.gov/fdsnws/event/1/)events of magnitude≥4\.5\\geq 4\.5, 2010–2024; retrieved 18 August 2026Cited by:[§6\.3](https://arxiv.org/html/2608.23910#S6.SS3.p2.1)\.
- Villani \(2009\)C\. VillaniOptimal transport: old and new\.Grundlehren der mathematischen Wissenschaften, Vol\.338,Springer,Berlin\.External Links:ISBN 9783540710509Cited by:[§1](https://arxiv.org/html/2608.23910#S1.p1.1)\.

## Appendix overview

[AppendixA](https://arxiv.org/html/2608.23910#A1)comes first and runs[Algorithm1](https://arxiv.org/html/2608.23910#alg1)by hand on one instance, showing the heap, the linked list and the free\-gap bookkeeping at every activation: it is the concrete account of what the algorithm does, and the mechanisms it exercises are the ones the rest of the appendix proves correct\.[AppendicesB](https://arxiv.org/html/2608.23910#A2),[C](https://arxiv.org/html/2608.23910#A3),[D](https://arxiv.org/html/2608.23910#A4),[E](https://arxiv.org/html/2608.23910#A5),[F](https://arxiv.org/html/2608.23910#A6),[G](https://arxiv.org/html/2608.23910#A7),[H](https://arxiv.org/html/2608.23910#A8)and[I](https://arxiv.org/html/2608.23910#A9)then contain the full development and every proof, in the order in which the main text uses them: notation and the cardinality\-kkformulation; the line structure inherited fromPAWLand the cut envelope; nested active sets, the common\-cut lemma and the cyclic\-neighbour theorem; cells and their marginals; the free\-gap invariant, the exact greedy theorem and the constructive simultaneous cut; the doubled\-sequence preprocessing that makes candidate marginalsO⁡\(1\)O\(1\); correctness and complexity; and plan recovery with the interpolation for non\-integer masses\.[AppendixJ](https://arxiv.org/html/2608.23910#A10)develops the spherical construction and its concentration bound\.

[AppendixK](https://arxiv.org/html/2608.23910#A11)reports the numerical validation — solvers and trust hierarchy, exactness against an LP oracle, the structural invariants, the complexity study, the one\-cut experiment of[SectionK\.5](https://arxiv.org/html/2608.23910#A11.SS5)and the spherical estimator’s behaviour\.[AppendixL](https://arxiv.org/html/2608.23910#A12)gives the protocols for the two applications in the main text, the unbalanced\-transport comparison, the in\-situ exactness check, and the application families we piloted and dropped\.

## Appendix AA worked example, step by step

This appendix runs[Algorithm1](https://arxiv.org/html/2608.23910#alg1)by hand on a single instance, so that every mechanism the paper introduces can be seen firing on concrete numbers before any of it is proved\. Notation is the main text’s; the statements the trace exercises —[Lemmas5](https://arxiv.org/html/2608.23910#Thmlemma5),[9](https://arxiv.org/html/2608.23910#Thmtheorem9)and[2](https://arxiv.org/html/2608.23910#Thmproposition2)— are proved in the sections that follow it\. The mechanisms are: a wrap\-around selection, a merged\-cell selection with matching revocation, lazy heap skips, free\-gap inheritance including the consumption of a selected cell’s own representative, and the two\-directed\-cell endgame\. A standalone copy is kept atdemos/pawc\_demo\.tex\. We run PAWC on the circle of circumferenceL=12L=12with unit weightsw=1w=1and geodesic costd𝕊1​\(u,v\)=min⁡\(\|u−v\|,L−\|u−v\|\)d\_\{\\mathbb\{S\}^\{1\}\}\(u,v\)=\\min\(\|u\-v\|,\\,L\-\|u\-v\|\):

x\\displaystyle x=\{0\.4,4\.1,4\.5,8\.0\}\\displaystyle=\\\{0\.4,\\;4\.1,\\;4\.5,\\;8\.0\\\}\(blue circles, sources\),\\displaystyle\\text\{\(blue circles, sources\)\},y\\displaystyle y=\{1\.6,5\.0,5\.4,11\.4\}\\displaystyle=\\\{1\.6,\\;5\.0,\\;5\.4,\\;11\.4\\\}\(orange circles, targets\)\.\\displaystyle\\text\{\(orange circles, targets\)\}\.The cyclic type patternx​y​x​x​y​y​x​yx\\,y\\,x\\,x\\,y\\,y\\,x\\,ymatches the PAWL walkthrough — but the wrap\-around gap\(y4,x1\)\(y\_\{4\},x\_\{1\}\)across00is now short \(1\.01\.0\), and this changes everything: the optimal partial plan will*use*the wrap atk=2,3k=2,3and*abandon*it atk=4k=4\. This shifting circulation is precisely why the circle does not reduce to a single line problem, and what PAWC’s machinery \(cells, free gaps, the simultaneous cut\) is built to tame\. The instance is chosen so that every mechanism fires: a wrap\-around selection, a merged\-cell selection with matching revocation, four lazy heap skips, free\-gap inheritance \(including consumption of a selected cell’s own representative\), and the two\-directed\-cell endgame\.

### Step 0 — Input onS1S^\{1\}, and the naive baseline

Cutting the circle open at any of theN=8N=8inter\-atom gaps and unrolling gives a line instance; the circular optimum is the lower envelope over cuts,Ck∘=minr⁡Ck,rlineC^\{\\circ\}\_\{k\}=\\min\_\{r\}C^\{\\text\{line\}\}\_\{k,r\}\(the cut envelope\)\. Running PAWL once per cut costsO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)\. PAWC produces the same profile — and a single cutθ⋆\\theta^\{\\star\}valid for*all*kkat once \([Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9)\) — in oneO⁡\(N​log⁡N\)O\(N\\log N\)sweep\. \(Atom spacing in the circle diagrams is schematic, spread for legibility; the gray coordinates are the truth\.\)

00x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}0\.41\.64\.14\.55\.05\.48\.011\.4clockwise

Atoms are read clockwise from00; hollow markers are*inactive*atoms \(none transported yet\)\. Notey4y\_\{4\}andx1x\_\{1\}sit on opposite sides of00, only1\.01\.0apart along the wrap\.

### Step 1 — Precomputation on the doubled sequence \([AppendixG](https://arxiv.org/html/2608.23910#A7)\)

To make every clockwise cell an ordinary interval, the sorted cyclic sequence is doubled:z~t\+8=z~t\+L\\tilde\{z\}\_\{t\+8\}=\\tilde\{z\}\_\{t\}\+L,t=1,…,8t=1,\\dots,8, givingz~1,…,z~16\\tilde\{z\}\_\{1\},\\dots,\\tilde\{z\}\_\{16\}\. One sweep computes the prefix*differential ranks*RtR\_\{t\}\(\+1\+1at a source,−1\-1at a target\), the signed prefix sumsStS\_\{t\}, the minimal\-chain predecessorsptp\_\{t\}\(last previous occurrence of the same rank\), and the maximal\-chain prefix costsQtQ\_\{t\}— exactly PAWL’s Algorithm 1 run on the doubled line\. The rank walk repeats with periodNN\(total balancen=mn=m\):

z~t\\tilde\{z\}\_\{t\}RtR\_\{t\}012x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}x1′x\_\{1\}^\{\\prime\}y1′y\_\{1\}^\{\\prime\}x2′x\_\{2\}^\{\\prime\}x3′x\_\{3\}^\{\\prime\}y2′y\_\{2\}^\{\\prime\}y3′y\_\{3\}^\{\\prime\}x4′x\_\{4\}^\{\\prime\}y4′y\_\{4\}^\{\\prime\}\+L\+L\(second copy\)

These rows are the whole oracle;StS\_\{t\}is listed so theQQrecursion can be checked by eye\. Note the index convention:ptp\_\{t\}is the*predecessor*, the lasts<ts<twithRs=RtR\_\{s\}=R\_\{t\}, so the minimal chain ending atttis\[pt\+1,t\]\[p\_\{t\}\+1,t\]— one position to the right ofptp\_\{t\}\. For instancep2=0p\_\{2\}=0and the minimal chain ending aty1y\_\{1\}is\[1,2\]=\{x1,y1\}\[1,2\]=\\\{x\_\{1\},y\_\{1\}\\\}\. The recursion isQt=Qpt\+w​\|St−Spt\|Q\_\{t\}=Q\_\{p\_\{t\}\}\+w\\lvert S\_\{t\}\-S\_\{p\_\{t\}\}\\rvert, e\.g\.Q6=Q2\+\|S6−S2\|=1\.2\+\|−3\.0−\(−1\.2\)\|=3\.0Q\_\{6\}=Q\_\{2\}\+\\lvert S\_\{6\}\-S\_\{2\}\\rvert=1\.2\+\\lvert\-3\.0\-\(\-1\.2\)\\rvert=3\.0, andQt=0Q\_\{t\}=0whenptp\_\{t\}does not exist\. Thet=0t=0column is the empty prefix, needed whenevera=1a=1\.

For any balanced interval\[a,b\]\[a,b\]withb−a<Nb\-a<N\([Proposition2](https://arxiv.org/html/2608.23910#Thmproposition2)\):cℝ​\(\[a,b\]\)=Qb−Qa−1c\_\{\\mathbb\{R\}\}\(\[a,b\]\)=Q\_\{b\}\-Q\_\{a\-1\}, and the marginal of a cell with endpointsa,ba,bis one line of arithmetic \([38](https://arxiv.org/html/2608.23910#A7.E38)\):

m⁡\(\[a,b\]\)=\(Qb−Qa−1\)−\(Qb−1−Qa\)\.m\(\[a,b\]\)=\\bigl\(Q\_\{b\}\-Q\_\{a\-1\}\\bigr\)\-\\bigl\(Q\_\{b\-1\}\-Q\_\{a\}\\bigr\)\.Worked example: the cell\[x2,y3\]=\[3,6\]\[x\_\{2\},y\_\{3\}\]=\[3,6\]hasm=\(Q6−Q2\)−\(Q5−Q3\)=\(3\.0−1\.2\)−\(3\.0−2\.5\)=1\.8−0\.5=1\.3m=\(Q\_\{6\}\-Q\_\{2\}\)\-\(Q\_\{5\}\-Q\_\{3\}\)=\(3\.0\-1\.2\)\-\(3\.0\-2\.5\)=1\.8\-0\.5=\\mathbf\{1\.3\}\. This cell does not exist yet — it is created when the three cells around\[x3,y2\]\[x\_\{3\},y\_\{2\}\]merge atk=1k\{=\}1, and it is selected atk=3k\{=\}3\(Step 5\)\.

### Step 2 — Cells, free gaps, and the initial heap \([AppendicesE](https://arxiv.org/html/2608.23910#A5)and[F](https://arxiv.org/html/2608.23910#A6)\)

The inactive atoms partitionS1S^\{1\}into*cells*\. Initially every cell is a single gap between cyclic neighbors; the six with opposite\-type endpoints are*candidate cells*\(green arcs\) with marginal equal to their clockwise arc length;\(x2,x3\)\(x\_\{2\},x\_\{3\}\)and\(y2,y3\)\(y\_\{2\},y\_\{3\}\)are not candidates\. Every cell contains a*free gap*— an original gap never absorbed by a selected cell \([Lemma5](https://arxiv.org/html/2608.23910#Thmlemma5)\) — and stores one boxed*representative*; initially each cell’s representative is its own gap\.

001\.22\.50\.52\.63\.41\.0x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}heap \(sorted\)\(x3,y2\)\(x\_\{3\},y\_\{2\}\): 0\.5\(y4,x1\)\(y\_\{4\},x\_\{1\}\): 1\.0\(x1,y1\)\(x\_\{1\},y\_\{1\}\): 1\.2\(y1,x2\)\(y\_\{1\},x\_\{2\}\): 2\.5\(y3,x4\)\(y\_\{3\},x\_\{4\}\): 2\.6\(x4,y4\)\(x\_\{4\},y\_\{4\}\): 3\.4

Note the wrap\-around candidate\(y4,x1\)\(y\_\{4\},x\_\{1\}\)at the top: on the circle it is a perfectly ordinary cell\. The two same\-type gaps carry free gaps and representatives too — the invariant is about*cells*, not candidates\.

### Step 3 — Iterationk=1k=1: pop\(x3,y2\)\(x\_\{3\},y\_\{2\}\); three cells merge into one

The cheapest cell\(x3,y2\)\(x\_\{3\},y\_\{2\}\), marginal0\.50\.5, is selected:x3→y2x\_\{3\}\\\!\\to\\\!y\_\{2\},C1∘=0\.5C^\{\\circ\}\_\{1\}=0\.5\. Cells\[x2,x3\]\[x\_\{2\},x\_\{3\}\],\[x3,y2\]\[x\_\{3\},y\_\{2\}\],\[y2,y3\]\[y\_\{2\},y\_\{3\}\]merge into\[x2,y3\]\[x\_\{2\},y\_\{3\}\], whose endpoints have opposite types — a new candidate with marginal1\.31\.3\(computed in Step 1\)\. The selected cell’s gap turns*used*; the merged cell inherits the boxed representative of its*left*unselected neighbor\[x2,x3\]\[x\_\{2\},x\_\{3\}\]; the right neighbor’s gap\(y2,y3\)\(y\_\{2\},y\_\{3\}\)stays free but unstored\.

00inheritedused1\.22\.52\.63\.41\.0new: 1\.3x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}heap afterk=1k\{=\}1popped:\(x3,y2\)\(x\_\{3\},y\_\{2\}\)\(y4,x1\)\(y\_\{4\},x\_\{1\}\): 1\.0\(x1,y1\)\(x\_\{1\},y\_\{1\}\): 1\.2\(x2,y3\)\(x\_\{2\},y\_\{3\}\): 1\.3\(y1,x2\)\(y\_\{1\},x\_\{2\}\): 2\.5\(y3,x4\)\(y\_\{3\},x\_\{4\}\): 2\.6\(x4,y4\)\(x\_\{4\},y\_\{4\}\): 3\.4

### Step 4 — Iterationk=2k=2: the wrap\-around cell is selected

Next cheapest is the wrap cell\(y4,x1\)\(y\_\{4\},x\_\{1\}\), marginal1\.01\.0: the matchx1→y4x\_\{1\}\\\!\\to\\\!y\_\{4\}crosses00\.C2∘=1\.5C^\{\\circ\}\_\{2\}=1\.5\. No cut placed at the top could ever find this plan — this is the step where the circle genuinely departs from every line relaxation cut near00\. Cells\[x4,y4\]\[x\_\{4\},y\_\{4\}\],\[y4,x1\]\[y\_\{4\},x\_\{1\}\],\[x1,y1\]\[x\_\{1\},y\_\{1\}\]merge into\[x4,y1\]\[x\_\{4\},y\_\{1\}\]\(opposite types\): new candidate, marginalm=\(Q10−Q6\)−\(Q9−Q7\)=4\.6−1\.0=3\.6m=\(Q\_\{10\}\-Q\_\{6\}\)\-\(Q\_\{9\}\-Q\_\{7\}\)=4\.6\-1\.0=\\mathbf\{3\.6\}, inheriting the representative of\[x4,y4\]\[x\_\{4\},y\_\{4\}\]\.

00inheritedused2\.52\.61\.3new:\[x4,y1\]\[x\_\{4\},y\_\{1\}\]: 3\.6x1→y4x\_\{1\}\\to y\_\{4\}crosses00x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}heap afterk=2k\{=\}2popped:\(y4,x1\)\(y\_\{4\},x\_\{1\}\)\(x1,y1\)\(x\_\{1\},y\_\{1\}\): 1\.2\(x2,y3\)\(x\_\{2\},y\_\{3\}\): 1\.3\(y1,x2\)\(y\_\{1\},x\_\{2\}\): 2\.5\(y3,x4\)\(y\_\{3\},x\_\{4\}\): 2\.6\(x4,y4\)\(x\_\{4\},y\_\{4\}\): 3\.4\(x4,y1\)\(x\_\{4\},y\_\{1\}\): 3\.6

### Step 5 — Iterationk=3k=3: a lazy skip, then the merged cell fires

The heap’s top,\(x1,y1\):1\.2\(x\_\{1\},y\_\{1\}\):1\.2, is*stale*:x1x\_\{1\}was activated by the wrap selection\. Lazy deletion discards it on pop \(validity check: both endpoints inactive, cyclic successors, opposite types\)\. Next is the merged cell\[x2,y3\]:1\.3\[x\_\{2\},y\_\{3\}\]:1\.3— valid\. Its endpoints activate and the cell’s interior is rematched in unwrapped order:x2→y2x\_\{2\}\\\!\\to\\\!y\_\{2\},x3→y3x\_\{3\}\\\!\\to\\\!y\_\{3\},*revoking*x3→y2x\_\{3\}\\\!\\to\\\!y\_\{2\}\.C3∘=2\.8C^\{\\circ\}\_\{3\}=2\.8\. Merging\[y1,x2\]\+\[x2,y3\]\+\[y3,x4\]→\[y1,x4\]\[y\_\{1\},x\_\{2\}\]\+\[x\_\{2\},y\_\{3\}\]\+\[y\_\{3\},x\_\{4\}\]\\to\[y\_\{1\},x\_\{4\}\]gives a new candidate, marginal\(Q7−Q1\)−\(Q6−Q2\)=5\.6−1\.8=3\.8\(Q\_\{7\}\-Q\_\{1\}\)\-\(Q\_\{6\}\-Q\_\{2\}\)=5\.6\-1\.8=\\mathbf\{3\.8\}\. Crucially, the selected cell’s own boxed representative\(x2,x3\)\(x\_\{2\},x\_\{3\}\)is*consumed*along with all its gaps — this is exactly why[Lemma5](https://arxiv.org/html/2608.23910#Thmlemma5)makes the merged cell inherit from an*unselected*neighbor: here the left one,\[y1,x2\]\[y\_\{1\},x\_\{2\}\], donating gap\(y1,x2\)\(y\_\{1\},x\_\{2\}\)\.

00inheritedused\(incl\. old rep\.\)\[x4,y1\]\[x\_\{4\},y\_\{1\}\]: 3\.6new:\[y1,x4\]\[y\_\{1\},x\_\{4\}\]: 3\.8rematchedin orderx1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}heap afterk=3k\{=\}3\(x1,y1\)\(x\_\{1\},y\_\{1\}\): 1\.2×\\timespopped:\(x2,y3\)\(x\_\{2\},y\_\{3\}\)\(y1,x2\)\(y\_\{1\},x\_\{2\}\): 2\.5\(y3,x4\)\(y\_\{3\},x\_\{4\}\): 2\.6\(x4,y4\)\(x\_\{4\},y\_\{4\}\): 3\.4\(x4,y1\)\(x\_\{4\},y\_\{1\}\): 3\.6\(y1,x4\)\(y\_\{1\},x\_\{4\}\): 3\.8

### Step 6 — Iterationk=4k=4: three skips, the endgame, and a circulation shift

Three stale entries are popped and discarded in a row:\(y1,x2\)\(y\_\{1\},x\_\{2\}\),\(y3,x4\)\(y\_\{3\},x\_\{4\}\),\(x4,y4\)\(x\_\{4\},y\_\{4\}\)— each has an active endpoint\. Only two inactive atoms remain,y1y\_\{1\}andx4x\_\{4\}, of opposite types: the endgame\. They bound*two*directed cells,\[x4,y1\]\[x\_\{4\},y\_\{1\}\]through the top \(marginal3\.63\.6\) and its complement\[y1,x4\]\[y\_\{1\},x\_\{4\}\]through the bottom \(3\.83\.8\); both sit in the heap, and the pop order selects the cheaper automatically\. Selecting\[x4,y1\]\[x\_\{4\},y\_\{1\}\]activatesx4,y1x\_\{4\},y\_\{1\}and rematches its interior\{y4,x1\}\\\{y\_\{4\},x\_\{1\}\\\}in unwrapped order:x4→y4x\_\{4\}\\\!\\to\\\!y\_\{4\},x1→y1x\_\{1\}\\\!\\to\\\!y\_\{1\}—*revoking the wrap match*x1→y4x\_\{1\}\\\!\\to\\\!y\_\{4\}\. The circulation that was optimal atk=2,3k=2,3is abandoned atk=4k=4:C4∘=2\.8\+3\.6=6\.4C^\{\\circ\}\_\{4\}=2\.8\+3\.6=6\.4\.

00wrap revokedx4→y4x\_\{4\}\\to y\_\{4\}x1→y1x\_\{1\}\\to y\_\{1\}selected: 3\.6complement: 3\.8x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}heap duringk=4k\{=\}4\(y1,x2\)\(y\_\{1\},x\_\{2\}\): 2\.5×\\times\(y3,x4\)\(y\_\{3\},x\_\{4\}\): 2\.6×\\times\(x4,y4\)\(x\_\{4\},y\_\{4\}\): 3\.4×\\timespopped:\[x4,y1\]\[x\_\{4\},y\_\{1\}\]\[y1,x4\]\[y\_\{1\},x\_\{4\}\]: 3\.8

### Step 7 —[Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9): the simultaneous cutθ⋆\\theta^\{\\star\}

Two gaps survive as free:\(y1,x2\)\(y\_\{1\},x\_\{2\}\)and\(y3,x4\)\(y\_\{3\},x\_\{4\}\)\. The representative maintained through every merge — last held by the complementary cell\[y1,x4\]\[y\_\{1\},x\_\{4\}\]— isθ⋆=\(y1,x2\)\\theta^\{\\star\}=\(y\_\{1\},x\_\{2\}\): cutting there and running plain PAWL on the unrolled line reproducesCk∘C^\{\\circ\}\_\{k\}for*every*kkat once\. The table below \(each row an exhaustively computed line profile\) shows why this is not automatic: a gap can be free*at some*kkyet fail at another\. In particular\(x4,y4\)\(x\_\{4\},y\_\{4\}\)is only consumed at the last step and matchesk≤3k\\leq 3but fails atk=4k=4; and the wrap gap\(y4,x1\)\(y\_\{4\},x\_\{1\}\), used atk=2k=2, happens to carry no flow again atk=4k=4— “used” is a*for\-all\-kk*certificate, which per\-kkfreeness cannot replace\.

00θ⋆\\theta^\{\\star\}freex1x\_\{1\}y1y\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}x4x\_\{4\}y4y\_\{4\}cut atθ⋆\\theta^\{\\star\}, unroll fromx2x\_\{2\},keep atoms with activationrank≤k\\leq k, match in order⇒\\Rightarrowoptimalπk\\pi^\{k\}for everykk\(plan recovery,[AppendixI](https://arxiv.org/html/2608.23910#A9)\)

### Step 8 — The output: the full circular profile

One sweep has producedCk∘C^\{\\circ\}\_\{k\}for everykk; fractional mass follows by linear interpolation \(convexity of the min\-cost\-flow value function\)\. The increments0\.5,1\.0,1\.3,3\.60\.5,\\,1\.0,\\,1\.3,\\,3\.6are non\-decreasing, so elbow\-based selection of the transported mass works exactly as in PAWL — note the pronounced elbow atk=3k=3, where the next sample would cost nearly three times more to transport\.

kk\(massss\)Ck∘C^\{\\circ\}\_\{k\}1234560123400\.51\.52\.86\.4\+0\.5\+1\.0\+1\.3\+3\.6

Every marginal was a constant\-time lookup in theQQ\-table of Step 1; every pop, skip, and insert a heap operation on at mostN\+kN\{\+\}kentries; the free\-gap representatives costO⁡\(1\)O\(1\)bookkeeping per merge and deliveredθ⋆\\theta^\{\\star\}for free\. Total:O⁡\(N​log⁡N\)O\(N\\log N\)— againstO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)for the cut\-enumeration baseline whose entire output \(the envelope table of Step 7\) this single sweep reproduces\.

## Appendix BNotation and problem formulation

Let the circle of circumferenceL\>0L\>0be

𝕊L1=ℝ/L​ℤ,\\mathbb\{S\}^\{1\}\_\{L\}=\\mathbb\{R\}/L\\mathbb\{Z\},and represent its points by coordinates in\[0,L\)\[0,L\)\. Its geodesic distance is

d𝕊1​\(x,y\)=min⁡\{\|x−y\|,L−\|x−y\|\}\.d\_\{\\mathbb\{S\}^\{1\}\}\(x,y\)=\\min\\\{\|x\-y\|,\\,L\-\|x\-y\|\\\}\.\(4\)Consider two empirical measures

μ=w​∑i=1nδxi,ν=w​∑j=1mδyj,w\>0\.\\mu=w\\sum\_\{i=1\}^\{n\}\\delta\_\{x\_\{i\}\},\\qquad\\nu=w\\sum\_\{j=1\}^\{m\}\\delta\_\{y\_\{j\}\},\\qquad w\>0\.\(5\)
###### Assumption 2\(Standing assumptions\)\.

All atoms have the same massww; the points in\{x1,…,xn,y1,…,ym\}\\\{x\_\{1\},\\dots,x\_\{n\},y\_\{1\},\\dots,y\_\{m\}\\\}are pairwise distinct; and the ground cost is the geodesic distance \([4](https://arxiv.org/html/2608.23910#A2.E4)\)\. LetN=n\+mN=n\+mandK=min⁡\(n,m\)K=\\min\(n,m\)\.

For a transported masss∈\[0,K​w\]s\\in\[0,Kw\], define

PW∘\(s\)=minπ∈ℝ\+n×m∑i=1n∑j=1md𝕊1\(xi,yj\)πi​j\\operatorname\{PW\}\_\{\\circ\}\(s\)=\\min\_\{\\pi\\in\\mathbb\{R\}\_\{\+\}^\{n\\times m\}\}\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)\\pi\_\{ij\}\(6\)subject to

∑jπi​j≤w,∑iπi​j≤w,∑i,jπi​j=s\.\\sum\_\{j\}\\pi\_\{ij\}\\leq w,\\qquad\\sum\_\{i\}\\pi\_\{ij\}\\leq w,\\qquad\\sum\_\{i,j\}\\pi\_\{ij\}=s\.\(7\)At an integer transported masss=k​ws=kw, define the rescaled transport plan

γi​j≔πi​jw\.\\gamma\_\{ij\}\\coloneqq\\frac\{\\pi\_\{ij\}\}\{w\}\.The feasible set then becomes

𝒫k=\{γ∈ℝ\+n×m\|∑j=1mγi​j≤1,∀i,∑i=1nγi​j≤1,∀j,∑i=1n∑j=1mγi​j=k\}\.\\mathcal\{P\}\_\{k\}=\\left\\\{\\gamma\\in\\mathbb\{R\}\_\{\+\}^\{n\\times m\}\\;\\middle\|\\;\\sum\_\{j=1\}^\{m\}\\gamma\_\{ij\}\\leq 1,\\ \\forall i,\\quad\\sum\_\{i=1\}^\{n\}\\gamma\_\{ij\}\\leq 1,\\ \\forall j,\\quad\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}\\gamma\_\{ij\}=k\\right\\\}\.This is the cardinality\-kkbipartite matching polytope\. Its extreme points are integral, meaning that

γi​j∈\{0,1\}\.\\gamma\_\{ij\}\\in\\\{0,1\\\}\.Since the objective is linear, an optimum is attained at an extreme point of𝒫k\\mathcal\{P\}\_\{k\}\. Therefore, there exists an optimal transport plan satisfying

πi​j∈\{0,w\}\.\\pi\_\{ij\}\\in\\\{0,w\\\}\.Moreover, the constraint

∑i,jγi​j=k\\sum\_\{i,j\}\\gamma\_\{ij\}=kimplies that exactlykkentries ofγ\\gammaare equal to one, while the row and column constraints ensure that no two selected entries share the same source or target\. Hence, an optimal solution can be represented by a cardinality\-kkmatching betweenkkdistinct source atoms andkkdistinct target atoms\. We therefore write

Ck∘=minM:\|M\|=kw∑\(xi,yj\)∈Md𝕊1\(xi,yj\),k=0,…,K,C\_\{k\}^\{\\circ\}=\\min\_\{M:\\,\|M\|=k\}w\\sum\_\{\(x\_\{i\},y\_\{j\}\)\\in M\}d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\),\\qquad k=0,\\dots,K,\(8\)where no source or target atom occurs in more than one edge ofMM\.

The*active set*of a matching is

A\(M\)=\{xi:∃j,\(xi,yj\)∈M\}∪\{yj:∃i,\(xi,yj\)∈M\}\.A\(M\)=\\\{x\_\{i\}:\\exists j,\(x\_\{i\},y\_\{j\}\)\\in M\\\}\\cup\\\{y\_\{j\}:\\exists i,\(x\_\{i\},y\_\{j\}\)\\in M\\\}\.\(9\)When only the active set matters, we writeAkA\_\{k\}for an optimal set containingkksource andkktarget atoms\.

##### Mass accounting\.

[Figure1](https://arxiv.org/html/2608.23910#S2.F1)provides an accounting interpretation of the fixed\-cardinality partial transport problem\. At cardinalitykk, exactlyk​wkwunits of mass are transported, while\(n−k\)​w\(n\-k\)wunits of source mass remain unmatched and\(m−k\)​w\(m\-k\)wunits of target capacity remain unfilled\. These latter quantities may be interpreted as destroyed and created mass, respectively, and represented by arcs to dummy reservoirs\. However, becausekkis fixed in \([8](https://arxiv.org/html/2608.23910#A2.E8)\), the total amounts of destruction and creation are prescribed\. Consequently, constant per\-unit destruction and creation penalties contribute only an additive constant, and PAWC needs to optimize only the geodesic transportation cost\.

## Appendix CBackground: the line structure and the cut envelope

### C\.1The line structure inherited from PAWL

On the line, uniformly weighted partialW1W\_\{1\}admits a particularly rigid combinatorial structure that makes it possible to compute the entire transported\-mass profile efficiently\. In particular, optimal active sets can be chosen to grow monotonically with the transported cardinality, and the transition from a cardinality\-kksolution to a cardinality\-\(k\+1\)\(k\+1\)solution activates exactly one source atom and one target atom\. Moreover, these newly activated atoms must be adjacent after removing the current active set, so each admissible update is represented by a balanced contiguous chain\. For the absolute\-value ground cost, the marginal cost of activating such a chain can be recovered from precomputed chain costs in constant time\. These structural and computational properties form the basis of PAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)and are summarized below, as they will serve as the starting point for our extension from the line to the circle\.

Throughout, all line costs are written with a single symbol\. LetPPbe a finite set of support points carrying equally many source and target atoms, all of common weightww, and letx\(1\)<⋯<x\(j\)x\_\{\(1\)\}<\\dots<x\_\{\(j\)\}andy\(1\)<⋯<y\(j\)y\_\{\(1\)\}<\\dots<y\_\{\(j\)\}be its source and target atoms in increasing order\. Such aPPis called*balanced*, and we write

cℝ​\(P\)=w​∑i=1j\|x\(i\)−y\(i\)\|c\_\{\\mathbb\{R\}\}\(P\)=w\\sum\_\{i=1\}^\{j\}\\bigl\|x\_\{\(i\)\}\-y\_\{\(i\)\}\\bigr\|\(10\)for its one\-dimensionalW1W\_\{1\}transport cost, the increasing\-order matching being optimal on the line\. We applycℝc\_\{\\mathbb\{R\}\}to whatever set of atoms is under discussion and abbreviate accordingly:cℝ​\(I\)c\_\{\\mathbb\{R\}\}\(I\)for the atoms lying in an intervalII,cℝ​\(A\)c\_\{\\mathbb\{R\}\}\(A\)for those of an active setAA,cℝ​\(𝒞\)c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)for those of a circular cell𝒞\\mathcal\{C\}once a cut outside it has been fixed, andcℝ​\(\[a,b\]\)c\_\{\\mathbb\{R\}\}\(\[a,b\]\)for those at positionsaathroughbbof the doubled sequence of[SectionG\.1](https://arxiv.org/html/2608.23910#A7.SS1)\. In every case the argument is balanced, so \([10](https://arxiv.org/html/2608.23910#A3.E10)\) applies verbatim; only the description of which atoms are meant changes\.

###### Lemma 2\(Universal line\-neighbor and locality principle\)\.

Consider two optimal active sets for uniformly weighted partialW1W\_\{1\}on the line satisfying

Ak\+1=Ak∪\{u,v\},A\_\{k\+1\}=A\_\{k\}\\cup\\\{u,v\\\},whereuuandvvbelong to opposite measures\. Thenuuandvvare consecutive in the ordered inactive setAkcA\_\{k\}^\{c\}\. Consequently, the open interval betweenuuandvvcontains only active atoms and is balanced\. Moreover, passing fromAkA\_\{k\}toAk\+1A\_\{k\+1\}changes the increasing\-order optimal matching only inside the closed interval\[u,v\]\[u,v\]; every matching edge outside this interval is preserved\.

###### Proof sketch and citation map\.

This lemma packages three ingredients from[Chapel and Tavenard \(2025, Proposition 2, Lemma 1 in Appendix A\.1, and Section 3\.3\)](https://arxiv.org/html/2608.23910#bib.bib3)\. Their Lemma 1 shows that every optimal active set on the line can be decomposed into disjoint contiguous balanced chains\. Their Proposition 2 then proves the neighbor property, while the discussion in Section 3\.3 identifies the resulting local rematching and its chain marginal\.

We recall the exchange argument because the universal quantifier in the present statement is important\. LetAkA\_\{k\}be any optimal cardinality\-kkactive set, and let

Ak\+1=Ak∪\{u,v\}A\_\{k\+1\}=A\_\{k\}\\cup\\\{u,v\\\}be any optimal nested cardinality\-\(k\+1\)\(k\+1\)extension\. Assume without loss of generality thatu<vu<v\. Suppose, toward a contradiction, thatuuandvvare not consecutive in the ordered inactive setAkcA\_\{k\}^\{c\}\. Then there exists an inactive atom in the open interval\(u,v\)\(u,v\)\. Letzzbe the first such atom encountered when moving fromuutowardvv\. By symmetry, we may assume thatzzbelongs to the same measure asvv\.

Becausezzis the first inactive atom afteruu, every support point strictly betweenuuandzzis active\. The chain decomposition ofAkA\_\{k\}therefore implies that the active atoms in\(u,z\)\(u,z\), together with the opposite\-type endpointsuuandzz, form a balanced contiguous chain\. Hence

is another feasible cardinality\-\(k\+1\)\(k\+1\)active set\.

The exchange calculation in the proof of[Chapel and Tavenard \(2025, Lemma 1, equations \(3\)–\(6\)\)](https://arxiv.org/html/2608.23910#bib.bib3)compares this competitor withAk∪\{u,v\}A\_\{k\}\\cup\\\{u,v\\\}\. In the increasing\-order matching, replacing the nearer atomzzby the strictly more distant atomvvforces one local matched endpoint to move strictly to the right\. The cost of the affected left chain therefore increases strictly\. The remaining part of the matching cannot compensate for this increase: otherwise one could replace the corresponding active atom inAkA\_\{k\}byvvand obtain a cardinality\-kksolution cheaper thanAkA\_\{k\}, contradicting its optimality\. Thus,

cℝ​\(Ak∪\{u,v\}\)\>cℝ​\(Ak∪\{u,z\}\),c\_\{\\mathbb\{R\}\}\\bigl\(A\_\{k\}\\cup\\\{u,v\\\}\\bigr\)\>c\_\{\\mathbb\{R\}\}\\bigl\(A\_\{k\}\\cup\\\{u,z\\\}\\bigr\),contradicting the assumed optimality of the extensionAk∪\{u,v\}A\_\{k\}\\cup\\\{u,v\\\}\.

The inequality is strict because all support locations are distinct\. Consequently, a non\-neighbor extension cannot even tie an optimal neighbor extension\. This is what upgrades the existential statement that*some*optimal extension uses neighboring inactive atoms to the universal statement used here:*every*optimal nested extension must do so\.

It remains to establish balance and locality\. Sinceuuandvvare consecutive inAkcA\_\{k\}^\{c\}, every atom in\(u,v\)\(u,v\)belongs toAkA\_\{k\}\. By the chain decomposition, this interior is a union of contiguous balanced chains and is therefore itself balanced\. On the line, the optimal matching between uniformly weighted active measures pairs sources and targets in increasing order\. Adding the opposite\-type endpointsuuandvvmay revoke and replace matches within\[u,v\]\[u,v\], but the balanced interior ensures that the source and target ranks agree again upon leaving the interval\. Hence all increasing\-order matches strictly to the left and strictly to the right of\[u,v\]\[u,v\]remain unchanged\. This is the locality property described in[Chapel and Tavenard \(2025, Section 3\.3, cases \(S1\)–\(S2\)\)](https://arxiv.org/html/2608.23910#bib.bib3)\. ∎

For a balanced line intervalIIand its interiorI∘I^\{\\circ\}, define

𝔪⁡\(I\)=cℝ​\(I\)−cℝ​\(I∘\),\\mathfrak\{m\}\(I\)=c\_\{\\mathbb\{R\}\}\(I\)\-c\_\{\\mathbb\{R\}\}\(I^\{\\circ\}\),\(11\)withcℝc\_\{\\mathbb\{R\}\}as in \([10](https://arxiv.org/html/2608.23910#A3.E10)\)\. By[Lemma2](https://arxiv.org/html/2608.23910#Thmlemma2), \([11](https://arxiv.org/html/2608.23910#A3.E11)\) is the exact line cost increment produced by activating the endpoints ofII\. This is the chain marginal used byPAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\.

### C\.2Circular flow, circulation, and cuts

This subsection concerns the balanced transport problem induced by a fixed active set\. Specifically, letAAcontainkksource atoms andkktarget atoms\. The restricted measures

μA=w​∑xi∈A∩supp⁡μδxi,νA=w​∑yj∈A∩supp⁡νδyj\\mu\_\{A\}=w\\sum\_\{x\_\{i\}\\in A\\cap\\operatorname\{supp\}\\mu\}\\delta\_\{x\_\{i\}\},\\qquad\\nu\_\{A\}=w\\sum\_\{y\_\{j\}\\in A\\cap\\operatorname\{supp\}\\nu\}\\delta\_\{y\_\{j\}\}have equal total massk​wkw, so their transport cost is an ordinary balanced11\-Wasserstein problem on the circle\. The partial nature of the overall problem enters through the subsequent optimization over the choice of the active setAA\.

To characterize one\-dimensional transport on the circle, we first introduce the elementary arcs between consecutive support points and the cumulative mass imbalance associated with them\. Let

z1,…,zN,N=n\+m,z\_\{1\},\\ldots,z\_\{N\},\\qquad N=n\+m,denote the cyclically ordered union of the source and target support points\. Throughout the paper, indices are understood cyclically, so thatzN\+1=z1z\_\{N\+1\}=z\_\{1\}\. The*original support gaps*are the open circular arcs

Gi≔\(zi,zi\+1\)∘,i=1,…,N,G\_\{i\}\\coloneqq\(z\_\{i\},z\_\{i\+1\}\)\_\{\\circ\},\\qquad i=1,\\ldots,N,and their lengths are denoted by

ℓi≔\|Gi\|=dcw​\(zi,zi\+1\),\\ell\_\{i\}\\coloneqq\|G\_\{i\}\|=d\_\{\\mathrm\{cw\}\}\(z\_\{i\},z\_\{i\+1\}\),wheredcwd\_\{\\mathrm\{cw\}\}is the clockwise arc length\. By construction, no source or target atom lies in the interior of a support gap\. Under our distinct\-support assumption, every gap has positive length and

∑i=1Nℓi=L\.\\sum\_\{i=1\}^\{N\}\\ell\_\{i\}=L\.These original support gaps should not be confused with the*current cells*introduced later: a current cell is an arc between consecutive inactive atoms and may contain several original support gaps as well as active atoms\.

Now fix a balanced active setAA, containing the same number of source and target atoms\. Choose an arbitrary originθ\\thetain one of the support gaps and unwrap the circle atθ\\theta, thereby identifying𝕊L1\\mathbb\{S\}\_\{L\}^\{1\}with the interval\[0,L\)\[0,L\)\. Define the cumulative imbalance

HA​\(t\)=\#⁡\{x∈A∩supp⁡μ:x∈\[0,t\)\}−\#⁡\{y∈A∩supp⁡ν:y∈\[0,t\)\}\.H\_\{A\}\(t\)=\\\#\\bigl\\\{x\\in A\\cap\\operatorname\{supp\}\\mu:\\ x\\in\[0,t\)\\bigr\\\}\-\\\#\\bigl\\\{y\\in A\\cap\\operatorname\{supp\}\\nu:\\ y\\in\[0,t\)\\bigr\\\}\.Thus,HA​\(t\)H\_\{A\}\(t\)records the net number of active source atoms minus active target atoms encountered while moving clockwise from the cutθ\\thetatott\. It increases by one when an active source atom is crossed, decreases by one when an active target atom is crossed, and is unchanged when an inactive atom is crossed\. Consequently,HAH\_\{A\}is integer\-valued and constant on the interior of every original support gapGiG\_\{i\}\. We denote this constant value by

Unlike on the line, the cumulative imbalance on the circle depends on where the circle is cut\. Equivalently, a feasible circular flow is determined only up to an arbitrary constant circulation around the cycle\. Accounting for this degree of freedom gives the standard one\-dimensional circularW1W\_\{1\}representation

W1,∘​\(A\)=w​min⁡∫0La∈ℝ⁡\|HA​\(t\)−a\|​𝑑t=w​min⁡∑i=1Na∈ℝ⁡ℓi​\|HA​\(Gi\)−a\|\.W\_\{1,\\circ\}\(A\)=w\\min\_\{a\\in\\mathbb\{R\}\}\\int\_\{0\}^\{L\}\\left\|H\_\{A\}\(t\)\-a\\right\|\\,dt=w\\min\_\{a\\in\\mathbb\{R\}\}\\sum\_\{i=1\}^\{N\}\\ell\_\{i\}\\left\|H\_\{A\}\(G\_\{i\}\)\-a\\right\|\.\(12\)The scalaraarepresents the circulation level\. The second equality follows becauseHAH\_\{A\}is constant on each support gap\. Hence, a minimizera⋆a^\{\\star\}is a weighted median of the values\{HA​\(Gi\)\}i=1N\\\{H\_\{A\}\(G\_\{i\}\)\\\}\_\{i=1\}^\{N\}, with each value weighted by the corresponding gap lengthℓi\\ell\_\{i\}\([Delon et al\., 2010](https://arxiv.org/html/2608.23910#bib.bib4);[Rabin et al\., 2011](https://arxiv.org/html/2608.23910#bib.bib7)\)\. Since all valuesHA​\(Gi\)H\_\{A\}\(G\_\{i\}\)are integers, an integer\-valued minimizing median may be chosen\.

The same representation admits a direct interpretation as a minimum\-cost flow problem on the cycle\. Orient each original support gapGiG\_\{i\}clockwise, and letfif\_\{i\}denote the signed amount of mass flowing through that gap, withfi\>0f\_\{i\}\>0corresponding to clockwise flow\. Let

bi=\{\+1,zi∈A∩supp⁡μ,−1,zi∈A∩supp⁡ν,0,zi∉A,b\_\{i\}=\\begin\{cases\}\+1,&z\_\{i\}\\in A\\cap\\operatorname\{supp\}\\mu,\\\\ \-1,&z\_\{i\}\\in A\\cap\\operatorname\{supp\}\\nu,\\\\ 0,&z\_\{i\}\\notin A,\\end\{cases\}denote the signed activity at theiith support point\. Conservation of mass imposes the discrete divergence constraints

fi−fi−1=w​bi,f\_\{i\}\-f\_\{i\-1\}=wb\_\{i\},with cyclic indexing\. These constraints determine the differences between successive edge flows, but they do not determine their common additive offset: adding the same constant circulation to everyfif\_\{i\}preserves all divergence constraints\. Consequently, every feasible circular flow can be written as

fi​\(a\)=w⁡\(HA​\(Gi\)−a\)f\_\{i\}\(a\)=w\\bigl\(H\_\{A\}\(G\_\{i\}\)\-a\\bigr\)for some scalar circulation levelaa\. Since transporting an amount\|fi​\(a\)\|\\lvert f\_\{i\}\(a\)\\rvertacross a gap of lengthℓi\\ell\_\{i\}incurs costℓi​\|fi​\(a\)\|\\ell\_\{i\}\\lvert f\_\{i\}\(a\)\\rvert, the minimum flow cost is

min⁡∑i=1Na∈ℝ⁡ℓi​\|fi​\(a\)\|=w​min⁡∑i=1Na∈ℝ⁡ℓi​\|HA​\(Gi\)−a\|,\\min\_\{a\\in\\mathbb\{R\}\}\\sum\_\{i=1\}^\{N\}\\ell\_\{i\}\\lvert f\_\{i\}\(a\)\\rvert=w\\min\_\{a\\in\\mathbb\{R\}\}\\sum\_\{i=1\}^\{N\}\\ell\_\{i\}\\left\|H\_\{A\}\(G\_\{i\}\)\-a\\right\|,which recovers \([12](https://arxiv.org/html/2608.23910#A3.E12)\)\.

This flow formulation makes the freedom in the choice of cut explicit: the circulation levelaais a free primal variable, and every value of it gives a feasible flow\. Because the minimizing circulationa⋆a^\{\\star\}may be chosen as a weighted median of the finitely many values\{HA​\(Gi\)\}i=1N\\\{H\_\{A\}\(G\_\{i\}\)\\\}\_\{i=1\}^\{N\}, it can be chosen equal toHA​\(Gr\)H\_\{A\}\(G\_\{r\}\)for at least one support gapGrG\_\{r\}\. The corresponding optimal flow then satisfies

fr=w⁡\(HA​\(Gr\)−a⋆\)=0\.f\_\{r\}=w\\bigl\(H\_\{A\}\(G\_\{r\}\)\-a^\{\\star\}\\bigr\)=0\.No mass crossesGrG\_\{r\}, so cutting the circle anywhere inside this gap does not interrupt the optimal transport flow and reduces the circular problem to an equivalent transport problem on the line\([Delon et al\., 2010](https://arxiv.org/html/2608.23910#bib.bib4);[Rabin et al\., 2011](https://arxiv.org/html/2608.23910#bib.bib7)\)\.

###### Proposition 1\(Cut representation for a fixed active set\)\.

For each original support gapGrG\_\{r\}, choose anyθr∈Gr\\theta\_\{r\}\\in G\_\{r\}, cut the circle atθr\\theta\_\{r\}, and unwrap it onto an interval of lengthLL\. LetW1,rline​\(A\)W\_\{1,r\}^\{\\mathrm\{line\}\}\(A\)denote the lineW1W\_\{1\}cost of the active setAAin this unwrapped representation\. Then, for every balanced active setAA,

W1,∘​\(A\)=minr=1,…,N⁡W1,rline​\(A\)\.W\_\{1,\\circ\}\(A\)=\\min\_\{r=1,\\ldots,N\}W\_\{1,r\}^\{\\mathrm\{line\}\}\(A\)\.\(13\)The valueW1,rline​\(A\)W\_\{1,r\}^\{\\mathrm\{line\}\}\(A\)does not depend on the precise location ofθr\\theta\_\{r\}insideGrG\_\{r\}, because moving the cut within a gap changes all unwrapped coordinates by the same translation and does not alter their linear order\.

###### Proof\.

A cut in gapGrG\_\{r\}fixes the flow through that gap to zero, which corresponds in \([12](https://arxiv.org/html/2608.23910#A3.E12)\) to choosinga=HA​\(Gr\)a=H\_\{A\}\(G\_\{r\}\)\. Conversely, an attained minimizing mediana⋆a^\{\\star\}equalsHAH\_\{A\}on at least one positive\-length gap; cutting there realizes the circular optimum as a line optimum\. ∎

###### Corollary 2\(Exact cut envelope\)\.

For each support gapGrG\_\{r\}, letCk,rlineC\_\{k,r\}^\{\\mathrm\{line\}\}denote the minimum transportation cost, with the absolute\-value ground cost on the unwrapped line, among all matchings that pair exactlykksource atoms withkktarget atoms\. Then

Ck∘=minr=1,…,N⁡Ck,rline\.C\_\{k\}^\{\\circ\}=\\min\_\{r=1,\\dots,N\}C\_\{k,r\}^\{\\mathrm\{line\}\}\.\(14\)Consequently, runningPAWLfor allNNpossible cuts yields an exactO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)reference solver for the complete circular partial\-transport profile\.

###### Proof\.

Using[Proposition1](https://arxiv.org/html/2608.23910#Thmproposition1)and exchanging two finite minima,

Ck∘=minA:\|A∩supp⁡μ\|=\|A∩supp⁡ν\|=kminrW1,rline\(A\)=minrCk,rline\.C\_\{k\}^\{\\circ\}=\\min\_\{A:\|A\\cap\\operatorname\{supp\}\\mu\|=\|A\\cap\\operatorname\{supp\}\\nu\|=k\}\\min\_\{r\}W\_\{1,r\}^\{\\mathrm\{line\}\}\(A\)=\\min\_\{r\}C\_\{k,r\}^\{\\mathrm\{line\}\}\.Each line run returns allkkinO⁡\(N​log⁡N\)O\(N\\log N\)time\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\. ∎

## Appendix DNested optimal active sets and cyclic neighbours

The purpose of this section is to establish the two structural properties that make an efficient incremental algorithm possible on the circle\. First, we show that optimal solutions can be selected consistently across transported cardinalities: starting from an optimal cardinality\-kksolution, one can construct an optimal cardinality\-\(k\+1\)\(k\+1\)solution by activating exactly one additional source atom and one additional target atom\. Thus, the associated active sets may be chosen to form a nested sequence\. Second, we exploit the one\-dimensional geometry of the circle to sharply restrict which inactive source–target pair can be activated next\. We show that the two newly activated atoms may be chosen to be consecutive in the cyclic ordering of the inactive support points\.

These results replace the quadratic search over all inactive source–target pairs by a linear\-size family of local candidates\. The nestedness property is derived first from the successive\-augmentation structure of min\-cost flow, while the cyclic\-neighbor property is obtained by cutting the circle at a suitable gap and reducing the transition to the corresponding line problem studied byPAWL\.

### D\.1Nested optimal active sets

A priori, optimal matchings at two consecutive cardinalities need not appear compatible: an optimal cardinality\-kkmatching and an independently computed optimal cardinality\-\(k\+1\)\(k\+1\)matching may involve substantially different source and target atoms\. For an incremental algorithm, however, we need a stronger statement\. Namely, we need to know that the optima can be*chosen*so that increasing the transported cardinality preserves every previously active atom and activates exactly one additional source atom and one additional target atom\. This nestedness property is the analogue of the monotone active\-set structure exploited by PAWL on the line\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\.

For a matchingMM, recall that its active set is

A⁡\(M\)≔\{xi:∃yj​such that​\(xi,yj\)∈M\}∪\{yj:∃xi​such that​\(xi,yj\)∈M\}\.A\(M\)\\coloneqq\\left\\\{x\_\{i\}:\\exists\\,y\_\{j\}\\text\{ such that \}\(x\_\{i\},y\_\{j\}\)\\in M\\right\\\}\\cup\\left\\\{y\_\{j\}:\\exists\\,x\_\{i\}\\text\{ such that \}\(x\_\{i\},y\_\{j\}\)\\in M\\right\\\}\.Thus, ifMMhas cardinalitykk, thenA⁡\(M\)A\(M\)contains exactlykksource atoms andkktarget atoms\.

###### Theorem 6\(Nested optimal extension\)\.

LetMkM\_\{k\}be any optimal cardinality\-kkmatching, withk<Kk<K\. Then there exists an optimal cardinality\-\(k\+1\)\(k\+1\)matchingMk\+1M\_\{k\+1\}such that

A⁡\(Mk\+1\)=A⁡\(Mk\)∪\{x,y\},A\(M\_\{k\+1\}\)=A\(M\_\{k\}\)\\cup\\\{x,y\\\},\(15\)wherex∈A​\(Mk\)cx\\in A\(M\_\{k\}\)^\{c\}is a source atom andy∈A​\(Mk\)cy\\in A\(M\_\{k\}\)^\{c\}is a target atom\.

###### Proof\.

We represent the cardinality\-constrained matching problem \([8](https://arxiv.org/html/2608.23910#A2.E8)\) as a unit\-capacity minimum\-cost flow problem\. Introduce a super\-source nodess, a super\-sink nodett, one node for each source atomxix\_\{i\}, and one node for each target atomyjy\_\{j\}\. The network contains the arcs

s⟶xi,xi⟶yj,yj⟶t,s\\longrightarrow x\_\{i\},\\qquad x\_\{i\}\\longrightarrow y\_\{j\},\\qquad y\_\{j\}\\longrightarrow t,all with unit capacity\. The arcs adjacent tossandtthave zero cost, while the source\-to\-target arcxi→yjx\_\{i\}\\to y\_\{j\}has cost

ci​j=w​d𝕊1​\(xi,yj\)\.c\_\{ij\}=w\\,d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)\.Because every arc has integral capacity, an integral flow of valuekkselects exactlykksource\-to\-target arcs, with at most one selected arc incident to each source or target atom\. It therefore corresponds exactly to a cardinality\-kkmatching\. Conversely, every cardinality\-kkmatching defines an integralss\-ttflow of valuekk\. Hence the minimum\-cost flow problem of valuekkis equivalent to \([8](https://arxiv.org/html/2608.23910#A2.E8)\), and the given optimal matchingMkM\_\{k\}corresponds to an optimal integral flowfkf\_\{k\}of valuekk\.

Consider the residual network offkf\_\{k\}\. For every unused source\-to\-target arcxi→yjx\_\{i\}\\to y\_\{j\}, the residual network contains a forward arc of costci​jc\_\{ij\}\. For every matched pair\(xi,yj\)∈Mk\(x\_\{i\},y\_\{j\}\)\\in M\_\{k\}, it contains the reverse residual arc

yj⟶xiy\_\{j\}\\longrightarrow x\_\{i\}of cost−ci​j\-c\_\{ij\}\. The latter arc represents the possibility of removing the currently selected matching edge during an augmentation\.

Sincefkf\_\{k\}is optimal, its residual network contains no negative\-cost directed cycle\. Moreover, becausek<Kk<K, there exist an unmatched source atomxix\_\{i\}and an unmatched target atomyjy\_\{j\}; the paths→xi→yj→ts\\to x\_\{i\}\\to y\_\{j\}\\to tis then residual, so anss–ttresidual path exists and a minimum\-cost one is well defined\. Equivalently, one may introduce feasible node potentials and compute the path using nonnegative reduced costs\. By the successive shortest augmenting\-path theorem, augmenting one unit of flow along such a path produces an optimal flowfk\+1f\_\{k\+1\}of valuek\+1k\+1\([Ahuja et al\., 1993](https://arxiv.org/html/2608.23910#bib.bib1)\)\. Importantly, this conclusion requires only thatfkf\_\{k\}be optimal, and not that it have been obtained through any particular sequence of previous augmentations\. We may choose the shortest augmenting path to be simple, so it does not revisit the super\-source or super\-sink\.

The first atom visited afterssmust be an unmatched source atom\. Indeed, the arcs→xis\\to x\_\{i\}has forward residual capacity only whenxix\_\{i\}is not already matched\. Similarly, the final atom visited beforettmust be an unmatched target atom\. Denote these two endpoints byxxandyy, respectively\.

Between these endpoints, the augmenting path alternates between unused forward matching edges and reversed currently matched edges\. Its source–target portion therefore has the form

x⟶y1⟶x1⟶y2⟶x2⟶⋯⟶y,x\\longrightarrow y\_\{1\}\\longrightarrow x\_\{1\}\\longrightarrow y\_\{2\}\\longrightarrow x\_\{2\}\\longrightarrow\\cdots\\longrightarrow y,where each forward edgexr→yr\+1x\_\{r\}\\to y\_\{r\+1\}is inserted into the matching and each reverse edgeyr→xry\_\{r\}\\to x\_\{r\}removes an edge ofMkM\_\{k\}\. Augmenting along the path is thus equivalent to toggling the matching status of all edges on this alternating path\.

Every internal source or target atom on the path loses one matched edge but simultaneously gains another\. Consequently, it remains matched after the augmentation\. Atoms that are not on the path are unaffected\. Only the two endpointsxxandyygain a matched edge without losing one, because they were unmatched before the augmentation\. Therefore, the resulting optimal matchingMk\+1M\_\{k\+1\}satisfies

A⁡\(Mk\+1\)=A⁡\(Mk\)∪\{x,y\},A\(M\_\{k\+1\}\)=A\(M\_\{k\}\)\\cup\\\{x,y\\\},which proves \([15](https://arxiv.org/html/2608.23910#A4.E15)\)\. ∎

###### Corollary 3\(Nested optimal sequence\)\.

There exist optimal matchings

M0,M1,…,MK,K=min⁡\{n,m\},M\_\{0\},M\_\{1\},\\ldots,M\_\{K\},\\qquad K=\\min\\\{n,m\\\},such that

A⁡\(Mk\)⊂A⁡\(Mk\+1\)for every​k<K,A\(M\_\{k\}\)\\subset A\(M\_\{k\+1\}\)\\qquad\\text\{for every \}k<K,whereA⁡\(Mk\+1\)∖A⁡\(Mk\)A\(M\_\{k\+1\}\)\\setminus A\(M\_\{k\}\)consists of exactly one source atom and one target atom\.

###### Proof\.

The empty matchingM0M\_\{0\}is the unique, hence optimal, cardinality\-00matching\. Applying[Theorem6](https://arxiv.org/html/2608.23910#Thmtheorem6)successively fork=0,…,K−1k=0,\\ldots,K\-1constructs the desired sequence\. ∎

\(a\) Optimal matchingMkM\_\{k\}

y2y\_\{2\}x2x\_\{2\}y1y\_\{1\}x3x\_\{3\}x1x\_\{1\}y5y\_\{5\}x5x\_\{5\}y4y\_\{4\}x4x\_\{4\}y3y\_\{3\}\(x2,y1\)\(x\_\{2\},y\_\{1\}\)\(x3,y2\)\(x\_\{3\},y\_\{2\}\)solid: atoms ofA⁡\(Mk\)A\(M\_\{k\}\); hollow: inactive atoms

\(b\) Optimal matchingMk\+1M\_\{k\+1\}

xxyyy2y\_\{2\}x2x\_\{2\}y1y\_\{1\}x1x\_\{1\}y3y\_\{3\}x3x\_\{3\}y5y\_\{5\}x5x\_\{5\}y4y\_\{4\}x4x\_\{4\}A⁡\(Mk\+1\)=A⁡\(Mk\)∪\{x,y\}A\(M\_\{k\+1\}\)=A\(M\_\{k\}\)\\cup\\\{x,y\\\}A⁡\(Mk\)⊂A⁡\(Mk\+1\)A\(M\_\{k\}\)\\subset A\(M\_\{k\+1\}\)Mk⊄Mk\+1M\_\{k\}\\not\\subset M\_\{k\+1\}

Figure 9:Nested optimal active sets \(Theorem[6](https://arxiv.org/html/2608.23910#Thmtheorem6)\)\.\(a\)An optimal cardinality\-kkmatchingMkM\_\{k\}on the circle, with matched pairs\(x2,y1\)\(x\_\{2\},y\_\{1\}\)and\(x3,y2\)\(x\_\{3\},y\_\{2\}\)transported along geodesic arcs; solid atoms form the active setA⁡\(Mk\)A\(M\_\{k\}\)and hollow atoms are inactive\.\(b\)An optimal cardinality\-\(k\+1\)\(k\{\+\}1\)matching obtained by augmenting along a minimum\-cost alternating path: exactly one source atomx=x1x=x\_\{1\}and one target atomy=y3y=y\_\{3\}are activated \(circled\), and they are cyclic neighbors among the inactive atoms since every atom between them is already active\. The augmentation revokes the edges\(x2,y1\)\(x\_\{2\},y\_\{1\}\)and\(x3,y2\)\(x\_\{3\},y\_\{2\}\)ofMkM\_\{k\}\(dashed\) and rematches the previously active atoms as\(x1,y1\)\(x\_\{1\},y\_\{1\}\),\(x2,y2\)\(x\_\{2\},y\_\{2\}\),\(x3,y3\)\(x\_\{3\},y\_\{3\}\), so thatA⁡\(Mk\+1\)=A⁡\(Mk\)∪\{x,y\}A\(M\_\{k\+1\}\)=A\(M\_\{k\}\)\\cup\\\{x,y\\\}whileMk⊄Mk\+1M\_\{k\}\\not\\subset M\_\{k\+1\}\(Remark[2](https://arxiv.org/html/2608.23910#Thmremark2)\)\.
### D\.2A pairwise common\-cut lemma

The next lemma is the bridge between nested circular optima and the line neighbor theorem\.

###### Lemma 3\(Common optimal cut\)\.

LetAAbe balanced and let

A′=A∪\{x,y\},A^\{\\prime\}=A\\cup\\\{x,y\\\},wherexxis a source andyyis a target\. There exists a support gapGGthat carries zero flow in an optimal circularW1W\_\{1\}solution for bothAAandA′A^\{\\prime\}\. Equivalently, cutting inGGrealizes both circular costs as line costs\.

###### Proof\.

Choose an orientation fromxxtoyyand letIIbe the corresponding circular arc\. Up to adding a constant to the cumulative imbalance ofA′A^\{\\prime\}, which is absorbed by the minimization in \([12](https://arxiv.org/html/2608.23910#A3.E12)\), we may write

HA′=HA\+𝟏I\.H\_\{A^\{\\prime\}\}=H\_\{A\}\+\\mathbf\{1\}\_\{I\}\.\(16\)Letaabe an attained weighted median ofHAH\_\{A\}, so

\|\{HA<a\}\|≤L/2,\|\{HA\>a\}\|≤L/2,\|\\\{H\_\{A\}<a\\\}\|\\leq L/2,\\qquad\|\\\{H\_\{A\}\>a\\\}\|\\leq L/2,\(17\)where\|⋅\|\|\\cdot\|denotes circular arc length\. SetE=\{HA=a\}E=\\\{H\_\{A\}=a\\\}\.

Ifaais also a median ofHA′H\_\{A^\{\\prime\}\}and\|E∖I\|\>0\|E\\setminus I\|\>0, choose a gap inE∖IE\\setminus I\. On that gap, both cumulative functions equalaa\.

Otherwise, we show thata\+1a\+1is a median ofHA′H\_\{A^\{\\prime\}\}and that\|E∩I\|\>0\|E\\cap I\|\>0\. Ifaais not a median ofHA′H\_\{A^\{\\prime\}\}, then becauseHA′≥HAH\_\{A^\{\\prime\}\}\\geq H\_\{A\}, only the upper median condition can fail\. Hence\|\{HA′\>a\}\|\>L/2\|\\\{H\_\{A^\{\\prime\}\}\>a\\\}\|\>L/2, and the excess over\{HA\>a\}\\\{H\_\{A\}\>a\\\}must come fromE∩IE\\cap I, which therefore has positive length\. SinceHA′H\_\{A^\{\\prime\}\}is integer\-valued,

\{HA′<a\+1\}=\{HA′≤a\}\\\{H\_\{A^\{\\prime\}\}<a\+1\\\}=\\\{H\_\{A^\{\\prime\}\}\\leq a\\\}has length belowL/2L/2, while

\{HA′\>a\+1\}⊆\{HA\>a\}\\\{H\_\{A^\{\\prime\}\}\>a\+1\\\}\\subseteq\\\{H\_\{A\}\>a\\\}has length at mostL/2L/2\. Thusa\+1a\+1is a median\.

The remaining case is thataais a median ofHA′H\_\{A^\{\\prime\}\}but\|E∖I\|=0\|E\\setminus I\|=0\. Then\|E∩I\|\>0\|E\\cap I\|\>0\. Moreover,

\{HA′<a\+1\}⊆\{HA<a\}∪\(E∖I\),\{HA′\>a\+1\}⊆\{HA\>a\},\\\{H\_\{A^\{\\prime\}\}<a\+1\\\}\\subseteq\\\{H\_\{A\}<a\\\}\\cup\(E\\setminus I\),\\qquad\\\{H\_\{A^\{\\prime\}\}\>a\+1\\\}\\subseteq\\\{H\_\{A\}\>a\\\},so \([17](https://arxiv.org/html/2608.23910#A4.E17)\) again shows thata\+1a\+1is a median ofHA′H\_\{A^\{\\prime\}\}\.

Choose a positive\-length gap inE∩IE\\cap I\. On it,HA=aH\_\{A\}=aandHA′=a\+1H\_\{A^\{\\prime\}\}=a\+1\. Centering each cumulative imbalance at its respective median gives zero flow for both active sets on the chosen gap\.[Figure10](https://arxiv.org/html/2608.23910#A4.F10)shows this second case: the two cumulative imbalances sit at different medians, and the gap chosen fromE∩IE\\cap Iis flow\-free for both\. ∎

\(a\) Common zero\-flow gapGGon𝕊L1\\mathbb\{S\}^\{1\}\_\{L\}

IIGGy2y\_\{2\}x2x\_\{2\}y1y\_\{1\}x3x\_\{3\}xxyyno optimal flow ofAAnorA′A^\{\\prime\}crossesGG:cutting inGGunrolls both problems to the line

\(b\) Cumulative imbalances and medians

IIIIGGaaa\+1a\{\+\}1yyx3x\_\{3\}y2y\_\{2\}x2x\_\{2\}y1y\_\{1\}xxHAH\_\{A\}HA′H\_\{A^\{\\prime\}\}

Common cut\.By \([16](https://arxiv.org/html/2608.23910#A4.E16)\), activating the pair\{x,y\}\\\{x,y\\\}raises the cumulative imbalance by one exactly onII\. Hereaais a weighted median ofHAH\_\{A\}but not ofHA′H\_\{A^\{\\prime\}\}, soa\+1a\{\+\}1is a median ofHA′H\_\{A^\{\\prime\}\}andE∩I=\{HA=a\}∩IE\\cap I=\\\{H\_\{A\}=a\\\}\\cap Ihas positive length, cf\. \([17](https://arxiv.org/html/2608.23910#A4.E17)\)\. On the gapG⊂E∩IG\\subset E\\cap I,HA=aH\_\{A\}=aandHA′=a\+1H\_\{A^\{\\prime\}\}=a\{\+\}1: both functions sit at their respective medians, so after centering, both optimal circular flows vanish onGG\.

Figure 10:Common optimal cut \(Lemma[3](https://arxiv.org/html/2608.23910#Thmlemma3)\)\.\(a\)A balanced active setA=\{x2,y1,x3,y2\}A=\\\{x\_\{2\},y\_\{1\},x\_\{3\},y\_\{2\}\\\}and its extensionA′=A∪\{x,y\}A^\{\\prime\}=A\\cup\\\{x,y\\\}on the circle\. The arcII, oriented fromxxtoyy, supports the one\-interval updateHA′=HA\+𝟏IH\_\{A^\{\\prime\}\}=H\_\{A\}\+\\mathbf\{1\}\_\{I\}\. The support gapGGcarries zero flow in an optimal circularW1W\_\{1\}solution for bothAA\(solid arcs\) andA′A^\{\\prime\}\(dashed arcs\), so cutting inGGrealizes both circular costs as line costs\.\(b\)The cumulative imbalances, unrolled at a point of the large support gap\.HAH\_\{A\}is flat at its medianaaonE=\{HA=a\}E=\\\{H\_\{A\}=a\\\}, whileHA′=HA\+𝟏IH\_\{A^\{\\prime\}\}=H\_\{A\}\+\\mathbf\{1\}\_\{I\}is flat at its mediana\+1a\{\+\}1onE∩IE\\cap I; the gapG⊂E∩IG\\subset E\\cap Iis at median level for both, hence flow\-free for both\.
### D\.3Cyclic neighbor addition

Nestedness alone does not yet yield an efficient update rule\. Although[Theorem6](https://arxiv.org/html/2608.23910#Thmtheorem6)guarantees that an optimal cardinality\-\(k\+1\)\(k\+1\)active set can be obtained from an optimal cardinality\-kkactive set by adding one source atom and one target atom, a direct search would still have to examine all opposite\-type pairs inAkcA\_\{k\}^\{c\}, resulting in a quadratic number of candidates\. The circular order provides a much stronger restriction: the two new atoms may be chosen adjacent after the currently active atoms are removed\. Thus, at iterationkk, it is sufficient to consider only opposite\-type pairs that are consecutive in the cyclic ordering ofAkcA\_\{k\}^\{c\}\. This reduces the candidate family to linear size and, more importantly, identifies each candidate with a single circular cell whose interior contains only active atoms\. The result is the circular counterpart of the locality property underlyingPAWLon the line\.

###### Theorem 7\(Cyclic\-neighbor property of optimal extensions\)\.

LetMkM\_\{k\}be any circularly optimal cardinality\-kkmatching, withk<Kk<K, and writeAk≔A⁡\(Mk\)A\_\{k\}\\coloneqq A\(M\_\{k\}\)\. LetMk\+1M\_\{k\+1\}be any circularly optimal cardinality\-\(k\+1\)\(k\+1\)matching satisfying

A⁡\(Mk\+1\)=Ak∪\{x,y\},A\(M\_\{k\+1\}\)=A\_\{k\}\\cup\\\{x,y\\\},\(18\)wherex∈Akcx\\in A\_\{k\}^\{c\}is a source atom andy∈Akcy\\in A\_\{k\}^\{c\}is a target atom\. Thenxxandyyare consecutive in the cyclic ordering of the inactive setAkcA\_\{k\}^\{c\}\.

In particular, by[Theorem6](https://arxiv.org/html/2608.23910#Thmtheorem6), every circularly optimal cardinality\-kkmatching admits a circularly optimal cardinality\-\(k\+1\)\(k\+1\)extension whose two newly active atoms are cyclic neighbors\.

###### Proof\.

LetMkM\_\{k\}andMk\+1M\_\{k\+1\}be as in the statement, and set

Ak\+1≔A⁡\(Mk\+1\)=Ak∪\{x,y\}\.A\_\{k\+1\}\\coloneqq A\(M\_\{k\+1\}\)=A\_\{k\}\\cup\\\{x,y\\\}\.It remains to show thatxxandyyare cyclically adjacent among the atoms that are inactive at stagekk\.

By[Lemma3](https://arxiv.org/html/2608.23910#Thmlemma3), there exists an original support gapGrG\_\{r\}such that cutting the circle at any pointθr∈Gr\\theta\_\{r\}\\in G\_\{r\}and unwrapping it onto an interval of lengthLLrealizes the circular transport costs of both active sets as line transport costs:

W1,rline​\(Ak\)=W1,∘​\(Ak\),W1,rline​\(Ak\+1\)=W1,∘​\(Ak\+1\)\.W^\{\\mathrm\{line\}\}\_\{1,r\}\(A\_\{k\}\)=W\_\{1,\\circ\}\(A\_\{k\}\),\\qquad W^\{\\mathrm\{line\}\}\_\{1,r\}\(A\_\{k\+1\}\)=W\_\{1,\\circ\}\(A\_\{k\+1\}\)\.SinceMkM\_\{k\}andMk\+1M\_\{k\+1\}are circularly optimal,

W1,∘​\(Ak\)=Ck∘,W1,∘​\(Ak\+1\)=Ck\+1∘,W\_\{1,\\circ\}\(A\_\{k\}\)=C\_\{k\}^\{\\circ\},\\qquad W\_\{1,\\circ\}\(A\_\{k\+1\}\)=C\_\{k\+1\}^\{\\circ\},and therefore

W1,rline​\(Ak\)=Ck∘,W1,rline​\(Ak\+1\)=Ck\+1∘\.W^\{\\mathrm\{line\}\}\_\{1,r\}\(A\_\{k\}\)=C\_\{k\}^\{\\circ\},\\qquad W^\{\\mathrm\{line\}\}\_\{1,r\}\(A\_\{k\+1\}\)=C\_\{k\+1\}^\{\\circ\}\.
We next verify thatAkA\_\{k\}andAk\+1A\_\{k\+1\}are optimal for the corresponding cardinality\-constrained partial\-transport problems on the unwrapped line\. For clarity, let

cost∘⁡\(M\)=w​∑\(xi,yj\)∈Md𝕊1​\(xi,yj\)\\operatorname\{cost\}^\{\\circ\}\(M\)=w\\sum\_\{\(x\_\{i\},y\_\{j\}\)\\in M\}d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)and letcostrline⁡\(M\)\\operatorname\{cost\}^\{\\mathrm\{line\}\}\_\{r\}\(M\)denote the analogous matching cost computed using the distances in the representation obtained by cutting atGrG\_\{r\}\.

Consider any cardinality\-kkmatchingM′M^\{\\prime\}\. For each matched pair, the circular geodesic distance is no larger than its distance in the fixed unwrapped representation\. Hence

costrline⁡\(M′\)≥cost∘⁡\(M′\)\.\\operatorname\{cost\}^\{\\mathrm\{line\}\}\_\{r\}\(M^\{\\prime\}\)\\geq\\operatorname\{cost\}^\{\\circ\}\(M^\{\\prime\}\)\.Circular optimality ofMkM\_\{k\}, together with the fact that the common cut realizes its circular cost, gives

costrline⁡\(M′\)≥cost∘⁡\(M′\)≥Ck∘=W1,rline​\(Ak\)\.\\operatorname\{cost\}^\{\\mathrm\{line\}\}\_\{r\}\(M^\{\\prime\}\)\\geq\\operatorname\{cost\}^\{\\circ\}\(M^\{\\prime\}\)\\geq C\_\{k\}^\{\\circ\}=W^\{\\mathrm\{line\}\}\_\{1,r\}\(A\_\{k\}\)\.Thus no cardinality\-kkline matching is cheaper than the optimal line matching supported onAkA\_\{k\}\. ThereforeAkA\_\{k\}is optimal for the cardinality\-kkpartial\-transport problem induced by the cut\. The same argument, withk\+1k\+1in place ofkk, proves thatAk\+1A\_\{k\+1\}is optimal for the corresponding cardinality\-\(k\+1\)\(k\+1\)line problem\.

We may now apply the universal line\-neighbor property of[Lemma2](https://arxiv.org/html/2608.23910#Thmlemma2)to the nested pair of line\-optimal active sets

Ak⊂Ak\+1\.A\_\{k\}\\subset A\_\{k\+1\}\.It follows that the two newly activated atomsxxandyyare consecutive in the linear ordering of the atoms inAkcA\_\{k\}^\{c\}induced by the cut\.

Finally, the linear inactive order is obtained by breaking the cyclic inactive order at a single location\. This operation can remove the one cyclic adjacency crossing the cut, but it cannot create any new adjacency\. Hence every pair that is consecutive in the linear inactive order is also consecutive in the original cyclic inactive order\. Thereforexxandyyare cyclic neighbors inAkcA\_\{k\}^\{c\}\. ∎

## Appendix ECircular cells and local marginals

The previous section established the combinatorial structure of an optimal cardinality\-by\-cardinality construction\. In particular, optimal active sets can be chosen to form a nested sequence, and the transition fromAkA\_\{k\}toAk\+1A\_\{k\+1\}may be realized by activating a source atom and a target atom that are consecutive in the cyclic ordering of the inactive setAkcA\_\{k\}^\{c\}\. This reduces the admissible updates from all opposite\-type inactive pairs to a linear\-size family of cyclic\-neighbor candidates\.

This structural reduction, however, is not yet sufficient for an efficient algorithm\. For each candidate pair, one must still determine the increase in the optimal transportation cost caused by activating its two endpoints\. Recomputing the circular optimal transport problem from scratch for every candidate would destroy the desired near\-linear complexity\. The key remaining question is therefore whether this cost increment can be expressed using only the portion of the circle lying between the two candidate endpoints\.

In this section, we show that the answer is affirmative\. Consecutive inactive points partition the circle into*current cells*, whose interiors contain only active atoms\. A cyclic\-neighbor pair of opposite type defines a candidate cell, and activating its endpoints modifies the optimal matching only within that cell after a suitable unwrapping onto the line\. This leads to an exact local marginal formula: the increase in circular transport cost is the difference between the line transport cost of the full balanced cell and that of its active interior\. We then relate these cell costs to the chain decomposition used byPAWL, which will later permit constant\-time marginal evaluation after preprocessing\.

LetUk=AkcU\_\{k\}=A\_\{k\}^\{c\}be the current inactive set, written in cyclic order as

u1,u2,…,ur\.u\_\{1\},u\_\{2\},\\dots,u\_\{r\}\.Each directed pair of consecutive inactive points defines a*cell*

𝒞i=\[ui,ui\+1\]↻,ur\+1=u1,\\mathcal\{C\}\_\{i\}=\[u\_\{i\},u\_\{i\+1\}\]\_\{\\circlearrowright\},\\qquad u\_\{r\+1\}=u\_\{1\},\(19\)where the arc is traversed clockwise and includes both endpoints\. The open cell interior contains only active points\.

###### Definition 2\(Candidate cell\)\.

A current cell is a*candidate*if its two inactive endpoints come from opposite measures\.

###### Lemma 4\(Balanced cell interiors\)\.

At every iteration of the algorithm, the active atoms in the interior of each current cell contain the same number of source and target atoms\.

###### Proof\.

Initially all cell interiors are empty\. Suppose the property holds and a candidate cell\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}is selected\. Letppbe the previous inactive point beforeuuandqqthe next inactive point aftervv\. Removingu,vu,vmerges

\[p,u\]↻,\[u,v\]↻,\[v,q\]↻\[p,u\]\_\{\\circlearrowright\},\\qquad\[u,v\]\_\{\\circlearrowright\},\\qquad\[v,q\]\_\{\\circlearrowright\}into\[p,q\]↻\[p,q\]\_\{\\circlearrowright\}\. The old interiors are balanced by induction, and the newly activated endpointsu,vu,vcontribute one source and one target\. Therefore the new interior is balanced\. Unaffected cells are unchanged\. ∎

For a current cell

𝒞=\[u,v\]↻,\\mathcal\{C\}=\[u,v\]\_\{\\circlearrowright\},the endpointsuuandvvare consecutive inactive atoms in the clockwise order\. Hence, by definition of a cell, there is no inactive atom in the open arc𝒞∘=\(u,v\)↻\\mathcal\{C\}^\{\\circ\}=\(u,v\)\_\{\\circlearrowright\}; every support point in its interior already belongs to the current active setAkA\_\{k\}\. If𝒞\\mathcal\{C\}is a candidate cell, thenuuandvvcome from opposite distributions\. Moreover,[Lemma4](https://arxiv.org/html/2608.23910#Thmlemma4)implies that the active atoms in𝒞∘\\mathcal\{C\}^\{\\circ\}contain the same number of sources and targets\. It follows that both the interior𝒞∘\\mathcal\{C\}^\{\\circ\}and the closed cell

𝒞=𝒞∘∪\{u,v\}\\mathcal\{C\}=\\mathcal\{C\}^\{\\circ\}\\cup\\\{u,v\\\}are balanced: the former represents the local transport configuration before activatinguuandvv, while the latter represents the local configuration after their activation\.

To compare these two configurations, choose a cut outside𝒞\\mathcal\{C\}and unwrap the circle onto an interval of lengthLL\. Because the cut does not intersect𝒞\\mathcal\{C\}, the clockwise arc𝒞\\mathcal\{C\}becomes a contiguous interval on the real line\. Let

μ𝒞∘andν𝒞∘\\mu\_\{\\mathcal\{C\}^\{\\circ\}\}\\quad\\text\{and\}\\quad\\nu\_\{\\mathcal\{C\}^\{\\circ\}\}denote the source and target measures supported on the active interior atoms, and let

μ𝒞andν𝒞\\mu\_\{\\mathcal\{C\}\}\\quad\\text\{and\}\\quad\\nu\_\{\\mathcal\{C\}\}denote the corresponding measures after including the two endpoints\. Both are balanced, so \([10](https://arxiv.org/html/2608.23910#A3.E10)\) applies to each:cℝ​\(𝒞∘\)c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\)is the cost of matchingμ𝒞∘\\mu\_\{\\mathcal\{C\}^\{\\circ\}\}againstν𝒞∘\\nu\_\{\\mathcal\{C\}^\{\\circ\}\}in increasing unwrapped order, andcℝ​\(𝒞\)c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)the same forμ𝒞\\mu\_\{\\mathcal\{C\}\}againstν𝒞\\nu\_\{\\mathcal\{C\}\}\.

###### Definition 3\(Circular cell marginal\)\.

The*local marginal cost*associated with a candidate cell𝒞\\mathcal\{C\}is

𝔪⁡\(𝒞\)=cℝ​\(𝒞\)−cℝ​\(𝒞∘\)\.\\mathfrak\{m\}\(\\mathcal\{C\}\)=c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)\-c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\)\.\(20\)Thus,𝔪⁡\(𝒞\)\\mathfrak\{m\}\(\\mathcal\{C\}\)measures the increase in the local transportation cost caused by activating the two inactive endpoints of𝒞\\mathcal\{C\}and recomputing the optimal matching inside the cell\.

The distance entering both terms in \([20](https://arxiv.org/html/2608.23910#A5.E20)\) is the ordinary absolute distance in the unwrapped interval, equivalently the clockwise arc length measured inside𝒞\\mathcal\{C\}\. It is not the circular geodesic distanced𝕊1d\_\{\\mathbb\{S\}^\{1\}\}\. Indeed, once a cut is fixed outside the cell,𝒞\\mathcal\{C\}is treated as a contiguous line interval, and the local matching is constrained to remain within that interval\. Using the geodesic distance at this stage could allow a pair of atoms in𝒞\\mathcal\{C\}to be connected through the complementary arc, thereby crossing the cut and destroying the desired locality\.

The significance of𝔪⁡\(𝒞\)\\mathfrak\{m\}\(\\mathcal\{C\}\)is that it is also the increment in the global line transport cost\. Before activation, the atoms in𝒞∘\\mathcal\{C\}^\{\\circ\}are matched optimally among themselves\. After activatinguuandvv, those local matching edges may be revoked and replaced by the optimal sorted matching on the larger balanced interval𝒞\\mathcal\{C\}\. By the one\-dimensional locality principle, all matching edges outside𝒞\\mathcal\{C\}remain unchanged\. Consequently, whenever the chosen cut lies outside𝒞\\mathcal\{C\},

cℝ​\(Ak∪\{u,v\}\)−cℝ​\(Ak\)=cℝ​\(𝒞\)−cℝ​\(𝒞∘\)=𝔪⁡\(𝒞\)\.c\_\{\\mathbb\{R\}\}\(A\_\{k\}\\cup\\\{u,v\\\}\)\-c\_\{\\mathbb\{R\}\}\(A\_\{k\}\)=c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\)\-c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}^\{\\circ\}\)=\\mathfrak\{m\}\(\\mathcal\{C\}\)\.Hence, the effect of activating a candidate pair can be evaluated entirely from the atoms contained in its cell\.[Figure2](https://arxiv.org/html/2608.23910#S3.F2)shows the rematching this describes: the sorted matching of the active interior is revoked and replaced by the sorted matching of the closed cell, while every edge outside the cell is untouched\.

## Appendix FFree gaps, the exact greedy theorem and the simultaneous cut

Let the*original gaps*be theNNarcs between consecutive points in the fully sorted union support\. A gap is called*used*once it lies inside a selected candidate cell, and*free*otherwise\. Since the endpoints of current cells are inactive atoms, hence support points, every original gap lies inside exactly one current cell, and which cell that is changes as cells merge\.

###### Lemma 5\(Free\-gap invariant\)\.

Before termination, every current cell contains at least one free original gap\.

###### Proof\.

The labels*free*and*used*attach to theNNoriginal gaps, which are fixed once and for all, and not to the cells, which are not: a gap acquires the label*used*when it first lies inside a selected cell and never loses it\. Merging changes which cell a gap lies in; it never changes the gap’s label\. This is the point on which the induction turns, since a gap stays free while the cell containing it grows\.

Initially, each current cell is exactly one original gap, hence free\. Suppose a candidate\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}is selected\. This marks used exactly the gaps lying inside\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}, and removesuuandvvfrom the inactive list, so the three cells\[p,u\]↻\[p,u\]\_\{\\circlearrowright\},\[u,v\]↻\[u,v\]\_\{\\circlearrowright\},\[v,q\]↻\[v,q\]\_\{\\circlearrowright\}merge into the single cell\[p,q\]↻\[p,q\]\_\{\\circlearrowright\}\. If the algorithm does not terminate, the arcs\[p,u\]↻\[p,u\]\_\{\\circlearrowright\}and\[v,q\]↻\[v,q\]\_\{\\circlearrowright\}are contained in\[p,q\]↻\[p,q\]\_\{\\circlearrowright\}, and each contained a free gap by induction\. Those gaps lie outside\[u,v\]↻\[u,v\]\_\{\\circlearrowright\}, so the selection did not mark them, and they are still free afterwards — the merged cell inherits two independent free gaps, of which the algorithm need only store one \([Figure3](https://arxiv.org/html/2608.23910#S3.F3)\)\. Every unaffected cell retains its free gap\. ∎

###### Lemma 6\(Cut compatibility\)\.

Let𝒞1,…,𝒞k\\mathcal\{C\}\_\{1\},\\dots,\\mathcal\{C\}\_\{k\}be a sequence of selected cells, and letθ\\thetabe an original gap contained in none of them\. After cutting atθ\\theta, the line cost of the active setAkA\_\{k\}generated by these selections is

W1,θline​\(Ak\)=∑r=1k𝔪⁡\(𝒞r\)\.W\_\{1,\\theta\}^\{\\mathrm\{line\}\}\(A\_\{k\}\)=\\sum\_\{r=1\}^\{k\}\\mathfrak\{m\}\(\\mathcal\{C\}\_\{r\}\)\.\(21\)If a current candidate cell𝒞\\mathcal\{C\}also avoidsθ\\theta, then activating its endpoints gives a line matching of cost

W1,θline​\(Ak\)\+𝔪⁡\(𝒞\)\.W\_\{1,\\theta\}^\{\\mathrm\{line\}\}\(A\_\{k\}\)\+\\mathfrak\{m\}\(\\mathcal\{C\}\)\.\(22\)

###### Proof\.

No selected cell crosses the cut, so every selected circular arc becomes an ordinary line interval\. The claim follows inductively from[Lemma2](https://arxiv.org/html/2608.23910#Thmlemma2): each activation changes the sorted line matching only inside its interval and adds exactly the local marginal\. The same argument applies to the additional candidate\. ∎

###### Theorem 8\(Exact greedy choice\)\.

Assume that the current active setAkA\_\{k\}is circularly optimal and was generated by successive cell selections\. Then

Ck\+1∘−Ck∘=min𝒞∈ℭk⁡𝔪⁡\(𝒞\),C\_\{k\+1\}^\{\\circ\}\-C\_\{k\}^\{\\circ\}=\\min\_\{\\mathcal\{C\}\\in\\mathfrak\{C\}\_\{k\}\}\\mathfrak\{m\}\(\\mathcal\{C\}\),\(23\)whereℭk\\mathfrak\{C\}\_\{k\}is the set of current candidate cells whose endpoints have opposite types\. Moreover, activating the endpoints of any minimizing cell yields a circularly optimal active setAk\+1A\_\{k\+1\}\.

###### Proof\.

Write

δk\+1≔Ck\+1∘−Ck∘\.\\delta\_\{k\+1\}\\coloneqq C\_\{k\+1\}^\{\\circ\}\-C\_\{k\}^\{\\circ\}\.
We first show that every candidate marginal is at leastδk\+1\\delta\_\{k\+1\}\. Fix an arbitrary current candidate cell𝒞∈ℭk\\mathcal\{C\}\\in\\mathfrak\{C\}\_\{k\}\. Choose a current cell different from𝒞\\mathcal\{C\}and, by[Lemma5](https://arxiv.org/html/2608.23910#Thmlemma5), select a free support gapθ\\thetacontained in that cell\. If only two inactive atoms remain, there are two complementary directed cells between them, and we choose the cell different from𝒞\\mathcal\{C\}\. Thus, in either case,θ\\thetalies outside𝒞\\mathcal\{C\}and belongs to none of the cells selected during the preceding iterations\.

By[Lemma6](https://arxiv.org/html/2608.23910#Thmlemma6), cutting the circle atθ\\thetais compatible with the entire sequence of cell selections that generatedAkA\_\{k\}\. SinceAkA\_\{k\}is circularly optimal by assumption, its line cost under this cut satisfies

W1,θline​\(Ak\)=Ck∘\.W\_\{1,\\theta\}^\{\\mathrm\{line\}\}\(A\_\{k\}\)=C\_\{k\}^\{\\circ\}\.Activating the two endpoints of𝒞\\mathcal\{C\}changes only the matching inside that cell\. By the definition of the local cell marginal and the line\-locality property, this produces a feasible cardinality\-\(k\+1\)\(k\+1\)line matching of cost

Ck∘\+𝔪⁡\(𝒞\)\.C\_\{k\}^\{\\circ\}\+\\mathfrak\{m\}\(\\mathcal\{C\}\)\.The same matching is feasible on the circle, and its circular geodesic cost is no larger than its cost in the fixed unwrapped representation\. Consequently,

Ck\+1∘≤Ck∘\+𝔪⁡\(𝒞\),C\_\{k\+1\}^\{\\circ\}\\leq C\_\{k\}^\{\\circ\}\+\\mathfrak\{m\}\(\\mathcal\{C\}\),or equivalently,

δk\+1≤𝔪⁡\(𝒞\)\.\\delta\_\{k\+1\}\\leq\\mathfrak\{m\}\(\\mathcal\{C\}\)\.\(24\)Since𝒞\\mathcal\{C\}was arbitrary, this inequality holds for every candidate cell inℭk\\mathfrak\{C\}\_\{k\}\.

We next establish the reverse inequality by exhibiting a candidate cell whose marginal equalsδk\+1\\delta\_\{k\+1\}\. LetMkM\_\{k\}be an optimal cardinality\-kkmatching supported on the particular active setAkA\_\{k\}produced by the greedy construction\. Applying[Theorem6](https://arxiv.org/html/2608.23910#Thmtheorem6)toMkM\_\{k\}yields a circularly optimal cardinality\-\(k\+1\)\(k\+1\)matchingMk\+1⋆M\_\{k\+1\}^\{\\star\}with active set

Ak\+1⋆=Ak∪\{x⋆,y⋆\},A\_\{k\+1\}^\{\\star\}=A\_\{k\}\\cup\\\{x^\{\\star\},y^\{\\star\}\\\},wherex⋆x^\{\\star\}is a previously inactive source atom andy⋆y^\{\\star\}is a previously inactive target atom\. By[Theorem7](https://arxiv.org/html/2608.23910#Thmtheorem7), these two newly activated atoms are consecutive in the cyclic ordering ofAkcA\_\{k\}^\{c\}\. They therefore delimit a current opposite\-endpoint candidate cell, which we denote by𝒞⋆\\mathcal\{C\}^\{\\star\}\.

By[Lemma3](https://arxiv.org/html/2608.23910#Thmlemma3), there exists an original support gap at which the circle can be cut so that the circular costs of bothAkA\_\{k\}andAk\+1⋆A\_\{k\+1\}^\{\\star\}are realized as line costs\. As established in the proof of[Theorem7](https://arxiv.org/html/2608.23910#Thmtheorem7), both active sets are optimal for the corresponding cardinality\-constrained line problems under this common cut\.

When more than two inactive atoms remain, the common cut cannot lie in the interior of𝒞⋆\\mathcal\{C\}^\{\\star\}\. Indeed, such a cut would placex⋆x^\{\\star\}andy⋆y^\{\\star\}at the two opposite ends of the linear inactive ordering, whereas the line\-neighbor property requires them to be consecutive\. If only two inactive atoms remain, the two complementary directed cells have the same endpoints, and we take𝒞⋆\\mathcal\{C\}^\{\\star\}to be the one whose interior does not contain the common cut\.

Thus, in all cases, the common cut lies outside𝒞⋆\\mathcal\{C\}^\{\\star\}\. The one\-dimensional locality principle then shows that the difference between the two optimal line costs is exactly the local marginal of this cell:

𝔪⁡\(𝒞⋆\)=W1line​\(Ak\+1⋆\)−W1line​\(Ak\)=Ck\+1∘−Ck∘=δk\+1\.\\mathfrak\{m\}\(\\mathcal\{C\}^\{\\star\}\)=W\_\{1\}^\{\\mathrm\{line\}\}\(A\_\{k\+1\}^\{\\star\}\)\-W\_\{1\}^\{\\mathrm\{line\}\}\(A\_\{k\}\)=C\_\{k\+1\}^\{\\circ\}\-C\_\{k\}^\{\\circ\}=\\delta\_\{k\+1\}\.It follows that

min𝒞∈ℭk⁡𝔪⁡\(𝒞\)≤𝔪⁡\(𝒞⋆\)=δk\+1\.\\min\_\{\\mathcal\{C\}\\in\\mathfrak\{C\}\_\{k\}\}\\mathfrak\{m\}\(\\mathcal\{C\}\)\\leq\\mathfrak\{m\}\(\\mathcal\{C\}^\{\\star\}\)=\\delta\_\{k\+1\}\.Combining this inequality with \([24](https://arxiv.org/html/2608.23910#A6.E24)\) proves \([23](https://arxiv.org/html/2608.23910#A6.E23)\)\.

Finally, suppose that𝒞\\mathcal\{C\}attains the minimum in \([23](https://arxiv.org/html/2608.23910#A6.E23)\)\. The construction in the first part of the proof gives a feasible circular cardinality\-\(k\+1\)\(k\+1\)matching whose cost is at most

Ck∘\+𝔪⁡\(𝒞\)=Ck∘\+δk\+1=Ck\+1∘\.C\_\{k\}^\{\\circ\}\+\\mathfrak\{m\}\(\\mathcal\{C\}\)=C\_\{k\}^\{\\circ\}\+\\delta\_\{k\+1\}=C\_\{k\+1\}^\{\\circ\}\.SinceCk\+1∘C\_\{k\+1\}^\{\\circ\}is the minimum cost among all feasible cardinality\-\(k\+1\)\(k\+1\)matchings, this matching must attainCk\+1∘C\_\{k\+1\}^\{\\circ\}\. Therefore, activating the endpoints of any minimizing candidate cell produces a circularly optimal active setAk\+1A\_\{k\+1\}\. ∎

###### Corollary 4\(Optimal nested sequence\)\.

Starting fromA0=∅A\_\{0\}=\\varnothingand repeatedly selecting a minimum\-marginal candidate cell produces an optimal active set for every cardinalityk=0,…,Kk=0,\\dots,K\.

### F\.1A constructive simultaneous cut

###### Theorem 9\(Simultaneous optimal cut\)\.

There exists an original support gapθ⋆\\theta^\{\\star\}such that, for everyk=0,…,Kk=0,\\dots,K,

Ck,θ⋆line=Ck∘\.C\_\{k,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}=C\_\{k\}^\{\\circ\}\.\(25\)Moreover, the greedy algorithm constructs such a gap\.

###### Proof\.

For every current cell, maintain one representative free gap\. Initially this is the cell’s unique original gap\. When a selected cell and its two neighbors merge, let the new cell inherit a free\-gap representative from either unselected neighboring cell, as guaranteed by[Lemma5](https://arxiv.org/html/2608.23910#Thmlemma5)\.[Figure11](https://arxiv.org/html/2608.23910#A6.F11)traces the resulting gap through a complete run: one original gap is avoided by every selection, so the same cut serves all cardinalities\.

Ifn≠mn\\neq m, the algorithm terminates with inactive atoms from only the larger measure\. Choose a representative free gap from any remaining current cell\. Ifn=mn=m, the final step starts with two inactive atoms and two complementary cells\. Select one cell and retain the free\-gap representative of the other\. In both cases, the resulting gapθ⋆\\theta^\{\\star\}belongs to no selected cell\.

By[Lemma6](https://arxiv.org/html/2608.23910#Thmlemma6), cutting atθ⋆\\theta^\{\\star\}gives

W1,θ⋆line​\(Ak\)=∑r=1k𝔪⁡\(𝒞r\)=Ck∘W\_\{1,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}\(A\_\{k\}\)=\\sum\_\{r=1\}^\{k\}\\mathfrak\{m\}\(\\mathcal\{C\}\_\{r\}\)=C\_\{k\}^\{\\circ\}for every greedy active setAkA\_\{k\}, where the last equality follows from[Theorem8](https://arxiv.org/html/2608.23910#Thmtheorem8)\. Therefore

Ck,θ⋆line≤Ck∘\.C\_\{k,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}\\leq C\_\{k\}^\{\\circ\}\.Conversely, any line matching is feasible on the circle with no larger geodesic cost, so

Ck∘≤Ck,θ⋆line\.C\_\{k\}^\{\\circ\}\\leq C\_\{k,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}\.The two inequalities imply \([25](https://arxiv.org/html/2608.23910#A6.E25)\)\. ∎

\(a\) One free gap survives every selection

θ⋆\\theta^\{\\star\}x1x\_\{1\}y1y\_\{1\}x2x\_\{2\}y2y\_\{2\}x3x\_\{3\}y3y\_\{3\}no selected cellcontainsθ⋆\\theta^\{\\star\}

All three selections avoided the gapθ⋆\\theta^\{\\star\}, so the same cut is valid for everykk\.

\(b\) Nested optimal plans after cutting atθ⋆\\theta^\{\\star\}

k=1k=1θ⋆\\theta^\{\\star\}θ⋆\+L\\theta^\{\\star\}\{\+\}Lk=2k=2θ⋆\\theta^\{\\star\}θ⋆\+L\\theta^\{\\star\}\{\+\}Lk=3k=3θ⋆\\theta^\{\\star\}θ⋆\+L\\theta^\{\\star\}\{\+\}LCk,θ⋆line=Ck∘C^\{\\rm line\}\_\{k,\\theta^\{\\star\}\}=C^\{\\circ\}\_\{k\}for everykk; each plan is recovered by sorted matching

The circle of \(a\), unwrapped atθ⋆\\theta^\{\\star\}into the interval\[θ⋆,θ⋆\+L\]\[\\theta^\{\\star\},\\theta^\{\\star\}\{\+\}L\]\. Atoms appear in the same cyclic order \(x1x\_\{1\},y1y\_\{1\},x2x\_\{2\},y2y\_\{2\},x3x\_\{3\},y3y\_\{3\}\); one admissible nested activation order is shown\.

Figure 11:Constructive simultaneous cut\. The free gapθ⋆\\theta^\{\\star\}is contained in no selected cell, so the complete nested sequence can be cut and unwrapped at the same location\. On the resulting line, the active sets grow by local sorted\-matching updates andCk,θ⋆line=Ck∘C\_\{k,\\theta^\{\\star\}\}^\{\\mathrm\{line\}\}=C\_\{k\}^\{\\circ\}for every transported cardinalitykk\.###### Example 1\(A cut optimal atk=Kk=Kand unbounded atk=1k=1\)\.

Taken=m=2n=m=2on a circle of circumferenceLL, with0<δ<L/40<\\delta<L/4:

x=\{0,L/4\},y=\{δ,3​L/4\}\.x=\\\{0,\\;L/4\\\},\\qquad y=\\\{\\delta,\\;3L/4\\\}\.\(26\)WriteG0=\(0,δ\)G\_\{0\}=\(0,\\delta\)andG2=\(L/4,3​L/4\)G\_\{2\}=\(L/4,3L/4\)for the two gaps whose cumulative imbalance sits one level above their neighbours\. Together they carryδ\+L/2\>L/2\\delta\+L/2\>L/2of the circumference, so that level is the weighted median in \([12](https://arxiv.org/html/2608.23910#A3.E12)\) and, by[Proposition1](https://arxiv.org/html/2608.23910#Thmproposition1),

G0,G2∈ΘK:=\{r:CK,rline=CK∘\},K=2\.G\_\{0\},G\_\{2\}\\in\\Theta\_\{K\}:=\\bigl\\\{r:\\ C\_\{K,r\}^\{\\mathrm\{line\}\}=C\_\{K\}^\{\\circ\}\\bigr\\\},\\qquad K=2\.\(27\)Both are therefore admissible choices for a rule that cuts where the full\-mass problem is solved, andG0G\_\{0\}is the first of them in index order\.

Atk=1k=1the two disagree\. The closest opposite\-type pair is\(0,δ\)\(0,\\delta\), soC1∘=w​δC\_\{1\}^\{\\circ\}=w\\delta, and cutting inG2G\_\{2\}recovers it\. Cutting inG0G\_\{0\}separates that pair: their unwrapped distance becomesL−δL\-\\delta, and the sorted line matching falls back on the runner\-upd2=L/4−δd\_\{2\}=L/4\-\\delta\. Hence

C1,G0line−C1∘C1∘=d2−δδ=L/4−2​δδ→δ→0∞\.\\frac\{C\_\{1,G\_\{0\}\}^\{\\mathrm\{line\}\}\-C\_\{1\}^\{\\circ\}\}\{C\_\{1\}^\{\\circ\}\}=\\frac\{d\_\{2\}\-\\delta\}\{\\delta\}=\\frac\{L/4\-2\\delta\}\{\\delta\}\\;\\xrightarrow\[\\ \\delta\\to 0\\ \]\{\}\\;\\infty\.\(28\)The mechanism is thatC1∘C\_\{1\}^\{\\circ\}is a*geodesic*nearest\-pair distance whereasC1,rlineC\_\{1,r\}^\{\\mathrm\{line\}\}is an*unwrapped*one, and nothing couples the location of the closest pair to the median that fixesΘK\\Theta\_\{K\}\. So no bound of the formCk,rline≤c​Ck∘C\_\{k,r\}^\{\\mathrm\{line\}\}\\leq c\\,C\_\{k\}^\{\\circ\}holds uniformly overr∈ΘKr\\in\\Theta\_\{K\}, for any constantcc: the full\-mass problem carries no information about the small\-mass ones\. This is what[Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9)supplies and a single cut cannot\.

## Appendix GConstant\-time cell\-marginal queries

We now adapt the minimal\-chain preprocessing ofPAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)to cyclic intervals\.

### G\.1Doubled cyclic sequence

Let

z1<z2<⋯<zN<z1\+Lz\_\{1\}<z\_\{2\}<\\cdots<z\_\{N\}<z\_\{1\}\+Lbe the sorted union support, and define labels

σi=\{\+1,zi∈supp⁡μ,−1,zi∈supp⁡ν\.\\sigma\_\{i\}=\\begin\{cases\}\+1,&z\_\{i\}\\in\\operatorname\{supp\}\\mu,\\\\ \-1,&z\_\{i\}\\in\\operatorname\{supp\}\\nu\.\\end\{cases\}\(29\)Form the doubled sequence

z~i=zi,z~i\+N=zi\+L,σ~i=σ~i\+N=σi,i=1,…,N\.\\widetilde\{z\}\_\{i\}=z\_\{i\},\\quad\\widetilde\{z\}\_\{i\+N\}=z\_\{i\}\+L,\\quad\\widetilde\{\\sigma\}\_\{i\}=\\widetilde\{\\sigma\}\_\{i\+N\}=\\sigma\_\{i\},\\qquad i=1,\\dots,N\.\(30\)Every clockwise circular cell can be represented by a standard interval\[a,b\]⊂\{1,…,2​N\}\[a,b\]\\subset\\\{1,\\dots,2N\\\}withb−a<Nb\-a<N\.

Define prefix differential ranks and signed coordinate sums

R0=0,Rt=∑i=1tσ~i,R\_\{0\}=0,\\qquad R\_\{t\}=\\sum\_\{i=1\}^\{t\}\\widetilde\{\\sigma\}\_\{i\},\(31\)S0=0,St=∑i=1tσ~i​z~i\.S\_\{0\}=0,\\qquad S\_\{t\}=\\sum\_\{i=1\}^\{t\}\\widetilde\{\\sigma\}\_\{i\}\\widetilde\{z\}\_\{i\}\.\(32\)An interval\[a,b\]\[a,b\]is balanced if and only if

Rb=Ra−1\.R\_\{b\}=R\_\{a\-1\}\.\(33\)
For eachtt, let

pt=max⁡\{s<t:Rs=Rt\},p\_\{t\}=\\max\\\{s<t:R\_\{s\}=R\_\{t\}\\\},\(34\)when this set is nonempty\. Then\[pt\+1,t\]\[p\_\{t\}\+1,t\]is the minimal balanced interval ending attt\.

###### Lemma 7\(Minimal\-chain cost\)\.

Ifptp\_\{t\}exists, then

cℝ​\(\[pt\+1,t\]\)=w​\|St−Spt\|\.c\_\{\\mathbb\{R\}\}\(\[p\_\{t\}\+1,t\]\)=w\\left\|S\_\{t\}\-S\_\{p\_\{t\}\}\\right\|\.\(35\)

###### Proof\.

By the maximality ofptp\_\{t\}, the relative rankRs−RptR\_\{s\}\-R\_\{p\_\{t\}\}does not return to zero forpt<s<tp\_\{t\}<s<t\. It therefore has a constant strict sign throughout the interval\. Equivalently, every pair in the increasing\-order line matching has the same orientation\. The sum of absolute pair displacements is consequently the absolute difference between the sum of source coordinates and the sum of target coordinates, which is\|St−Spt\|\|S\_\{t\}\-S\_\{p\_\{t\}\}\|\. Multiplying bywwgives \([35](https://arxiv.org/html/2608.23910#A7.E35)\)\. This is the minimal\-chain identity used byPAWLfor the Manhattan cost\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\. ∎

[Figure12](https://arxiv.org/html/2608.23910#A7.F12)illustrates the two ingredients: a balanced interval decomposing into adjacent minimal chains, and the differential\-rank walk whose first returns identify them\. Define the maximal\-chain prefix costQtQ\_\{t\}recursively by

Q0=0,Qt=\{Qpt\+w​\|St−Spt\|,pt​exists,0,pt​does not exist\.Q\_\{0\}=0,\\qquad Q\_\{t\}=\\begin\{cases\}Q\_\{p\_\{t\}\}\+w\|S\_\{t\}\-S\_\{p\_\{t\}\}\|,&p\_\{t\}\\text\{ exists\},\\\\ 0,&p\_\{t\}\\text\{ does not exist\}\.\\end\{cases\}\(36\)
###### Proposition 2\(Balanced interval query\)\.

For every balanced interval\[a,b\]\[a,b\]in the doubled sequence,

cℝ​\(\[a,b\]\)=Qb−Qa−1\.c\_\{\\mathbb\{R\}\}\(\[a,b\]\)=Q\_\{b\}\-Q\_\{a\-1\}\.\(37\)

###### Proof\.

Repeatedly applyingptp\_\{t\}decomposes every balanced interval into a unique sequence of adjacent minimal balanced intervals\. The increasing\-order line matching never crosses a boundary between adjacent balanced blocks, so their costs add\. BecauseRb=Ra−1R\_\{b\}=R\_\{a\-1\}, the maximal\-chain decomposition ending ata−1a\-1is exactly the prefix of the maximal\-chain decomposition ending atbb\. Subtracting their accumulated costs gives \([37](https://arxiv.org/html/2608.23910#A7.E37)\)\. This is the same dynamic\-programming principle as the maximal\-chain cost identity inPAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\. ∎

###### Corollary 5\(Constant\-time candidate marginal\)\.

Let a candidate cell be represented by the balanced doubled interval\[a,b\]\[a,b\]\. Then

𝔪⁡\(\[a,b\]\)=\(Qb−Qa−1\)−\(Qb−1−Qa\),\\mathfrak\{m\}\(\[a,b\]\)=\\bigl\(Q\_\{b\}\-Q\_\{a\-1\}\\bigr\)\-\\bigl\(Q\_\{b\-1\}\-Q\_\{a\}\\bigr\),\(38\)with the second term interpreted as zero when the interior is empty\. Hence a candidate marginal is evaluated inO⁡\(1\)O\(1\)time after preprocessing\.

###### Proof\.

The outer interval\[a,b\]\[a,b\]and the interior\[a\+1,b−1\]\[a\+1,b\-1\]are balanced by[Lemma4](https://arxiv.org/html/2608.23910#Thmlemma4)\. Apply[Proposition2](https://arxiv.org/html/2608.23910#Thmproposition2)to both and use \([20](https://arxiv.org/html/2608.23910#A5.E20)\)\. ∎

\(a\) A balanced interval in the doubled sequence decomposes into minimal balanced chains

⋯\\cdots⋯\\cdotsy1y\_\{1\}x1x\_\{1\}x2x\_\{2\}x3x\_\{3\}y2y\_\{2\}y3y\_\{3\}y4y\_\{4\}x4x\_\{4\}𝒞1⋆\\mathcal\{C\}\_\{1\}^\{\\star\}𝒞2⋆\\mathcal\{C\}\_\{2\}^\{\\star\}𝒞3⋆\\mathcal\{C\}\_\{3\}^\{\\star\}\[a,b\]=𝒞1⋆∪𝒞2⋆∪𝒞3⋆\[a,b\]=\\mathcal\{C\}\_\{1\}^\{\\star\}\\cup\\mathcal\{C\}\_\{2\}^\{\\star\}\\cup\\mathcal\{C\}\_\{3\}^\{\\star\}

z~i\+N=z~i\+L,cℝ​\(\[a,b\]\)=∑rcℝ​\(𝒞r⋆\)=Qb−Qa−1\.\\widetilde\{z\}\_\{i\+N\}=\\widetilde\{z\}\_\{i\}\+L,\\qquad c\_\{\\mathbb\{R\}\}\(\[a,b\]\)=\\sum\_\{r\}c\_\{\\mathbb\{R\}\}\(\\mathcal\{C\}\_\{r\}^\{\\star\}\)=Q\_\{b\}\-Q\_\{a\-1\}\.
\(b\) Differential\-rank walk

ttRt−Ra−1R\_\{t\}\-R\_\{a\-1\}a−1a\{\-\}1bbfirst returnfirst returnfirst return

A balanced interval satisfiesRb=Ra−1R\_\{b\}=R\_\{a\-1\}\. For each endpointtt, the most recent previous occurrence

pt=max⁡\{s<t:Rs=Rt\}p\_\{t\}=\\max\\\{s<t:R\_\{s\}=R\_\{t\}\\\}identifies the minimal chain ending attt\. Its cost is

cℝ​\(\[pt\+1,t\]\)=w​\|St−Spt\|\.c\_\{\\mathbb\{R\}\}\(\[p\_\{t\}\+1,t\]\)=w\\lvert S\_\{t\}\-S\_\{p\_\{t\}\}\\rvert\.When\[a,b\]\[a,b\]represents a candidate cell, as above \(opposite\-type endpoints, balanced interior\), its marginal

𝔪⁡\(\[a,b\]\)=\(Qb−Qa−1\)−\(Qb−1−Qa\)\\mathfrak\{m\}\(\[a,b\]\)=\(Q\_\{b\}\-Q\_\{a\-1\}\)\-\(Q\_\{b\-1\}\-Q\_\{a\}\)is obtained from four table lookups\.

Figure 12:Constant\-time cell\-cost preprocessing on the doubled cyclic sequence\. A balanced interval decomposes uniquely into adjacent minimal balanced chains, analogous to the chain decomposition inPAWL\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\. Repeated differential\-rank values identify the minimal chains; their costs are signed\-coordinate prefix differences\. The accumulated valuesQtQ\_\{t\}then provide both the cell cost and its interior cost with constant\-time table lookups\.All valuesRt,St,pt,QtR\_\{t\},S\_\{t\},p\_\{t\},Q\_\{t\}fort=0,…,2​Nt=0,\\dots,2Nare computed inO⁡\(N\)O\(N\)time after sorting\. The predecessorptp\_\{t\}is found by storing the most recent index of each integer differential\-rank value in a hash table or array indexed over the rank range\[−2​N,2​N\]\[\-2N,2N\]\.

## Appendix HCorrectness and complexity

The active/inactive cyclic order is maintained by a circular doubly linked list\. Each directed current cell stores its endpoints and a representative free original gap\. Candidate cells are stored in a min\-heap keyed by \([38](https://arxiv.org/html/2608.23910#A7.E38)\)\. Heap deletion is lazy: an entry is valid only if both endpoints remain inactive and the second endpoint is still the clockwise successor of the first\.

###### Theorem 10\(Correctness and complexity\)\.

Under[Assumption2](https://arxiv.org/html/2608.23910#Thmassumption2),[Algorithm1](https://arxiv.org/html/2608.23910#alg1)returns the exact valuesCk∘C\_\{k\}^\{\\circ\}and an optimal active set for everyk=0,…,Kk=0,\\dots,K, together with a gapθ⋆\\theta^\{\\star\}satisfying \([25](https://arxiv.org/html/2608.23910#A6.E25)\)\. Its time and memory complexities are

time=O\(NlogN\),memory=O\(N\)\.\\boxed\{\\text\{time \}=O\(N\\log N\),\\qquad\\text\{memory \}=O\(N\)\.\}\(39\)

###### Proof\.

Correctness follows inductively from[Theorem8](https://arxiv.org/html/2608.23910#Thmtheorem8); the simultaneous cut is guaranteed by[Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9)\. Sorting costsO⁡\(N​log⁡N\)O\(N\\log N\)\. The doubled\-sequence preprocessing and linked\-list initialization costO⁡\(N\)O\(N\)\. There are at mostNNinitial heap entries and at most one new candidate insertion per iteration\. Thus onlyO⁡\(N\)O\(N\)heap entries are ever created\. Every entry is popped at most once, valid or stale, and each heap operation costsO⁡\(log⁡N\)O\(\\log N\)\. Candidate\-key evaluation, linked\-list updates, and free\-gap inheritance areO⁡\(1\)O\(1\)\. The heap, linked list, preprocessing arrays, and activation records all useO⁡\(N\)O\(N\)memory\. ∎

## Appendix IPlan recovery and arbitrary transported masses

### I\.1Integer cardinalities

The activation rank of each atom determines the optimal active setAkA\_\{k\}\. Cut the circle at the simultaneous gapθ⋆\\theta^\{\\star\}, retain the atoms activated by iterationkk, and match the retained source and target atoms in increasing unwrapped order\. By[Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9), this line matching has valueCk∘C\_\{k\}^\{\\circ\}and is therefore circularly optimal\.

If the selected atoms are filtered from the already sorted circular order, the matching can be recovered inO⁡\(N\)O\(N\)time; sorting only the selected atoms gives the simplerO⁡\(k​log⁡k\)O\(k\\log k\)implementation\.

### I\.2Noninteger transported mass

Lets∈\[0,K​w\]s\\in\[0,Kw\]and write

k=⌊sw⌋,λ=s−k​ww∈\[0,1\]\.k=\\left\\lfloor\\frac\{s\}\{w\}\\right\\rfloor,\\qquad\\lambda=\\frac\{s\-kw\}\{w\}\\in\[0,1\]\.\(40\)Letπk\\pi\_\{k\}andπk\+1\\pi\_\{k\+1\}be consecutive optimal transport plans associated with the nested sequence\. Then

πs=\(1−λ\)​πk\+λ​πk\+1\\pi\_\{s\}=\(1\-\\lambda\)\\pi\_\{k\}\+\\lambda\\pi\_\{k\+1\}\(41\)is feasible for transported massss\.

###### Proposition 3\(Interpolation\)\.

The plan \([41](https://arxiv.org/html/2608.23910#A9.E41)\) is optimal, and

PW∘⁡\(s\)=\(1−λ\)​Ck∘\+λ​Ck\+1∘\.\\operatorname\{PW\}\_\{\\circ\}\(s\)=\(1\-\\lambda\)C\_\{k\}^\{\\circ\}\+\\lambda C\_\{k\+1\}^\{\\circ\}\.\(42\)

###### Proof\.

The partial matching problem is a min\-cost flow problem with integral capacities\. Its optimal value as a function of the required flow is convex and piecewise linear, with breakpoints at integer flow values; successive shortest augmentations give nondecreasing marginal costs\([Ahuja et al\., 1993](https://arxiv.org/html/2608.23910#bib.bib1)\)\. Therefore the value on\[k,k\+1\]\[k,k\+1\]is the linear interpolation ofCk∘C\_\{k\}^\{\\circ\}andCk\+1∘C\_\{k\+1\}^\{\\circ\}\. The feasible plan \([41](https://arxiv.org/html/2608.23910#A9.E41)\) attains exactly that value\. Equivalently, after cutting atθ⋆\\theta^\{\\star\}, this is the interpolation principle used byPAWLon the line\([Chapel and Tavenard, 2025](https://arxiv.org/html/2608.23910#bib.bib3)\)\. ∎

## Appendix JSpherical slicing and partial transport on𝕊d−1\\mathbb\{S\}^\{d\-1\}

The construction so far is exact but one\-dimensional\. This section uses it as a primitive: we recall the spherical slicing of[Bonet et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib8)and[Liu et al\. \(2025\)](https://arxiv.org/html/2608.23910#bib.bib9), and then define a sliced discrepancy that inheritsPAWC’s partial structure, so that the whole transported\-mass profile on𝕊d−1\\mathbb\{S\}^\{d\-1\}is available at once, and the two measures need not carry the same mass\.

### J\.1Great circles and the geodesic projection

Let𝕊d−1=\{x∈ℝd:‖x‖2=1\}\\mathbb\{S\}^\{d\-1\}=\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|\_\{2\}=1\\\}with the geodesic distanced𝕊d−1​\(x,y\)=arccos⁡⟨x,y⟩d\_\{\\mathbb\{S\}^\{d\-1\}\}\(x,y\)=\\arccos\\langle x,y\\rangle\. The geodesics of𝕊d−1\\mathbb\{S\}^\{d\-1\}are its great circles, obtained by intersecting the sphere with a two\-dimensional linear subspace\. Slicing on𝕊d−1\\mathbb\{S\}^\{d\-1\}therefore replaces the lines of Euclidean sliced transport by great circles, and the one\-dimensional problem it leaves behind is a transport problem on a circle rather than on a line – which is precisely the problem[Algorithm1](https://arxiv.org/html/2608.23910#alg1)solves\.

Following[Bonet et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib8), subspaces are parameterised by the Stiefel manifold

Vd,2=\{U∈ℝd×2:U⊤​U=I2\},V\_\{d,2\}=\\\{U\\in\\mathbb\{R\}^\{d\\times 2\}:U^\{\\\!\\top\}U=I\_\{2\}\\\},\(43\)which covers the GrassmannianGd,2G\_\{d,2\}of two\-planes throughU↦U​U⊤U\\mapsto UU^\{\\\!\\top\}\([Bendokat et al\., 2020](https://arxiv.org/html/2608.23910#bib.bib11)\)\. EachU∈Vd,2U\\in V\_\{d,2\}gives the great circle𝒞U=span⁡\(U\)∩𝕊d−1\\mathcal\{C\}\_\{U\}=\\mathrm\{span\}\(U\)\\cap\\mathbb\{S\}^\{d\-1\}, and the natural map onto it is the geodesic projection

ΠU​\(x\)=arg​miny∈𝒞U⁡d𝕊d−1​\(x,y\)=U​U⊤​x‖U⊤​x‖2∈𝒞U⊂ℝd,\\Pi\_\{U\}\(x\)=\\operatorname\*\{arg\\,min\}\_\{y\\in\\mathcal\{C\}\_\{U\}\}d\_\{\\mathbb\{S\}^\{d\-1\}\}\(x,y\)=\\frac\{UU^\{\\\!\\top\}x\}\{\\\|U^\{\\\!\\top\}x\\\|\_\{2\}\}\\;\\in\\;\\mathcal\{C\}\_\{U\}\\subset\\mathbb\{R\}^\{d\},\(44\)defined except on\{x:U⊤​x=0\}\\\{x:U^\{\\\!\\top\}x=0\\\}, a subsphere of codimension two that is null for any measure charging no such set\([Bardelli and Mennucci, 2017](https://arxiv.org/html/2608.23910#bib.bib12)\), so the pushforwards below are well defined\.

The columns ofUUform an orthonormal basis ofspan⁡\(U\)\\mathrm\{span\}\(U\), soz↦U​zz\\mapsto Uzis an isometry from𝕊1\\mathbb\{S\}^\{1\}onto𝒞U\\mathcal\{C\}\_\{U\}andΠU=U​PU\\Pi\_\{U\}=U\\,P^\{U\}, where

PU​\(x\)=U⊤​ΠU​\(x\)=U⊤​x‖U⊤​x‖2∈𝕊1P^\{U\}\(x\)=U^\{\\\!\\top\}\\Pi\_\{U\}\(x\)=\\frac\{U^\{\\\!\\top\}x\}\{\\\|U^\{\\\!\\top\}x\\\|\_\{2\}\}\\;\\in\\;\\mathbb\{S\}^\{1\}\(45\)is the coordinate representation of \([44](https://arxiv.org/html/2608.23910#A10.E44)\) in the basisUU\([Bonet et al\., 2023](https://arxiv.org/html/2608.23910#bib.bib8), Lemma 1\)\. The two are kept apart deliberately:ΠU\\Pi\_\{U\}lands on the great circle inℝd\\mathbb\{R\}^\{d\}, whereasPUP^\{U\}is its coordinate vector inℝ2\\mathbb\{R\}^\{2\}, and it isPUP^\{U\}that the one\-dimensional solver consumes\. Concretely,[Algorithm1](https://arxiv.org/html/2608.23910#alg1)is run on the circular coordinate

θU​\(x\)=atan2⁡\(\(U⊤​x\)2,\(U⊤​x\)1\)mod2​π∈\[0,2​π\),\\theta\_\{U\}\(x\)=\\operatorname\{atan2\}\\bigl\(\(U^\{\\\!\\top\}x\)\_\{2\},\\;\(U^\{\\\!\\top\}x\)\_\{1\}\\bigr\)\\bmod 2\\pi\\;\\in\\;\[0,2\\pi\),\(46\)that is, on𝕊L1\\mathbb\{S\}^\{1\}\_\{L\}with circumferenceL=2​πL=2\\pi; becausez↦U​zz\\mapsto Uzis an isometry, arc length along𝒞U\\mathcal\{C\}\_\{U\}agrees with arc length in the coordinateθU\\theta\_\{U\}, so no rescaling is needed\.[Figure4](https://arxiv.org/html/2608.23910#S5.F4)\(a\) illustrates the projection\.

Two features of this construction matter here\. First, the image ofPUP^\{U\}is a circle of circumference2​π2\\pi, so the slice inherits the cyclic structure with no distinguished boundary – the difficulty that motivated everything above, now arising for a second reason\. Second,PUP^\{U\}is a pushforward of measures, so it preserves total mass and maps atoms to atoms: an empirical measure withnnatoms of common weightwwbecomes an empirical measure on𝕊1\\mathbb\{S\}^\{1\}withnnatoms of the same weightww\. The standing assumptions of[Assumption2](https://arxiv.org/html/2608.23910#Thmassumption2)are therefore met on almost every slice, distinctness of the projected support failing only on aσ\\sigma\-null set ofUU\.

### J\.2Sliced spherical partial Wasserstein

Letσ\\sigmabe the uniform probability measure onVd,2V\_\{d,2\}\. For probability measuresμ,ν∈𝒫⁡\(𝕊d−1\)\\mu,\\nu\\in\\mathcal\{P\}\(\\mathbb\{S\}^\{d\-1\}\),[Bonet et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib8)define the spherical sliced\-Wasserstein discrepancy by averaging the circular Wasserstein distance over slices,

SSWpp​\(μ,ν\)=∫Vd,2Wp,∘p​\(P\#U​μ,P\#U​ν\)​𝑑σ​\(U\)\.\\mathrm\{SSW\}\_\{p\}^\{p\}\(\\mu,\\nu\)=\\int\_\{V\_\{d,2\}\}W\_\{p,\\circ\}^\{p\}\\bigl\(P^\{U\}\_\{\\\#\}\\mu,\\,P^\{U\}\_\{\\\#\}\\nu\\bigr\)\\,d\\sigma\(U\)\.\(47\)This presumesμ\\muandν\\nuare probability measures, hence of equal mass\. We drop that requirement\.

Letμ\\muandν\\nube finite positive measures on𝕊d−1\\mathbb\{S\}^\{d\-1\}with uniformly weighted atoms,

μ=w∑i=1nδxi,ν=w∑j=1mδyj,xi,yj∈𝕊d−1,w\>0,\\mu=w\\sum\_\{i=1\}^\{n\}\\delta\_\{x\_\{i\}\},\\qquad\\nu=w\\sum\_\{j=1\}^\{m\}\\delta\_\{y\_\{j\}\},\\qquad x\_\{i\},y\_\{j\}\\in\\mathbb\{S\}^\{d\-1\},\\ w\>0,\(48\)withn≠mn\\neq mallowed, so thatμ⁡\(𝕊d−1\)=n​w\\mu\(\\mathbb\{S\}^\{d\-1\}\)=nwandν⁡\(𝕊d−1\)=m​w\\nu\(\\mathbb\{S\}^\{d\-1\}\)=mwmay differ\. Because eachPUP^\{U\}preserves mass, the admissible transported massess∈\[0,K​w\]s\\in\[0,Kw\]withK=min⁡\{n,m\}K=\\min\\\{n,m\\\}are the same on every slice; a singlessis thus meaningful across all ofVd,2V\_\{d,2\}simultaneously\.

###### Definition 4\(Sliced spherical partial Wasserstein\)\.

Fors∈\[0,K​w\]s\\in\[0,Kw\]andμ,ν\\mu,\\nuas in \([48](https://arxiv.org/html/2608.23910#A10.E48)\), define

SSPW⁡\(s,μ,ν\)=∫Vd,2PW∘⁡\(s,P\#U​μ,P\#U​ν\)​𝑑σ​\(U\),\\mathrm\{SSPW\}\(s;\\mu,\\nu\)=\\int\_\{V\_\{d,2\}\}\\operatorname\{PW\}\_\{\\circ\}\\bigl\(s;\\,P^\{U\}\_\{\\\#\}\\mu,\\,P^\{U\}\_\{\\\#\}\\nu\\bigr\)\\,d\\sigma\(U\),\(49\)wherePW∘⁡\(s,⋅,⋅\)\\operatorname\{PW\}\_\{\\circ\}\(s;\\cdot,\\cdot\)is the partial transport cost \([6](https://arxiv.org/html/2608.23910#A2.E6)\) on the circle, i\.e\. the quantity[Algorithm1](https://arxiv.org/html/2608.23910#alg1)returns for every admissiblessin a single run\.

At integer cardinalities the integrand isCk∘C\_\{k\}^\{\\circ\}of \([8](https://arxiv.org/html/2608.23910#A2.E8)\) evaluated on the projected measures; between them it is the interpolation of[Proposition3](https://arxiv.org/html/2608.23910#Thmproposition3)\. Four remarks fix the scope of the definition\.

### J\.3Estimation and cost

In practice \([49](https://arxiv.org/html/2608.23910#A10.E49)\) is estimated by Monte Carlo over slices; we writeMMfor their number, reservingLLfor the circumference as elsewhere\. DrawU1,…,UMU\_\{1\},\\dots,U\_\{M\}i\.i\.d\. fromσ\\sigma, for instance by QR factorisation of ad×2d\\times 2Gaussian matrix, and set

SSPW^​\(s,μ,ν\)=1M​∑ℓ=1MPW∘⁡\(s,P\#Uℓ​μ,P\#Uℓ​ν\)\.\\widehat\{\\mathrm\{SSPW\}\}\(s;\\mu,\\nu\)=\\frac\{1\}\{M\}\\sum\_\{\\ell=1\}^\{M\}\\operatorname\{PW\}\_\{\\circ\}\\bigl\(s;\\,P^\{U\_\{\\ell\}\}\_\{\\\#\}\\mu,\\,P^\{U\_\{\\ell\}\}\_\{\\\#\}\\nu\\bigr\)\.\(52\)
###### Proposition 4\(Uniform concentration of the sliced estimate\)\.

Letμ,ν\\mu,\\nube as in \([48](https://arxiv.org/html/2608.23910#A10.E48)\) and letU1,…,UMU\_\{1\},\\dots,U\_\{M\}be i\.i\.d\.σ\\sigma\. For every fixeds∈\[0,K​w\]s\\in\[0,Kw\]and everyε\>0\\varepsilon\>0,

Pr⁡\(\|SSPW^​\(s,μ,ν\)−SSPW⁡\(s,μ,ν\)\|≥ε\)≤2​exp⁡\(−2​M​ε2π2​s2\)\.\\Pr\\Bigl\(\\bigl\|\\widehat\{\\mathrm\{SSPW\}\}\(s;\\mu,\\nu\)\-\\mathrm\{SSPW\}\(s;\\mu,\\nu\)\\bigr\|\\geq\\varepsilon\\Bigr\)\\;\\leq\\;2\\exp\\\!\\Bigl\(\-\\frac\{2M\\varepsilon^\{2\}\}\{\\pi^\{2\}s^\{2\}\}\\Bigr\)\.\(53\)Uniformly over the profile,

Pr⁡\(sups∈\[0,K​w\]\|SSPW^​\(s,μ,ν\)−SSPW⁡\(s,μ,ν\)\|≥ε\)≤2​\(K\+1\)​exp⁡\(−2​M​ε2π2​K2​w2\),\\Pr\\Bigl\(\\sup\_\{s\\in\[0,Kw\]\}\\bigl\|\\widehat\{\\mathrm\{SSPW\}\}\(s;\\mu,\\nu\)\-\\mathrm\{SSPW\}\(s;\\mu,\\nu\)\\bigr\|\\geq\\varepsilon\\Bigr\)\\;\\leq\\;2\(K\+1\)\\exp\\\!\\Bigl\(\-\\frac\{2M\\varepsilon^\{2\}\}\{\\pi^\{2\}K^\{2\}w^\{2\}\}\\Bigr\),\(54\)so thatM≥\(π2​K2​w2/2​ε2\)​log⁡\(2​\(K\+1\)/δ\)M\\geq\\bigl\(\\pi^\{2\}K^\{2\}w^\{2\}/2\\varepsilon^\{2\}\\bigr\)\\log\\bigl\(2\(K\+1\)/\\delta\\bigr\)slices suffice forε\\varepsilon\-accuracy on the entire profile with probability at least1−δ1\-\\delta\.

###### Proof\.

Fixssand setZℓ=PW∘⁡\(s,P\#Uℓ​μ,P\#Uℓ​ν\)Z\_\{\\ell\}=\\operatorname\{PW\}\_\{\\circ\}\\bigl\(s;P^\{U\_\{\\ell\}\}\_\{\\\#\}\\mu,P^\{U\_\{\\ell\}\}\_\{\\\#\}\\nu\\bigr\), so theZℓZ\_\{\\ell\}are i\.i\.d\. with meanSSPW⁡\(s,μ,ν\)\\mathrm\{SSPW\}\(s;\\mu,\\nu\)\. A transport plan of massssmoves no mass further than the geodesic radiusπ\\piof a circle of circumference2​π2\\pi, whence0≤Zℓ≤π​s0\\leq Z\_\{\\ell\}\\leq\\pi s; the upper end is attained when every transported pair is antipodal, so the range cannot be tightened without further assumptions onμ\\muandν\\nu\. Hoeffding’s inequality for i\.i\.d\. variables confined to an interval of lengthπ​s\\pi sgives \([53](https://arxiv.org/html/2608.23910#A10.E53)\)\.

For \([54](https://arxiv.org/html/2608.23910#A10.E54)\), apply \([53](https://arxiv.org/html/2608.23910#A10.E53)\) at each breakpoints=k​ws=kw,k=0,…,Kk=0,\\dots,K, with the range relaxed to the uniform boundπ​K​w\\pi Kw, and take a union bound over theK\+1K\+1breakpoints\. By[Proposition3](https://arxiv.org/html/2608.23910#Thmproposition3)every slice profile is linear on\[k​w,\(k\+1\)​w\]\[kw,\(k\+1\)w\]; hence so areSSPW^\\widehat\{\\mathrm\{SSPW\}\}andSSPW\\mathrm\{SSPW\}, being an average and an integral of such profiles over a common breakpoint set, and hence so is their difference\. A linear function attains its maximum modulus on an interval at an endpoint, so control at the breakpoints controls the supremum\. ∎

Each term of \([52](https://arxiv.org/html/2608.23910#A10.E52)\) costs one projection of theN=n\+mN=n\+matoms,O⁡\(d​N\)O\(dN\), followed by a single call to[Algorithm1](https://arxiv.org/html/2608.23910#alg1),O⁡\(N​log⁡N\)O\(N\\log N\)by[Theorem10](https://arxiv.org/html/2608.23910#Thmtheorem10)\. The estimator therefore costs

O⁡\(M​N​\(d\+log⁡N\)\)O\\bigl\(M\\,N\(d\+\\log N\)\\bigr\)\(55\)in time andO⁡\(N\)O\(N\)in memory beyond the input,*for the entire profile inss*\. The slices are independent and embarrassingly parallel\.

Two points are worth isolating\. First, the profile is free: obtainingSSPW⁡\(s,⋅,⋅\)\\mathrm\{SSPW\}\(s;\\cdot,\\cdot\)at every admissiblesscosts the same as obtaining it at one, because[Algorithm1](https://arxiv.org/html/2608.23910#alg1)produces all cardinalities in a single sweep\. A construction built instead on a per\-sscircular solver would pay a further factor ofK=Θ⁡\(N\)K=\\Theta\(N\), which is exactly the cut\-enumeration penalty measured in[SectionK\.4](https://arxiv.org/html/2608.23910#A11.SS4)\. Second, replacing the circular solver by theO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)cut\-enumeration reference of[Corollary2](https://arxiv.org/html/2608.23910#Thmcorollary2)would raise \([55](https://arxiv.org/html/2608.23910#A10.E55)\) toO⁡\(L​N2​log⁡N\)O\(LN^\{2\}\\log N\); the sliced construction is what makes theO⁡\(N​log⁡N\)O\(N\\log N\)solver worth having, and theO⁡\(N​log⁡N\)O\(N\\log N\)solver is what makes the sliced construction affordable at the sizes reported in[SectionK\.4](https://arxiv.org/html/2608.23910#A11.SS4)\.

## Appendix KNumerical validation of the solver

This section reports an implementation of[Algorithm1](https://arxiv.org/html/2608.23910#alg1)and the programme used to verify it\. The cut envelope \([14](https://arxiv.org/html/2608.23910#A3.E14)\) supplies a direct exact oracle – enumerate every original support gap, cut and unwrap there, run linePAWLonce to obtain allCk,rlineC\_\{k,r\}^\{\\mathrm\{line\}\}, and compare thePAWCoutput tominr⁡Ck,rline\\min\_\{r\}C\_\{k,r\}^\{\\mathrm\{line\}\}for everykk– and a cardinality\-constrained assignment solver applied separately for eachkksupplies a second, slower oracle that does not use the circle\-cut structure at all\. Everything below is reproducible from a fixed set of seeds; the timing data and the fitted slopes are emitted directly by the benchmark script into a CSV whose header records the environment, package versions, and machine\.

### K\.1Solvers and the trust hierarchy

Four solvers are compared, ordered by how much structure they assume\. A disagreement is always resolved in favour of the solver that assumes less\.

Baseline A \(LP oracle\)\.For eachkkseparately, the cardinality\-constrained problem \([8](https://arxiv.org/html/2608.23910#A2.E8)\) is solved as a linear program over the cardinality\-kkmatching polytope𝒫k\\mathcal\{P\}\_\{k\}, using the full circular cost matrixd𝕊1​\(xi,yj\)d\_\{\\mathbb\{S\}^\{1\}\}\(x\_\{i\},y\_\{j\}\)\. It uses no cut, no cell and no chain, so it is independent of every structural result proved above\. Its extreme points are integral, and the returned vertex is checked to be a matching\.

Baseline B \(cut enumeration\)\.The exact cut envelope \([14](https://arxiv.org/html/2608.23910#A3.E14)\): cut at each of theNNoriginal support gaps, unwrap, run linePAWLonce per cut, and minimise over cuts for everykk\. This is theO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)reference solver of[Corollary2](https://arxiv.org/html/2608.23910#Thmcorollary2)\.

PAWC\(reference\)\.A transparent transcription of[Algorithm1](https://arxiv.org/html/2608.23910#alg1)that mirrors the proof structure and carries the invariant assertions of[SectionK\.3](https://arxiv.org/html/2608.23910#A11.SS3)\.

PAWC\.The optimised implementation, in two variants – one in plain array code and one just\-in\-time compiled\.

Instances are drawn from seven families chosen to stress different parts of the argument: uniform; clustered \(long free gaps and long chains\); near\-antipodal pairs, perturbed off the exact tie excluded by[Assumption2](https://arxiv.org/html/2608.23910#Thmassumption2); all atoms inside a short arc, where the circle should degenerate to the line; strongly unbalancedn≠mn\\neq m; near\-regular spacing, which produces many near\-equal candidate marginals; and strict source/target alternation around the circle\.

### K\.2Exactness

On504504random instances withn,m∈\[2,30\]n,m\\in\[2,30\]spanning all seven families, the cut envelope and the LP oracle agree at every cardinalityk=0,…,Kk=0,\\dots,Kto10−910^\{\-9\}, confirming[Propositions1](https://arxiv.org/html/2608.23910#Thmproposition1)and[2](https://arxiv.org/html/2608.23910#Thmcorollary2)numerically\. BothPAWCvariants reproduce these values on the same battery, and agree with the cut envelope on larger instances up toN=2000N=2000\.

Two checks guard against the agreement being an artefact of floating point\. First, the whole comparison is repeated in exact rational arithmetic: support points are taken as distinct multiples of1/d1/d, gap midpoints are then exactly rational, and the line profile under each cut is recomputed by anO⁡\(n​m​K\)O\(nmK\)dynamic program over non\-crossing matchings, which is exact because\|u−v\|\\lvert u\-v\\rvertsatisfies the Monge condition on the line\. Second, the two optimised variants are required to reproduce the reference implementation*bit for bit*– identicalfloat64cost arrays and identical activation orders, not merely costs within a tolerance\. This is a strong test: it fails under any reassociation of the floating\-point sums, and it is the reason the recursion \([36](https://arxiv.org/html/2608.23910#A7.E36)\) is evaluated sequentially rather than as a segmented cumulative sum \([Remark10](https://arxiv.org/html/2608.23910#Thmremark10)\)\.

A separate check confirms the premise of[Proposition1](https://arxiv.org/html/2608.23910#Thmproposition1): cuts placed at uniformly random positions on the circle never beat the minimum over theNNinter\-point gaps, and moving the cut within a gap leaves the unwrapped profile unchanged\.

### K\.3Structural invariants

Cost agreement alone is a weak test, because optima need not be unique: a solver can return the right number from a structurally wrong state\. The following are therefore asserted directly, at*every*induction stepkkof every instance\.

1. 1\.*Nestedness*\([Theorems6](https://arxiv.org/html/2608.23910#Thmtheorem6)and[3](https://arxiv.org/html/2608.23910#Thmcorollary3)\):Ak⊂Ak\+1A\_\{k\}\\subset A\_\{k\+1\}, and the increment consists of exactly one source atom and one target atom\.
2. 2\.*Cyclic\-neighbor addition*\([Theorem7](https://arxiv.org/html/2608.23910#Thmtheorem7)\): the two newly activated atoms are consecutive in the cyclic ordering of the inactive setAkcA\_\{k\}^\{c\}\.
3. 3\.*Balanced cell interiors*\([Lemma4](https://arxiv.org/html/2608.23910#Thmlemma4)\): the active atoms strictly inside each current cell contain equally many sources and targets\.
4. 4\.*Free\-gap invariant*\([Lemma5](https://arxiv.org/html/2608.23910#Thmlemma5)\): the current cells are recomputed from scratch, and every one of them is confirmed to contain a gap belonging to no previously selected cell\.
5. 5\.*Cut compatibility*\([Lemma6](https://arxiv.org/html/2608.23910#Thmlemma6)\), in a strengthened form: cutting at*any*free gap of*any*current cell reproducesCk∘C\_\{k\}^\{\\circ\}exactly, not merely bounds it\.
6. 6\.*Cost consistency*: the incrementally maintained cost is compared withW1,∘​\(Ak\)W\_\{1,\\circ\}\(A\_\{k\}\)recomputed from the circulation form \([12](https://arxiv.org/html/2608.23910#A3.E12)\) – a weighted median over gap lengths, which involves no cut, cell or chain and is therefore independent of how the algorithm arrived at its value\.
7. 7\.*Constant\-time marginal*\([Corollary5](https://arxiv.org/html/2608.23910#Thmcorollary5)\): the four\-lookup formula \([38](https://arxiv.org/html/2608.23910#A7.E38)\) is checked against[Definition3](https://arxiv.org/html/2608.23910#Thmdefinition3)evaluated by explicit sorted matching inside the cell\.

At the level of whole instances we further verify thatθ⋆\\theta^\{\\star\}realisesCk∘C\_\{k\}^\{\\circ\}as a line cost simultaneously for everykk\([Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9)\) and lies in a gap contained in no selected cell; thatk↦Ck∘k\\mapsto C\_\{k\}^\{\\circ\}is nondecreasing and convex; that recovered plans are feasible, with marginals at mostww, total massk​wkw, and cost equal to the reported cost when re\-evaluated withd𝕊1d\_\{\\mathbb\{S\}^\{1\}\}directly; that[Proposition3](https://arxiv.org/html/2608.23910#Thmproposition3)holds at noninteger transported mass; and that the whole profile is invariant under rotation of the circle, under reflection, and under exchangingμ\\muandν\\nu\. Rotation invariance is the sharpest of these in practice, since wrap\-around handling is where circular implementations characteristically fail\. Degenerate configurations are covered separately:k=0k=0;k=1k=1, whereC1∘C\_\{1\}^\{\\circ\}must equal the smallest geodesic distance over all pairs;n=1n=1orm=1m=1; and all atoms confined to a short arc, where the profile must coincide with a single linePAWLcall\.

### K\.4Complexity

[Figure5](https://arxiv.org/html/2608.23910#S6.F5)and[Table3](https://arxiv.org/html/2608.23910#A11.T3)report the cost of computing the*complete*profile, i\.e\. all cardinalitiesk=0,…,Kk=0,\\dots,K, forNNfrom10210^\{2\}to10610^\{6\}, with five repetitions per size and just\-in\-time compilation excluded by an explicit warm\-up\. Baseline B is measured toN=3⋅104N=3\\cdot 10^\{4\}and extrapolated beyond that along its theoreticalN2​log⁡NN^\{2\}\\log Nslope, the constant being fitted at the largest measured size\. Baseline A is measured toN=103N=10^\{3\}, beyond which one linear program per cardinality is no longer practical, and is extrapolated alongN3N^\{3\}\.

Table 3:Time to compute the complete partial\-transport profile for allkk, mean of five repetitions \(two for Baseline A atN≥600N\\geq 600\)\.†extrapolated alongN2​log⁡NN^\{2\}\\log N,‡alongN3N^\{3\}, in both cases with the constant fitted at the largest measured size; a dash marks sizes past which no extrapolation is attempted\. AtN=106N=10^\{6\}the compiled implementation returns every cardinality in0\.3650\.365s, against roughly six days for cut enumeration\. Baseline A already needs almost four minutes atN=103N=10^\{3\}, wherePAWCneeds1\.3⋅10−41\.3\\cdot 10^\{\-4\}s\.Fittinglog⁡\(time\)\\log\(\\text\{time\}\)againstlog⁡N\\log Ngives a slope of2\.002\.00over all sizes and2\.032\.03over the top decade for cut enumeration, matching itsO⁡\(N2​log⁡N\)O\(N^\{2\}\\log N\)cost\. Baseline A fits at3\.053\.05, matching the cubic cost of the task it performs: computing the whole profile by successive shortest augmenting paths takesΘ⁡\(N\)\\Theta\(N\)augmentations, each a shortest\-path computation costingO⁡\(N2\)O\(N^\{2\}\)on the dense bipartite graph with node potentials\([Ahuja et al\., 1993](https://arxiv.org/html/2608.23910#bib.bib1)\)\. A pureN3N^\{3\}law fitted at the largest measured size reproduces every measured point to within35%35\\%across a decade, which is why its curve is extrapolated on the same footing as Baseline B’s\. ForPAWCthe same fit gives1\.111\.11and1\.291\.29\(array code\), and1\.031\.03and1\.231\.23\(compiled\)\. The top\-decade values exceed what one might naively expect, and the discrepancy deserves comment rather than rounding\.

Three observations place it\. First,N​log⁡NN\\log Nitself does not have log\-log slope11on this range: over the top decade its slope is1\.0791\.079, so the relevant target is1\.081\.08and not1\.01\.0\. Second, restricted toN≤3⋅104N\\leq 3\\cdot 10^\{4\}, where the preprocessing tables, the heap and the linked list still fit in cache, the same code fits at0\.970\.97\(array\) and0\.910\.91\(compiled\); the excess appears only fromN≥105N\\geq 10^\{5\}upward, which is the signature of a memory\-hierarchy crossover rather than of an algorithmic term, since an unaccounted factor would inflate the slope uniformly\. Third, and most directly, the same measurement applied to linePAWL– an establishedO⁡\(N​log⁡N\)O\(N\\log N\)partial\-transport solver, compiled and unmodified – gives1\.1231\.123over all sizes and1\.2511\.251over the top decade on the same machine, soPAWCis in fact slightly flatter over the top decade than the line algorithm it extends\.

The machine\-independent form of[Theorem10](https://arxiv.org/html/2608.23910#Thmtheorem10)is cleaner to verify directly, and is: the heap performs0\.81​N0\.81Ndeletions and0\.31​N0\.31Ninsertions atN=104N=10^\{4\},10510^\{5\}and10610^\{6\}alike\. That is, the total number of entries ever created is linear, each is removed at most once whether valid or stale, and at most one new candidate is inserted per iteration, exactly as[Algorithm1](https://arxiv.org/html/2608.23910#alg1)prescribes\. Profiling atN=105N=10^\{5\}shows no stage growing faster than the others, and in particular no residual cost from candidate\-list cleaning, which lazy deletion removes entirely\.

### K\.5Is the simultaneous cut necessary?

[Example1](https://arxiv.org/html/2608.23910#Thmexample1)shows that a single cut chosen atk=Kk=Kcan be arbitrarily wrong atk=1k=1\. That is a worst case; this subsection measures the typical one\. Everything below is a reduction of the tableT⁡\[r\]​\[k\]=Ck,rlineT\[r\]\[k\]=C\_\{k,r\}^\{\\mathrm\{line\}\}that the cut envelope already computes, so no additional solver is involved, and all of it is computed in exact integer arithmetic: whether a cut is optimal is an equality test, and a tolerance would otherwise decide the answer\.

We compare four rules for choosing one cut and reusing it for everykk: the deterministicmin⁡ΘK\\min\\Theta\_\{K\}; the widest support gap; a uniformly random gap, whose expectation is evaluated exactly rather than sampled; and a warm start that fixes the cut atk0=K/2k\_\{0\}=K/2\.[Table4](https://arxiv.org/html/2608.23910#A11.T4)reports56005600instances,800800from each of the seven families of[SectionK\.1](https://arxiv.org/html/2608.23910#A11.SS1); failure rates are stable to1\.11\.1percentage points against an independent replication of the same size\.[Figure13](https://arxiv.org/html/2608.23910#A11.F13)breaks the deterministic rule down by family and places the adversarial family of[Example1](https://arxiv.org/html/2608.23910#Thmexample1)against its closed form\.

Table 4:One\-cut rules against the exact envelope,56005600exact instances\. A rule*fails*on an instance when its cut is strictly suboptimal at somekk; the excess columns aremaxk⁡εk\\max\_\{k\}\\varepsilon\_\{k\}over the instances where it does, withεk=\(Ck,rline−Ck∘\)/Ck∘\\varepsilon\_\{k\}=\(C\_\{k,r\}^\{\\mathrm\{line\}\}\-C\_\{k\}^\{\\circ\}\)/C\_\{k\}^\{\\circ\}\. Every cut is a valid upper bound \([Corollary2](https://arxiv.org/html/2608.23910#Thmcorollary2)\); only looseness is at issue\.0%10%20%30%12%clust32%inter22%antip10%grid8%arc0%unbal10%unifinstances wheremin⁡RK\\min R\_\{K\}is suboptimal\(a\) failure of the deterministic one\-cut rule10−710^\{\-7\}10−610^\{\-6\}10−510^\{\-5\}10−410^\{\-4\}10−310^\{\-3\}10−210^\{\-2\}10−110^\{\-1\}10010^\{0\}10210^\{2\}10410^\{4\}10610^\{6\}\(b\) adversarial family:ε1\\varepsilon\_\{1\}againstδ/L\\delta/Lδ/L\\delta/L\(decreasing\)ε1\\varepsilon\_\{1\}at thek=Kk=K\-optimal cutgrey: closed form\(d2−δ\)/δ\(d\_\{2\}\-\\delta\)/\\deltaorange: measured, exactFigure 13:\(a\) Failure rate of the deterministic rulemin⁡ΘK\\min\\Theta\_\{K\}by instance family,800800instances each\. \(b\) The family of[Example1](https://arxiv.org/html/2608.23910#Thmexample1): measured relative excess atk=1k=1of a cut that is exactly optimal atk=Kk=K, against the closed form \([28](https://arxiv.org/html/2608.23910#A6.E28)\), in exact arithmetic over six decades ofδ\\delta\.Three things are worth stating plainly, including the one that cuts against the result we set out to find\.

*The deterministic rule usually works\.*It is optimal at everykkon86\.5%86\.5\\%of instances\. A reader who expects one\-cut heuristics to fail routinely on random data is wrong, and we do not claim otherwise\. What it lacks is a certificate: on the13\.5%13\.5\\%where it fails there is nothing local distinguishing them, and the excess reaches three orders of magnitude\. Its failure rate is also uneven –0\.1%0\.1\\%on strongly unbalanced instances,31\.5%31\.5\\%on strictly alternating ones – so it cannot be excused as a boundary effect\. Two further caveats sharpen the comparison rather than soften it\. First, obtainingΘK\\Theta\_\{K\}is only cheap whenn=mn=m, where thek=Kk=Kproblem is balanced and its cut is a weighted median of \([12](https://arxiv.org/html/2608.23910#A3.E12)\); whenn≠mn\\neq mthe full\-mass problem is itself partial, so the rule presupposes the machinery it claims to avoid\. Restricted ton=mn=m, where it is genuinely cheap, its failure rate rises to27\.3%27\.3\\%\. Second, the choice withinΘK\\Theta\_\{K\}matters:min⁡ΘK\\min\\Theta\_\{K\}is one of several optimal cuts atk=Kk=K, and a different element of that same set fails on46\.5%46\.5\\%of instances\.

*A simultaneously optimal cut is common, not rare\.*The setΘ∩\\Theta\_\{\\cap\}of gaps optimal at everykkhas median size between0\.17​N0\.17Nand0\.92​N0\.92Ndepending on the family\.[Theorem9](https://arxiv.org/html/2608.23910#Thmtheorem9)therefore does not locate a needle in a haystack on random data, and we should not claim it does\. Its content is that such a gap exists*always*and is produced constructively, not that it is hard to stumble on\. Correspondingly, a uniformly random element ofΘK\\Theta\_\{K\}is simultaneously optimal with median probability11, but with probability as low as0\.140\.14on the worst instance encountered – which is the same point as before in another form: the typical case is benign and carries no guarantee\.

*The optimal cut does move withkk\.*Trackingmin⁡Rk\\min R\_\{k\}askkgrows, the index changes on a majority of instances in every family except the strongly unbalanced one\. This is the concrete form of the claim in[Section1](https://arxiv.org/html/2608.23910#S1)that the optimal circulation varies with transported mass, and it is why a warm start degrades ask0k\_\{0\}moves away from the cardinality of interest: fixing the cut atk0=K/2k\_\{0\}=K/2already fails on38\.9%38\.9\\%of instances\.

### K\.6The spherical construction

[AppendixJ](https://arxiv.org/html/2608.23910#A10)is a construction; this subsection is the evidence for it\. Two things are measured: that the implementation reproduces an independent published one at the single point where the two theories must coincide, and how the Monte\-Carlo estimator \([52](https://arxiv.org/html/2608.23910#A10.E52)\) actually behaves against[Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4)\.

##### Reduction to the balanced case\.

[Remark6](https://arxiv.org/html/2608.23910#Thmremark6)\(4\) states that atn=mn=mands=n​ws=nwevery slice problem is balanced andSSPW⁡\(n​w,μ,ν\)=n​w​SSW1​\(μ/n​w,ν/n​w\)\\mathrm\{SSPW\}\(nw;\\mu,\\nu\)=nw\\,\\mathrm\{SSW\}\_\{1\}\(\\mu/nw,\\nu/nw\)\. This is the only quantity in[AppendixJ](https://arxiv.org/html/2608.23910#A10)with an external reference, and reproducing it exercises the whole pipeline: Stiefel sampling, geodesic projection, the circular coordinate \([46](https://arxiv.org/html/2608.23910#A10.E46)\),[Algorithm1](https://arxiv.org/html/2608.23910#alg1), and the slice average\. We compare against the implementation shipped with POT\([Flamary et al\., 2021](https://arxiv.org/html/2608.23910#bib.bib13)\), which follows[Bonet et al\. \(2023\)](https://arxiv.org/html/2608.23910#bib.bib8)\.

The comparison uses*the same slices*on both sides\. Letting each implementation draw its own would compare two Monte\-Carlo estimates, and agreement would then only be required in distribution – a weak test that a systematic bias of the size of the Monte\-Carlo noise would pass\. With shared slices both sides evaluate the same finite average of the same integrand, so agreement is required to solver tolerance\.[Table5](https://arxiv.org/html/2608.23910#A11.T5)reports five checks, each isolating what the next would aggregate away\.

Table 5:Maximum relative discrepancy of the reduction cross\-check, overd∈\{3,5,10,50\}d\\in\\\{3,5,10,50\\\},n=m∈\{10,50,200\}n=m\\in\\\{10,50,200\\\}and both instance families, with slices shared between implementations\. Check \(e\) additionally has zero slice\-to\-slice variance \(6\.7⋅10−166\.7\\cdot 10^\{\-16\}\), as it must, since atd=2d=2the projection is an isometry and every slice returns the same value\.Checks \(b\) and \(c\) sit near10−910^\{\-9\}rather than near10−1510^\{\-15\}, and the cause is worth recording because it is not on our side\. POT’s circular solver dispatches to a binary search for everypp– it provides no exactp=1p=1circular routine – and that search terminates at a tolerance of10−610^\{\-6\}, so10−810^\{\-8\}is its own accuracy floor\. On the worst slice of check \(b\) our value agrees with an LP over the geodesic cost matrix*exactly*, to the last bit, while POT differs from that LP by7\.5⋅10−97\.5\\cdot 10^\{\-9\}\. The acceptance criterion is therefore split: exact against the LP oracle, POT’s own tolerance against POT\. Requiring10−1010^\{\-10\}of POT would be requiring it to be more accurate than it is\.

##### Concentration\.

[Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4)is next\. We take a reference atMref=105M\_\{\\mathrm\{ref\}\}=10^\{5\}slices as ground truth, drawn from a slice stream*disjoint*from the estimates under test – if the estimate’s slices were a subset of the reference’s, deviations would be biased downward and the convergence would flatter itself – and use200200repetitions at eachM∈\{23,…,212\}M\\in\\\{2^\{3\},\\dots,2^\{12\}\\\}, overd∈\{3,10,50\}d\\in\\\{3,10,50\\\}, three families and bothn=mn=mandn≠mn\\neq m\.

Three checks pass and are reported without further comment: the estimator converges at the rate the bound implies, with fitted slope−0\.497\-0\.497across the eighteen configurations and none outside\[−0\.519,−0\.476\]\[\-0\.519,\-0\.476\]; the bound of \([53](https://arxiv.org/html/2608.23910#A10.E53)\) is never violated, on any of the540540configuration and threshold combinations tested; and the piecewise linearity inssthat the proof of \([54](https://arxiv.org/html/2608.23910#A10.E54)\) relies on holds exactly, the deviation on a finess\-grid never exceeding its value at the breakpoints\. That last one is a step of the proof rather than an implementation detail, which is why it is checked directly\.

What the measurements add is a quantitative account of where[Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4)is loose, and there are two distinct answers\.

10−310^\{\-3\}10−210^\{\-2\}10−110^\{\-1\}10010^\{0\}0\.000\.250\.500\.751\.00theπ​s\\pi sceilingd=3d=3d=10d=10d=50d=50\(a\) effective range/π​s/\\ \\pi sk/Kk/K035070010501400175021000\.000\.250\.500\.751\.00\(b\)log10\\log\_\{10\}\(uniform term / pointwise bound\)k/Kk/Kidentical ford=3,10,50d=3,10,50Figure 14:\(a\) The effective Hoeffding rangemaxℓ⁡Zℓ−minℓ⁡Zℓ\\max\_\{\\ell\}Z\_\{\\ell\}\-\\min\_\{\\ell\}Z\_\{\\ell\}as a fraction of the ceilingπ​s\\pi sused in[Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4), against transported cardinality; median over families,Mref=105M\_\{\\mathrm\{ref\}\}=10^\{5\}\. The ceiling is never approached, and the gap widens asssshrinks\. \(b\) The ratio of the per\-breakpoint term of the uniform bound \([54](https://arxiv.org/html/2608.23910#A10.E54)\), which uses the rangeπ​K​w\\pi Kw, to the pointwise bound \([53](https://arxiv.org/html/2608.23910#A10.E53)\) at the samess, which usesπ​s\\pi s;ε=0\.05​K​w\\varepsilon=0\.05\\,Kw,M=212M=2^\{12\}\. The two coincide ats=K​ws=Kwand diverge without limit ass→0s\\to 0\.First, the range\. The bound uses0≤Zℓ≤π​s0\\leq Z\_\{\\ell\}\\leq\\pi s, attained only when every transported pair is antipodal\. Measured, the effective rangemaxℓ⁡Zℓ−minℓ⁡Zℓ\\max\_\{\\ell\}Z\_\{\\ell\}\-\\min\_\{\\ell\}Z\_\{\\ell\}– which is what Hoeffding’s inequality actually depends on – is between0\.3%0\.3\\%and15%15\\%ofπ​s\\pi s\([Figure14](https://arxiv.org/html/2608.23910#A11.F14)\(a\)\), and the ceiling itself is never approached:maxℓ⁡Zℓ\\max\_\{\\ell\}Z\_\{\\ell\}stays below0\.29​π​s0\.29\\,\\pi sthroughout\. The looseness is worst at smallss\. It also*grows*with dimension rather than shrinking – the median effective range is0\.00670\.0067,0\.00910\.0091and0\.01000\.0100ofπ​s\\pi satd=3,10,50d=3,10,50– so the slack is not explained by the projected measures approaching uniformity on the circle asddgrows, which would have been the natural guess\. Whatever a dimension\-dependent refinement of[Remark7](https://arxiv.org/html/2608.23910#Thmremark7)would exploit, it is not that\.

Second, and separately, the uniform bound \([54](https://arxiv.org/html/2608.23910#A10.E54)\) is obtained by relaxing the range at every breakpoint fromπ​k​w\\pi kwtoπ​K​w\\pi Kwbefore taking the union bound\. For controlling the supremum this costs little, since thek=Kk=Kterm dominates the sum regardless\. But it makes \([54](https://arxiv.org/html/2608.23910#A10.E54)\) a poor guarantee*at*a smallss: its per\-breakpoint term ats=k​ws=kwexceeds the pointwise bound \([53](https://arxiv.org/html/2608.23910#A10.E53)\) there by a factor whose logarithm grows likeK2/k2K^\{2\}/k^\{2\}, reaching1036110^\{361\}atk/K=0\.05k/K=0\.05for the configuration of[Figure14](https://arxiv.org/html/2608.23910#A11.F14)\(b\), and identically so at everyddtested\. The practical reading is that \([54](https://arxiv.org/html/2608.23910#A10.E54)\) should be used for what it is – a statement about the whole profile – and \([53](https://arxiv.org/html/2608.23910#A10.E53)\) used when accuracy is wanted at a particular transported mass\.[Remark9](https://arxiv.org/html/2608.23910#Thmremark9)records the natural way to have both at once\.

Finally, the slice count\.[Proposition4](https://arxiv.org/html/2608.23910#Thmproposition4)demandsM≥\(π2​K2​w2/2​ε2\)​log⁡\(2​\(K\+1\)/δ\)M\\geq\(\\pi^\{2\}K^\{2\}w^\{2\}/2\\varepsilon^\{2\}\)\\log\(2\(K\+1\)/\\delta\); the smallest testedMMat which no repetition out of200200exceededε\\varepsilonis smaller than that by a median factor of470470, and the empirical figure is itself conservative, being an observed tail of0/2000/200rather than ofδ\\delta\. Two orders of magnitude is the usual price of a distribution\-free bound, and it is stated here so that a reader sizing a computation uses the measurement rather than the proposition\.

## Appendix LApplication detail and what did not work

### L\.1Shape matching: protocol

Contours are traced at the0\.50\.5level of eachmpeg\-7mask, resampled to128128points uniformly in arclength, and converted to outward normal angles by a centred difference over five samples\. Pixel quantisation makes long straight runs share a tangent*exactly*, which violates[Assumption2](https://arxiv.org/html/2608.23910#Thmassumption2); a deterministic jitter of10−710^\{\-7\}circle units \(seeded by a checksum of the file name, so it is reproducible\) separates them\. That is1\.3×10−41\.3\\times 10^\{\-4\}degrees, four orders of magnitude below the coarsest quantisation step and far below any cost difference these tasks resolve — it is the symbolic perturbation of[Section7](https://arxiv.org/html/2608.23910#S7)made concrete\.

A query keeps a contiguous fractionvvof the arclength starting at a uniformly random sample, replaces a fractionccof the survivors by normals drawn uniformly on the circle, and is rotated by a uniformly random angle\. Every method scores the same grid of360360rotations\. For retrieval, the database holds the intact signatures of all14001400shapes and the query’s own entry is excluded; the bullseye score counts how many of the2020shapes of the query’s class appear in the top4040\. For correspondences the plan is read at the rotation that minimises the cost atρ=0\.8\\rho=0\.8, and a pair is correct if it matches the arclength index the query sample was built from; clutter samples have no correct partner, so asserting one is an error\.

The correlation baseline is the classical extended\-Gaussian\-image matcher: a von Mises kernel density on each measure, cross\-correlated over rotations by FFT, at bandwidths0\.010\.01,0\.020\.02and0\.040\.04circle units, reported at its best bandwidth per cell\. The nearest\-neighbour baseline for correspondences is mutual nearest neighbour in normal angle after alignment\.

### L\.2Why not unbalanced transport, and is this the same optimum?

Two checks on one shape per class over the same twelve cells \(864864queries\)\. First, a KL\-relaxed unbalanced Sinkhorn cost\([Peyré and Cuturi, 2019](https://arxiv.org/html/2608.23910#bib.bib6)\)replaces the partial one, at marginal weightsτ∈\{0\.01,0\.05,0\.2\}\\tau\\in\\\{0\.01,0\.05,0\.2\\\}and entropic regularisation10−210^\{\-2\}, reported at its bestτ\\tauper cell\. It matchesPAWCwhile the query is nearly complete and falls behind as the boundary disappears —0\.710\.71against0\.850\.85success atv=0\.35v=0\.35,c=0\.4c=0\.4— and no singleτ\\tauis competitive across cells: theτ\\tauthat is best at full visibility scores0\.610\.61there andτ=0\.2\\tau=0\.2scores0\.440\.44\. The relaxation weight is a parameter to tune;ρ=1−c\\rho=1\-cis a rule\. The rotation sweep also costs0\.580\.58s per query perτ\\tauagainst0\.0290\.029s for all360360PAWCsolves\.

Second, on a sample of rotations from every query we comparedPAWC’s profile value against POT’spartial\_wasserstein2at the same cardinality with unit atom weights — the same problem, not a proportional one\. The largest absolute difference over the864864queries is4\.3×10−144\.3\\times 10^\{\-14\}\. The applications therefore read exactly the optimum a general partial solver reports,1313times faster atn=128n=128and27002700times faster byn=2048n=2048\.

### L\.3Spherical fitting: gradients and protocol

For one sliceUUandp=U⊤​xp=U^\{\\top\}x, the circle coordinate isθU​\(x\)=atan2⁡\(p2,p1\)\\theta\_\{U\}\(x\)=\\operatorname\{atan2\}\(p\_\{2\},p\_\{1\}\)with∂θ/∂x=U​\(−p2,p1\)⊤/‖p‖2\\partial\\theta/\\partial x=U\(\-p\_\{2\},p\_\{1\}\)^\{\\top\}/\\\|p\\\|^\{2\}; the matched geodesic distances contribute±1\\pm 1through∂/∂θ\\partial/\\partial\\theta\. The matching found byPAWCis held fixed while differentiating \(the envelope theorem\), the gradient is projected onto the tangent space at each particle and the step retracted by renormalising\. Analytic gradients agree with central differences to3×10−63\\times 10^\{\-6\}relative\.

Training uses500500particles from a uniform start,3232slices redrawn every step,20002000Adam steps with a cosine schedule from8×10−28\\times 10^\{\-2\}to4×10−34\\times 10^\{\-3\}, and target batches of sizeγ⋅500\\gamma\\cdot 500\. The synthetic target has five von Mises–Fisher components with masses0\.28,0\.22,0\.18,0\.20,0\.120\.28,0\.22,0\.18,0\.20,0\.12and concentrationsκ=80,200,60,120,150\\kappa=80,200,60,120,150\. The catalogue is split80/2080/20once, with a fixed permutation seed; the model never sees the evaluation fifth\. Real catalogues round their coordinates, so a target batch can contain exact duplicates: the tie\-break perturbation has magnitude in\[10−9,2×10−9\)\[10^\{\-9\},2\\times 10^\{\-9\}\)with random sign, bounded away from zero because a Gaussian jitter of that size falls below one ulp often enough to leave ties in place over10810^\{8\}draws\.