請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52897
標題: | 在歐式空間中尋找多數決策點 Finding Plurality Points in Euclidean Space |
作者: | Wei-Yin Lin 林蔚茵 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 演算法,歐式空間,多數決策點, algorithm,Euclidean space,plurality point, |
出版年 : | 2015 |
學位: | 博士 |
摘要: | 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52897 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 796.49 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。