Computing plurality points and condorcet points in Euclidean space

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

研究成果: 書貢獻/報告類型會議論文篇章

6 引文 斯高帕斯(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.

原文英語
主出版物標題Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
頁面688-698
頁數11
DOIs
出版狀態已發佈 - 2013
對外發佈
事件24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, 中国
持續時間: 2013 十二月 162013 十二月 18

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
8283 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

會議

會議24th International Symposium on Algorithms and Computation, ISAAC 2013
國家/地區中国
城市Hong Kong
期間2013/12/162013/12/18

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「Computing plurality points and condorcet points in Euclidean space」主題。共同形成了獨特的指紋。

引用此