Faster algorithms for computing plurality points

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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).

Originele taal-2Engels
Titel32. Symposium on Computational Geometry 2016, 14-18 June 2016, Boston, Massachusetts
StatusGepubliceerd - 2016
Evenement32nd International Symposium on Computational Geometry (SoCG 2016) - Boston, Verenigde Staten van Amerika
Duur: 14 jun 201618 jun 2016


Congres32nd International Symposium on Computational Geometry (SoCG 2016)
Land/RegioVerenigde Staten van Amerika


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

Citeer dit