Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Uniformity of Point Samples in Metric Spaces using Gap Ratio


Ghosh,  Arijit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 520KB

Supplementary Material (public)
There is no public supplementary material available

Bishnu, A., Desai, S., Ghosh, A., Goswami, M., & Paul, S. (2014). Uniformity of Point Samples in Metric Spaces using Gap Ratio. Retrieved from http://arxiv.org/abs/1411.7819.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-47F3-B
Teramoto et al. defined a new measure of uniformity of point distribution called the \emph{gap ratio} that measures the uniformity of a finite point set sampled from $\cal S$, a bounded subset of $\mathbb{R}^2$. We attempt to generalize the definition of this measure over all metric spaces. While they look at online algorithms minimizing the measure at every instance, wherein the final size of the sampled set may not be known a priori, we look at instances in which the final size is known and we wish to minimize the final gap ratio. We solve optimization related questions about selecting uniform point samples from metric spaces; the uniformity is measured using gap ratio. We give lower bounds for specific as well as general instances, prove hardness results on specific metric spaces, and a general approximation algorithm framework giving different approximation ratios for different metric spaces.