Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming
Michael T.M. Emmerich · 2025
Read Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming by Michael T.M. Emmerich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-01163.txt.
Introduction
Michael Emmerich presents a method for picking a small, well-spread subset from an ordered set of points, in a 2025 paper. The goal is to keep the total Riesz energy, a measure of how crowded the points are, near its lowest value. In general the task is hard, but order in one dimension opens a shortcut.
His step-by-step method builds the subset in stages and works fast for large sets. He extends it to two-goal trade-off fronts used in design choices. The method usually lands near the best answer and avoids traps that catch greedy picking, though rare cases miss the true optimum because the recurrence is approximate. Code in Python is shared, with tests on broken fronts and large point sets.
Catalog record
| CREATOR | Michael T.M. Emmerich |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-01163
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming Michael T.M. Emmerich Abstract We present a dynamic programming algorithm for selecting a representative subset of size k k from a given set with n n points such that the Riesz s s -energy is near minimized. While NP-hard in general dimensions, the one-dimensional case can use the natural data ordering for efficient dynamic programming as an effective heuristic solution approach. This approach is then extended to problems related to two-dimensional Pareto front representations arising in biobjective optimization problems. Under the assumption of sorted (or non-dominated) input, the method typically yields near-optimal solutions in most cases. We also show that the approach avoids mistakes of greedy subset-selection by means of example. However, as we demonstrate, there are exceptions where DP does not identify the global minimum; for example, in one of our examples, the DP solution slightly deviates from the configuration found by a brute-force search.This is because the DP scheme’s recurrence is approximate. The total time complexity of our algorithm is shown to be O ( n 2 k ) O(n^{2}k) . We provide computational examples with discontinuous Pareto fronts and an open-source Python implementation, demonstrating the approximate DP algorithm’s effectiveness across various problems with large point sets. Keywords: Dynamic Programming, Subset Selection, Riesz s s -Energy, Pareto Front, Biobjective Optimization, Multiobjective Optimization, Diversity Measures. 1 Introduction Often it is desirable to select a representative subset of points from a larger set such that the points are as evenly spread as possible. A common measure to quantify this evenness is the Riesz s -energy [ 7 , 6 ] . For a set S of k points, the Riesz s -energy is defined as E(S)=\sum_{1\leq p<q\leq k}\frac{1}{d(P_{p},P_{q})^{s}}, where d(P_{p},P_{q}) denotes the distance between the points P_{p} and P_{q} and s>0 is a parameter. In this paper we describe a dynamic programming (DP) approach to select a subset that (nearly) minimizes the Riesz s -energy. We begin with the one-dimensional (1D) case (points on the real line) and then extend the technique to two-dimensional (2D) Pareto fronts in the context of biobjective optimization. It is worth noting that while the general problem is NP-hard [ 9 ] , in the 1D case (or for suitably ordered 2D Pareto fronts) the structure of the data permits an efficient DP formulation. Moreover, our approach is motivated by promising results in related problems such as the maximum subset selection of the hypervolume indicator for non-dominated points in 2D [ 1 ] . Although the DP strategy yields optimal or near-optimal solutions in most cases, as we illustrate later, there exist exceptions where the DP solution deviates from the globally best configuration as determined by an exhaustive brute-force search. The remainder of the paper is organized as follows. Section 2 presents the dynamic programming formulation and its proof of correctness for the one-dimensional case. Section 3 extends the approach to two-dimensional Pareto fronts, followed by detailed examples and computational analyses. Finally, Section 4 concludes with a summary of our contributions and a discussion of potential future work. 2 Dynamic Programming for Subset Selection in 1D Dynamic programming (DP) is an optimization method that decomposes a complex problem into simpler, overlapping subproblems, solves each subproblem once, and stores the solutions for future use. This method is particularly effective for problems that exhibit optimal substructure —that is, an optimal solution to the problem can be constructed from (near) optimal solutions to its subproblems—and overlapping subproblems , where the same subproblems are solved repeatedly. In the context of our subset selection problem, the property that the best selection of r points ending at a given point can be built upon a (near) optimal selection of r-1 points ending at an earlier point is key. This inherent structure allows us to design a DP scheme that efficiently (and in most cases optimally) minimizes the Riesz s -energy. For further details on the fundamentals of dynamic programming, see [ 2 ] . 2.1 Problem Statement Let x_{1}<x_{2}<\cdots<x_{n} be a sorted set of points in \mathbb{R} . For a given integer k ( 1\leq k<n ) and a parameter s>0 , our goal is to choose a subset S=\{x_{i_{1}},x_{i_{2}},\dots,x_{i_{k}}\},\quad\text{with }i_{1}<i_{2}<\cdots<i_{k}, that (nearly) minimizes E(S)=\sum_{1\leq p<q\leq k}\frac{1}{\left(x_{i_{q}}-x_{i_{p}}\right)^{s}}. Because the energy increases sharply when points are close (due to the term 1/(x_{i_{q}}-x_{i_{p}})^{s} ), the objective is to select k points that are as spread out as possible. 2.2 Dynamic Programming Algorithm We define the DP state as DP(i,r)=\text{(near) minimum energy achievable by selecting $r$ points from }\{x_{1},\dots,x_{i}\}\text{ with }x_{i}\text{ as the last point.} Base Case: For r=1 , there are no pairs of points, hence DP(i,1)=0\quad\text{for }i=1,\dots,n. Recurrence: For r\geq 2 and i\geq r , assume that a (near) optimal (r-1) -subset ending at x_{p} (with p<i ) is known. When adding x_{i} as the r th point, the additional cost is \Delta(p,i)=\sum_{x\in S(p,r-1)}\frac{1}{(x_{i}-x)^{s}}, where S(p,r-1) denotes the subset corresponding to DP(p,r-1) . Hence, the recurrence is given approximatly by DP(i,r)\approx\min_{1\leq p<i}\left\{DP(p,r-1)+\Delta(p,i)\right\}. Pseudocode Algorithm 1 DP Subset Selection for Minimizing Riesz s -Energy in 1D 1: Sorted points x_{1},\dots,x_{n} , integer k , parameter s>0 . 2: for i=1 to n do 3: DP(i,1)\leftarrow 0 4: S(i,1)\leftarrow\{x_{i}\} \triangleright Record the subset for reconstruction. 5: for r=2 to k do 6: for i=r to n do 7: DP(i,r)\leftarrow+\infty 8: for p=r-1 to i-1 do 9: Compute \Delta(p,i)\leftarrow\sum_{x\in S(p,r-1)}\frac{1}{(x_{i}-x)^{s}} 10: if DP(p,r-1)+\Delta(p,i)<DP(i,r) then 11: DP(i,r)\leftarrow DP(p,r-1)+\Delta(p,i) 12: S(i,r)\leftarrow S(p,r-1)\cup\{x_{i}\} 13: return \min_{i=k,\dots,n}DP(i,k) and the corresponding subset. 2.3 Discussion on (Near) Optimality While the recurrence and the DP formulation would ideally guarantee that the selected subset is optimal with respect to the locally computed subproblems, the non-local interactions inherent in the Riesz s -energy may result in situations where the overall subset is only near optimal. In most cases, the DP approach yields the optimal subset, but there exist exceptions. For example, in the second TikZ illustration in Section 3, the DP algorithm selects a subset whose energy is near optimal; however, a brute-force search over the configuration space produces a different subset with slightly lower energy when we choose 5 points, whereas for 3 and 4 points the results are correct. This observation underlines that the DP algorithm, due to its reliance on local decisions, may sometimes overlook the global optimum when non-local interactions are significant. 2.4 Time Complexity The DP table is of size O(nk) and for each state DP(i,r) the algorithm examines up to O(n) previous states. With appropriate precomputation (or memoization) of the \Delta(p,i) values, the overall time complexity is O(n^{2}k) . 2.5 Examples Example 1: x=[0,\,1,\,3,\,6] , k=3 , s=1 Brute-Force Calculation: List all 3-point subsets and compute the energy: • \{0,1,3\} : E=\frac{1}{1-0}+\frac{1}{3-0}+\frac{1}{3-1}=1+\frac{1}{3}+\frac{1}{2}\approx 1.8333. • \{0,1,6\} : E=1+\frac{1}{6-0}+\frac{1}{6-1}\approx 1.3667. • \{0,3,6\} : E=\frac{1}{3-0}+\frac{1}{6-0}+\frac{1}{6-3}\approx 0.8333. • \{1,3,6\} : E=\frac{1}{3-1}+\frac{1}{6-1}+\frac{1}{6-3}\approx 1.0333. Thus, the brute-force analysis indicates that the subset \{0,3,6\} has the lowest energy, approximately 0.8333 . DP Computation: • For r=1 : DP(i,1)=0 for all i . • For r=2 : – DP(2,2)=DP(1,1)+1/(1-0)=1 . – DP(3,2)=\min\{DP(1,1)+1/(3-0),\,DP(2,1)+1/(3-1)\}=\min\{1/3,\,1/2\}\approx 0.3333 . – DP(4,2)=\min\{DP(1,1)+1/(6-0),\,DP(2,1)+1/(6-1),\,DP(3,1)+1/(6-3)\}\approx\min\{0.1667,\,0.2,\,0.3333\}=0.1667 . • For r=3 : – DP(3,3)=DP(2,2)+\left[1/(3-0)+1/(3-1)\right]\approx 1+\left(1/3+1\right)\approx 1.8333 (only possible with p=2 ). – DP(4,3)=\min\{DP(2,2)+\Delta(2,4),\,DP(3,2)+\Delta(3,4)\} . With p=2 : \Delta(2,4)=1/(6-0)+1/(6-1)\approx 1/6+1/5\approx 0.3667 , total =1+0.3667=1.3667