## Abstract

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
_{2} 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
_{1} norm, where each point v ∈ V has a preference vector w
_{1} (v), . . ., w
_{d} (v) and the distance from v to any point p ∈ R
^{d} is given by
^{d}
_{i}=
_{1} 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).

Original language | English |
---|---|

Article number | 36 |

Number of pages | 23 |

Journal | ACM Transactions on Algorithms |

Volume | 14 |

Issue number | 3 |

DOIs | |

Publication status | Published - Jul 2018 |

## Keywords

- Computational geometry
- Computational social choice
- Condorcet points
- Plurality points
- Voronoi games
- Voting theory