Progressive scattered data filtering

Given a finite point set Z⊂Rd, the covering radius of a nonempty subset X⊂Z is the minimum distance rX,Z such that every point in Z is at a distance of at most rX,Z from some point in X. This paper concerns the construction of a sequence of subsets of decreasing sizes, such that their covering radii are small. To this end, a method for progressive data reduction, referred to as scattered data filtering, is proposed. The resulting scheme is a composition of greedy thinning, a recursive point removal strategy, and exchange, a postprocessing local optimization procedure. The paper proves adaptive a priori lower bounds on the minimal covering radii, which allows us to control for any current subset the deviation of its covering radius from the optimal value at run time. Important computational aspects of greedy thinning and exchange are discussed. The good performance of the proposed filtering scheme is finally shown by numerical examples.