Exact Sector Clustering of Circular Histograms via Cut Interleaving

Many quantities in machine learning and vision are angles: gradient orientations inside a SIFT descriptor, the hue of a pixel, wind direction, the longitude of an earthquake. A common step is to split a circular histogram of such values into $k$ contiguous angular sectors, for example to build a hue palette, pick dominant orientations, or quantize directions. On a line this problem has an exact, efficient solution. Optimal clusters are contiguous intervals, so dynamic programming over sorted bins finds the global optimum. On a circle there is no natural place to start: the best sector may straddle $0/2\pi$. The obvious fix is to try every possible cut and solve each resulting line problem, which multiplies the cost by the number of bins $N$.

This note proposes to remove most of that overhead with a structural fact borrowed from circular optimal transport. Under a quadrangle-type inequality on the interval cost, optimal partitions computed from different cuts do not cross each other. In particular, the optimal circular partition interleaves with the optimal linear partition obtained from any arbitrary cut. The cut search can then be restricted to the smallest cluster of a single linear solution and organized as divide-and-conquer. The result would be an exact circular Bregman sector-clustering algorithm, with a robust variant that tolerates outliers. It would replace brute-force search over $N$ cuts and also replace the local-optimum-prone Lloyd/EM methods practitioners use today.

Core Claim

Let a circular histogram have bins $1,\dots,N$ with masses $w_i$. Let $c(a,b)$ be the cost of making the arc of bins $a..b$ (indices taken modulo $N$) into one cluster: its weighted Bregman divergence to the arc's centroid. Prefix sums give $c$ in $O(1)$, exactly as in the linear case. The claim has two parts.

The first part concerns the cost. We say $c$ satisfies the quadrangle inequality when

$$c(a,d) + c(b,e) \ \ge\ c(a,e) + c(b,d) \quad \text{for all arcs with } a \le b \le d \le e,$$

which states that splitting overlapping arcs is never worse than nesting them. When this holds, the optimal $k$-partitions of the line starting at cut $i$ and at cut $j$ can be chosen so that their boundaries interleave. This is the same uncrossing argument that underlies "no leapfrogging" for mobile sensors and the stationary-cut lemma for circular transport.

The second part concerns the consequence. One linear solve from an arbitrary cut has a smallest cluster of at most $N/k$ bins, and some optimal circular boundary must fall inside it. Divide-and-conquer over candidate cuts, in which each child problem's boundaries are confined between those of its neighbours, then brings the exact solution from the brute-force $O(N^3 k)$ down to roughly $O(N^2 k \log N)$.

We aim to prove both parts for squared-Euclidean arc length and for the Bregman family, and to identify exactly where they fail.

One observation makes the circle more natural than it first looks. Optimal Interval Clustering shows that 1D DP is exact for mixture learning only when component densities cross at most once; unequal-variance Gaussians break this. On the circle, two distinct densities with equal total mass must cross at least twice, and two crossings delimit an arc. The circular counterpart of the "one-intersection rule" is therefore a "two-intersection rule." We conjecture it holds for von Mises components of unequal concentration in cases where the linear analogue fails, which would give a regime where circular DP is exact and linear DP is not.

Relation to Prior Work

The method comes from circular transport. Transportation Distances on the Circle proves that an optimal circular plan leaves some point uncrossed, so cutting there reduces the problem to the line. Circular Earth Mover's Distance turns this into a median-offset $O(N)$ formula. Fast Transport Optimization for Monge Costs on the Circle uses the quadrangle inequality to prove that cost is convex in the shift. All three compare two histograms; none segments a single histogram. We reuse their uncrossing logic on a partition objective instead of a transport plan.

The order-preservation results play the same role on the line. Barrier coverage of a linear domain and aggregate interval coverage show that uncrossing trajectories lets binary search replace permutation search. These results are linear and concern point movement; we transfer the uncrossing idea to cluster boundaries indexed by a cut. Dispersing points on intervals handles cycles by duplicating the domain, but it works with point placements rather than density partitions.

The DP itself comes from Optimal Interval Clustering: exact $O(n^2k)$ Bregman interval clustering via prefix-sum tables, on a bounded line only. Our outlier variant builds on Partial K-Means with M Outliers, which solves 1D partial $k$-means in $O(KN^2(1+M))$. That paper also warns that intuitive outlier structure breaks under weights, which constrains us: on the circle, outliers can sit between any two sectors, so we will treat only unit-weight samples exactly.

LCOT is the closest bridge between the two directions. It embeds whole circular distributions into a flat space so that many distributions can be clustered with $k$-means. It does not partition the mass within one distribution, which is our problem. Optimal quantization of circular distributions does address the single-distribution problem, but only for parametric densities and by gradient descent, with no global guarantee.

Research Program

The theory phase proves interleaving across cuts for convex-in-arc-length costs and for weighted Bregman centroids. It characterizes the failure cases, which we expect when clusters wrap more than half the circle and arc length stops being a faithful proxy for geodesic distance. It also tests the two-intersection conjecture for von Mises mixtures. The algorithm phase implements three solvers: a brute-force all-cuts DP used as a correctness oracle, the smallest-cluster restriction, and the divide-and-conquer solver. It then adds an $M$-outlier version that allows skipped bins between sectors. The empirical phase checks exactness against the oracle, measures runtime scaling, and tests whether exact sectors matter downstream.

Baselines

The naive reference is a single arbitrary cut. Cut the circle at bin 1 and run the linear DP of Optimal Interval Clustering. This is what a practitioner gets by ignoring periodicity, and it is also what stereographic or unrolled pipelines in the style of S3W effectively do. We report the relative excess cost of this solution over the exact optimum, averaged over random rotations of each histogram. Beating it means a strictly lower cost on the instances where the best sector wraps the cut.

The exactness oracle and main runtime competitor is brute-force all-cuts DP. It is exact by construction, so the comparison is purely about time. We run it with identical prefix-sum code, in the same language, on the same machine. Beating it means identical objective values on every instance, together with measured wall-clock speedups that grow with $N$ and $k$ in line with the predicted factor of $N/\log N$.

The strongest heuristic competitors are circular Lloyd $k$-means and von Mises mixture EM, both given $R$ random restarts with $R$ chosen so their total runtime matches our solver. The quantizer of Optimal quantization of circular distributions is run on the same targets. That paper reports optimization times of 0.2 to 5.3 seconds for 10 to 30 points. It reports no quantization-error figure, and we found no reported result on Lacuna for circular sector clustering quality. Beating these competitors means lower objective at equal time and zero variance across restarts.

The ablation isolates the key ingredient. We run divide-and-conquer with interleaving constraints switched off but keep the smallest-cluster restriction. This separates the speedup due to the pigeonhole bound from the speedup due to non-crossing.

Why not just…?

Why not just try every cut? It is exact and simple, and we use it as the oracle. Its cost is $O(N^3k)$, though. That is tolerable for an 8-bin SIFT orientation histogram but not for 360-bin hue or 3600-bin longitude histograms clustered across thousands of images. The runtime curves will show where it stops being practical. If $N$ is always tiny in an application, we will say so: for that application our method offers nothing.

Why not just run circular k-means or von Mises EM? These methods are fast but local. Optimal Interval Clustering reports that EM ends in worse optima than DP on the Lena histogram. Von Mises-Fisher Clustering Models shows that geometry-appropriate models beat flat ones, with NMI 0.900 versus 0.842 for $k$-means on TDT4. That result is high-dimensional, so we cite it only as motivation. Our time-matched restart comparison measures how often restarts actually miss the optimum. If they almost never do on real histograms, the contribution narrows to the guarantee and the outlier variant.

Why not just duplicate the array and run linear DP on length $2N$? Duplication works for convolution alignment, as in Necklaces, Convolutions, and X+Y. For partitioning, however, a DP over $2N$ bins does not by itself force exactly one cover of the circumference. Adding that constraint brings back a per-start search, which is brute force again. We include a duplicated-DP variant with start-tracking and expect it to equal brute force in cost.

Why not just project to the line, as S3W does? Projection picks a cut implicitly and distorts distances near the pole (Stereographic Spherical Sliced Wasserstein Distances). The single-cut baseline above measures exactly this loss.

Proposed Experiments

The first set uses synthetic von Mises and wrapped normal mixtures with varied concentrations, as in LCOT. On these we check exactness against the oracle, measure runtime against $N$ and $k$, and test the two-intersection conjecture by comparing optimal circular DP sectors with the Bayes-optimal mixture assignment.

The second set uses real circular histograms. These are gradient-orientation histograms extracted from the affine SIFT database of Circular Earth Mover's Distance, hue histograms of the paintings used in Fast Transport Optimization, and longitude histograms of the earthquake, flood, and wildfire data used by Spherical Sliced-Wasserstein.

A robustness test injects uniform background contamination and compares the $M$-outlier solver with plain DP.

The decisive checks are these. First, the fast solver must match the oracle on every instance. Second, the single-cut baseline must show nonzero excess cost on a substantial fraction of real histograms; if wrap-around optima are rare in practice, the problem is less important than claimed. Third, the measured speedup must scale as predicted.