Optimal Coresets for Low-Dimensional Geometric Median

We investigate coresets for approximating the cost with respect to median queries. In this problem, we are given a set of points P ⊂ ℝ^d and median queries are ∑_p∈P ∥p - c∥ for any point c ∈ ℝ^d. Our goal is to compute a small weighted summary S ⊂ P such that the cost of any median query is approximated within a multiplicative (1 ± ε) factor. We provide matching upper and lower bounds on the number of points contained in S of the order Θ̃ (ε^-d/(d+1)).