# Faster algorithms for computing plurality points

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

## Samenvatting

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).

Originele taal-2 Engels 32. Symposium on Computational Geometry 2016, 14-18 June 2016, Boston, Massachusetts 1-15 https://doi.org/10.4230/LIPIcs.SoCG.2016.32 Gepubliceerd - 2016 32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, Verenigde Staten van AmerikaDuur: 14 jun 2016 → 18 jun 2016

### Congres

Congres 32nd International Symposium on Computational Geometry (SoCG 2016) Verenigde Staten van Amerika Boston 14/06/16 → 18/06/16

## Vingerafdruk

Duik in de onderzoeksthema's van 'Faster algorithms for computing plurality points'. Samen vormen ze een unieke vingerafdruk.