Faster algorithms for computing plurality points

Mark T. de Berg, Joachim Gudmundsson, Mehran Mehr

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
1 Downloads (Pure)

Abstract

Let V be a set of n points in R d, which we call voters. A point p ∈ R d is preferred over another point p' ∈ R d by a voter v ∈ 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 a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality 6 ball. Finally, we consider the problem in the personalized L 1 norm, where each point v ∈ V has a preference vector w 1 (v), . . ., w d (v) and the distance from v to any point p ∈ R d is given by d i= 1 w i (v) · |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
Article number36
Number of pages23
JournalACM Transactions on Algorithms
Volume14
Issue number3
DOIs
Publication statusPublished - Jul 2018

Keywords

  • Computational geometry
  • Computational social choice
  • Condorcet points
  • Plurality points
  • Voronoi games
  • Voting theory

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

Cite this