TY - GEN

T1 - Computing plurality points and condorcet points in Euclidean space

AU - Wu, Yen Wei

AU - Lin, Wei Yin

AU - Wang, Hung Lung

AU - Chao, Kun Mao

PY - 2013

Y1 - 2013

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

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

UR - http://www.scopus.com/inward/record.url?scp=84893399008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893399008&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45030-3_64

DO - 10.1007/978-3-642-45030-3_64

M3 - Conference contribution

AN - SCOPUS:84893399008

SN - 9783642450297

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 688

EP - 698

BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings

T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013

Y2 - 16 December 2013 through 18 December 2013

ER -