Description
Abstract:
Teramoto et al. [Inserting points uniformly at every instance. IEICE Transactions, 2006.] defined a spatial uniformity measure of a finite point set in a unit square in R2 called gap ratio. We generalize the definition of this measure over all metric spaces. The generalized definition is basically a ratio between the covering radius and the packing radius of points in the given metric space. A uniform distribution of points according to this measure gives a thin covering and a tight packing i.e., low gap ratio. This gives rise to the question of sampling points while minimising the gap ratio. We solve optimization related questions about selecting uniform point samples from metric spaces, which may be continuous or discrete. In the optimization framework, we study
- lower bounds on gap ratio for different metric spaces;
- hardness results;
- approximation algorithms and hardness of approximation results;
- existence of core sets for both the static and streaming point set.