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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5924/
Go to the corresponding LIPIcs Volume Portal

de Berg, Mark ; Gudmundsson, Joachim ; Mehr, Mehran

Faster Algorithms for Computing Plurality Points

pdf-format:
LIPIcs-SoCG-2016-32.pdf (0.5 MB)

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 Published by LZI