Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard
2026-08-24 • Computational Geometry
Computational GeometryComputational Complexity
AI summaryⓘ
The authors show that picking a subset of points in a plane to minimize a certain energy measure, called Riesz 2-energy, is a hard problem (NP-complete). This is the first time such complexity has been proven when both the dimension (2D) and the energy exponent (2) are fixed. They create their proof by translating a known hard problem from physics (Ising model) into this energy selection problem, carefully encoding spins and interactions using points arranged in squares and lines. Their construction uses exact rational numbers, ensuring precise calculations without approximation.
Riesz energyNP-completeEuclidean planeIsing modelferromagneticantiferromagneticsubset selectioncomputational complexityrational coordinates
Authors
Michael Emmerich
Abstract
We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.