Faster algorithms for computing plurality points

Let V be a set of n points in R ^d, which we call voters. A point p ∈ R ^d is preferred over another point p' ∈ R ^d by a voter v ∈ V if dist(v, p) < dist(v, p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L ₂ norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality 6 ball. Finally, we consider the problem in the personalized L ₁ norm, where each point v ∈ V has a preference vector w ₁ (v), . . ., w _d (v) and the distance from v to any point p ∈ R ^d is given by ^d _i= ₁ w _i (v) · |x _i (v) − x _i (p) |. For this case we can compute in O(n ^{d −1} ) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).