Low Complexity Methods For Discretizing Manifolds Via Riesz Energy Minimization

Let be a compact -rectifiable set embedded in Euclidean space . For a given continuous distribution with respect to a -dimensional Hausdorff measure on , our earlier results provided a method for generating -point configurations on that have an asymptotic distribution as ; moreover, such configurations are "quasi-uniform" in the sense that the ratio of the covering radius to the separation distance is bounded independently of . The method is based upon minimizing the energy of particles constrained to interacting via a weighted power-law potential , where is a fixed parameter and . Here we show that one can generate points on with the aforementioned properties keeping in the energy sums only those pairs of points that are located at a distance of at most from each other, with being a positive sequence tending to infinity arbitrarily slowly. To do this, we minimize the energy with respect to a varying truncated weight , where is a bounded function with , and . Under appropriate assumptions, this reduces the complexity of generating -point "low energy" discretizations to order computations.