在歐式空間中尋找多數決策點

Finding Plurality Points in Euclidean Space

林蔚茵(Wei-Yin Lin)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2015年)

https://doi.org/10.6342/NTU.2015.00980

摘要

無資料

關鍵字

演算法 ； 歐式空間 ； 多數決策點

並列摘要

The purpose of this dissertation is to study the properties of plurality points and design an efficient algorithm to find them. Given a multiset of $n$ points equipped with the $ell_2$-norm, a emph{plurality point} is a location which is closer to at least as many given points as any other location. This spatial equilibrium formed by voting has been studied for decades in both the field of economy and location theory. For any $d$-dimensional space where $d$ is fixed, we present an $O(n^{d-1} log n)$-time algorithm to compute the point. However, the plurality point may not exist if the given points are not collinear. In order to find an alternative solution, some related problem extensions are also investigated in this dissertation.

並列關鍵字

algorithm ； Euclidean space ； plurality point

參考文獻

[41] W.-Y. Lin, Y.-W. Wu, H.-L. Wang, and K.-M. Chao, “Forming plurality at minimum cost,” Proceedings of the 9th International Workshop on Algorithms and Computation, pp. 77–88, 2015.

[30] P. Hansen and J.-F. Thisse, “Outcomes of voting and planning : Condorcet, Weber and Rawls locations,” Journal of Public Economics, Vol. 16(1), pp. 1–15, 1981.

[19] G. Demange, “Spatial models of collective choice,” In: J.-F. Thisse and H. G. Zoller (eds.), Locational Analysis of Public Facilities, North-Holland, Amsterdam, 1983.

[2] P. Afshani, “On approximate range counting and depth,” Discrete and Computational Geometry, Vol. 42(1), pp. 3–21, 2009.

[4] G. Aloupis, S. Langerman, M. Soss, and G. T. Toussaint, “Algorithms for bivariate medians and a Fermat-Torricelli problem for lines,” Computational Geometry, Vol. 26(1), pp. 69–79, 2003.