Finding plurality points in R^d

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


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.
Original languageEnglish
Title of host publication32nd European Workshop on Computational Geometry (EuroCG 2016), 30 March - 1 April, Lugano, Switzerland
Publication statusPublished - 2016
Event32nd European Workshop on Computational Geometry (EuroCG 2016) - Lugano, Switzerland
Duration: 30 Mar 20161 Apr 2016
Conference number: 32


Workshop32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated titleEuroCG 2016
Internet address


Dive into the research topics of 'Finding plurality points in R^d'. Together they form a unique fingerprint.

Cite this