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, dle 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 (Nrightarrow 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, tge 1) , and (lim _{trightarrow 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.