Before revision:  Additionally, we propose new algorithms for computing such subsets, with tight approximation factors in general metrics, and improved factors for doubling metrics and \ell_p metrics with p . Finally , we show an alternative implementation scheme that reduces the worst-case time complexity of one of these algorithms , becoming the first truly subquadratic approximation algorithm for the nearest-neighbor condensationproblem .
After revision:  Additionally, we propose new algorithms for computing such subsets, with tight approximation factors in general metrics, and improved factors for doubling metrics and \ell_p metrics with p . Finally , we show an alternative implementation scheme that reduces the worst-case time complexity of one of these algorithms to have subquadratic runtime, being the first of this kind for condensation .