# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Uniformity of Point Samples in Metric Spaces using Gap Ratio

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1411.7819.pdf

(Preprint), 520KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.