Low complexity methods for discretizing manifolds via Riesz energy minimization

Abstract. Let A be a compact d-rectifiable set embedded in Euclidean space Rp, d ≤ p. For a given continuous distribution σ(x) with respect to d-dimensional Hausdorff measure on A, our earlier results provided a method for generating N-point configura-tions on A that have asymptotic distribution σ(x) as N →∞; moreover such configura-tions are “quasi-uniform ” in the sense that the ratio of the covering radius to the separa-tion distance is bounded independent 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) = (σ(x)σ(y))−(s/2d). Here we show that one can generate points on A with the above mentioned properties keeping in the energy sums only those pairs of points that are located at a distance of at most rN = CNN −1/d from each other, with CN being a positive sequence tending to infinity arbitrarily slowly. To do this we minimize the energy with respect to a varying truncated weight vN (x, y) = Φ (|x − y | /rN)w(x, y), where Φ: (0,∞) → [0,∞) is a bounded function with Φ(t) = 0, t ≥ 1, and limt→0+ Φ(t) = 1. This reduces, under appropriate assumptions, the complexity of generating N point ‘low energy’ discretizations to order NCdN computations. 1