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