## Samenvatting

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).

Originele taal-2 | Engels |
---|---|

Titel | 32. Symposium on Computational Geometry 2016, 14-18 June 2016, Boston, Massachusetts |

Pagina's | 1-15 |

DOI's | |

Status | Gepubliceerd - 2016 |

Evenement | 32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, Verenigde Staten van Amerika Duur: 14 jun 2016 → 18 jun 2016 |

### Congres

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

Land/Regio | Verenigde Staten van Amerika |

Stad | Boston |

Periode | 14/06/16 → 18/06/16 |