Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52897
Title: | 在歐式空間中尋找多數決策點 Finding Plurality Points in Euclidean Space |
Authors: | Wei-Yin Lin 林蔚茵 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 演算法,歐式空間,多數決策點, algorithm,Euclidean space,plurality point, |
Publication Year : | 2015 |
Degree: | 博士 |
Abstract: | 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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-104-1.pdf Restricted Access | 796.49 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.