title: Computing an Approximate Median ("pseudo median") algorithm
body: <p>I've encountered the following question which I have no idea how to solve.</p>
  <p>I'd appreciate some Help:</p>
  <p>Let (X, d) be a metric space. Let Y = {x1, . . . , xn} ⊆ X be a set of n points in the metric
  space. A point x<sup>∗</sup> ∈ X is a ∆-pseudo-median of Y if there exist at least m indices i1, . . . , im
  with m &gt; n/2 such that d(x<sub>i,j</sub> , x<sup>∗</sup>) ≤ ∆ for all j = 1, . . . , m.</p>
  <p>Assume that a ∆-pseudo-median x<sup>∗</sup> exists for Y (but is unknown).
  Devise an algorithm with running time O(n<sup>2</sup>) that finds an index i ∈ {1..n} such that d(xi, x<sup>∗</sup>) ≤ 4∆.</p>
  <p>(Assume that evaluating d(x, y) for x, y ∈ X
  takes O(1) time).</p>