Finding plurality points in R^d

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

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

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

Workshop

Workshop32nd European Workshop on Computational Geometry (EuroCG 2016)
Abbreviated titleEuroCG 2016
CountrySwitzerland
CityLugano
Period30/03/161/04/16
Internet address

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

Cite this