2026-07-26T03:28:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5924 2024-03-06T10:37:17Z ddc:004 open_access

Faster Algorithms for Computing Plurality Points de Berg, Mark Gudmundsson, Joachim Mehr, Mehran computational geometry computational social choice voting theory plurality points Condorcet points 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Joachim Gudmundsson and Mehran Mehr 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.32 urn:nbn:de:0030-drops-59248 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode