Polynomial-Time Riesz-Energy Subset Selection for Ordered Point Sets on Lines and $\ell_1$-Staircases
2026-06-15 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study a problem where you pick a fixed number of points from a list to minimize a special energy related to distances raised to a negative power. They prove a key property (called Monge) for these distances that helps turn the problem into one solvable by known mathematical tools (submodular minimization). Using this, they create an efficient algorithm based on graph cuts (minimum cut) to find the best subset, with clear complexity bounds. Their approach also applies to selecting diverse points in two-dimensional data, like picking good representatives in competing choices. They provide open-source code to help others use their method.
Riesz energyMonge propertysubmodular minimizationdistributive latticeminimum cutmax-flowcomplexitysubset selectionPareto frontskyline approximation
Authors
Michael T. M. Emmerich
Abstract
We study the one-dimensional fixed-cardinality minimum Riesz $s$-energy subset problem with fixed exponent $s > 0$: given ordered real points $x_1 < x_2 < \cdots < x_n$, a positive parameter $s>0$, and a cardinality $k$, choose indices $1 \leq i_1 < \cdots < i_k \leq n$ minimizing $E_s(i_1,\ldots,i_k)=\sum_{1\leq p<q\leq k}(x_{i_q}-x_{i_p})^{-s}$. The paper proves a Monge property for the one-dimensional Riesz interaction. Encoding feasible subsets by increasing index vectors, this Monge inequality implies submodularity on a finite distributive lattice and gives polynomial-time solvability via submodular minimization over distributive lattices. The structural construction is valid for every real $s>0$; bit-complexity claims require the arithmetic assumptions stated in the complexity section. The same structure also yields an explicit minimum $S$--$T$ cut algorithm with $k(n-k)$ threshold variables and $O(k^2(n-k)^2)$ finite pairwise edges. The resulting graph has $N=k(n-k)$ nodes and $M=O(k^2(n-k)^2)$ arcs after an $O(k^2(n-k)^2)$ coefficient-construction step; an $O(NM)$ max-flow bound gives an $O(k^3(n-k)^3)$ min-cut step, while the conservative $O(N^2M)$ bound gives $O(k^4(n-k)^4)$. Due to isometry, the results apply directly to subset selection on $\ell_1$ staircases, such as choosing diverse and representative Pareto front or skyline approximations in two dimensions. An open-source Python implementation of the min-cut algorithm accompanies the reproducibility material.