de Berg, Mark ;
Gudmundsson, Joachim ;
Mehr, Mehran
Faster Algorithms for Computing Plurality Points
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 socalled minimumradius 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^(d1)) 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:132:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5924},
URN = {urn:nbn:de:0030drops59248},
doi = {10.4230/LIPIcs.SoCG.2016.32},
annote = {Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points}
}
10.06.2016
Keywords: 

computational geometry, computational social choice, voting theory, plurality points, Condorcet points 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

10.06.2016 