Proximity Algorithms for Nearly Doubling Spaces
Lee-Ad J. Gottlieb, Robert Krauthgamer · SIAM Journal on Discrete Mathematics · 2013
We introduce a new problem in the study of doubling spaces: Given a point set $S$ and a target dimension $d^*$, remove from $S$ the fewest number of points so that the remaining set has doubling dimension at most $d^*$. We present a bicriteria approximation for this problem and extend this algorithm to solve a group of proximity problems.