Computing plurality points and condorcet points in Euclidean space

Yen Wei Wu, Wei Yin Lin, Hung Lung Wang, Kun Mao Chao

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

6 Citations (Scopus)


This work concerns two kinds of spatial equilibria. Given a multiset of n points in Euclidean space equipped with the ℓ2-norm, we call a location a plurality point if it is closer to at least as many given points as any other location. A location is called a Condorcet point if there exists no other location which is closer to an absolute majority of the given points. In d-dimensional Euclidean space ℝd , we show that the plurality points and the Condorcet points are equivalent. When the given points are not collinear, the Condorcet point (which is also the plurality point) is unique in ℝd if such a point exists. To the best of our knowledge, no efficient algorithm has been proposed for finding the point if the dimension is higher than one. In this paper, we present an O(n d-1 logn)-time algorithm for any fixed dimension d ≥ 2.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Number of pages11
Publication statusPublished - 2013
Externally publishedYes
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: 2013 Dec 162013 Dec 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8283 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Symposium on Algorithms and Computation, ISAAC 2013
CityHong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Computing plurality points and condorcet points in Euclidean space'. Together they form a unique fingerprint.

Cite this