Faster algorithms for computing plurality points

M.T. de Berg, J. Gudmundsson, M. Mehr

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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 languageEnglish
Title of host publication32. Symposium on Computational Geometry 2016, 14-18 June 2016, Boston, Massachusetts
Publication statusPublished - 2016
Event32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, United States
Duration: 14 Jun 201618 Jun 2016


Conference32nd International Symposium on Computational Geometry (SoCG 2016)
Country/TerritoryUnited States


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


Dive into the research topics of 'Faster algorithms for computing plurality points'. Together they form a unique fingerprint.

Cite this