 License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.32
URN: urn:nbn:de:0030-drops-59248
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5924/
 Go to the corresponding LIPIcs Volume Portal

### Faster Algorithms for Computing Plurality Points

 pdf-format:

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

### BibTeX - Entry

```@InProceedings{deberg_et_al:LIPIcs:2016:5924,
author =	{Mark de Berg and Joachim Gudmundsson and Mehran Mehr},
title =	{{Faster Algorithms for Computing Plurality Points}},
booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
pages =	{32:1--32:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-009-5},
ISSN =	{1868-8969},
year =	{2016},
volume =	{51},
editor =	{S{\'a}ndor Fekete and Anna Lubiw},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5924},
URN =		{urn:nbn:de:0030-drops-59248},
doi =		{10.4230/LIPIcs.SoCG.2016.32},
annote =	{Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points}
}
```

 Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points Collection: 32nd International Symposium on Computational Geometry (SoCG 2016) Issue Date: 2016 Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy 