Low Complexity Methods For Discretizing Manifolds Via Riesz Energy Minimization

Let \(A\) be a compact \(d\)-rectifiable set embedded in Euclidean space \({\mathbb R}^p, d\le p\). For a given continuous distribution \(\sigma (x)\) with respect to a \(d\)-dimensional Hausdorff measure on \(A\), our earlier results provided a method for generating \(N\)-point configurations on \(A\) that have an asymptotic distribution \(\sigma (x)\) as \(N\rightarrow \infty \); moreover, such configurations are “quasi-uniform” in the sense that the ratio of the covering radius to the separation distance is bounded independently of \(N\). The method is based upon minimizing the energy of \(N\) particles constrained to \(A\) interacting via a weighted power-law potential \(w(x,y)|x-y|^{-s}\), where \(s>d\) is a fixed parameter and \(w(x,y)=\left( \sigma (x)\sigma (y)\right) ^{-({s}/{2d})}\). Here we show that one can generate points on \(A\) with the aforementioned properties keeping in the energy sums only those pairs of points that are located at a distance of at most \(r_N=C_N N^{-1/d}\) from each other, with \(C_N\) being a positive sequence tending to infinity arbitrarily slowly. To do this, we minimize the energy with respect to a varying truncated weight \(v_N(x,y)=\Phi (|x-y|/r_N)\cdot w(x,y)\), where \(\Phi :(0,\infty )\rightarrow [0,\infty )\) is a bounded function with \(\Phi (t)=0, t\ge 1\), and \(\lim _{t\rightarrow 0^+}\Phi (t)=1\). Under appropriate assumptions, this reduces the complexity of generating \(N\)-point “low energy” discretizations to order \(N C_N^d\) computations.