## Abstract

Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in 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 the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector <w_1(v), ...,w_d(v)> and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |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 |
---|---|

Title of host publication | 32. Symposium on Computational Geometry 2016, 14-18 June 2016, Boston, Massachusetts |

Pages | 1-15 |

DOIs | |

Publication status | Published - 2016 |

Event | 32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, United States Duration: 14 Jun 2016 → 18 Jun 2016 |

### Conference

Conference | 32nd International Symposium on Computational Geometry (SoCG 2016) |
---|---|

Country/Territory | United States |

City | Boston |

Period | 14/06/16 → 18/06/16 |

## Keywords

- computational geometry, computational social choice, voting theory, plurality points, Condorcet points