Finding Plurality Points in Euclidean Space
Date Issued
2015
Date
2015
Author(s)
Lin, Wei-Yin
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.
Subjects
algorithm
Euclidean space
plurality point
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-F97922079-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):f7b7590a6e3e8235db21d80a9213c1fd