Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Computing Plurality Points and Condorcet Points in Euclidean Space
verfasst von : Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, Kun-Mao Chao
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
log
n
)-time algorithm for any fixed dimension
d
≥ 2.