Before revision:  our result is the first sub-linear time algorithm having the sample size {\em   independent of both the input number of points n and dimensionality d  . Furthermore, we observe that these two techniques can be generalized to deal with a broader range of geometric optimization problems with outliers in high dimensions, including flat fitting, k-center clustering, and SVM with outliers, and therefore achieve  sub-linear time bi-criteria approximation algorithms for these problems respectively.
After revision:  our result is the first sub-linear time algorithm having the sample size {\em the number of sampled points) independent of both the input number of points n and dimensionality d . Furthermore, we observe that these two techniques can be generalized to deal with a broader range of geometric optimization problems with outliers in high dimensions, including flat fitting, k-center clustering, and SVM with outliers, and therefore achieve sub-linear time bi-criteria approximation algorithms for these problems respectively.