Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/38540
|
| Title: | 質心范諾圖在選區重劃之應用
Using CVD in Electoral Redistricting |
| Authors: | 吳振寰
Wu, Chen-Huan |
| Contributors: | 何瑁鎧
Hor, Maw-Kae
吳振寰
Wu, Chen-Huan |
| Keywords: | 選區重劃
質心范諾圖
redistricting
centroidal voronoi diagram |
| Date: | 2009 |
| Issue Date: | 2010-04-09 13:21:58 (UTC+8) |
| Abstract: | 傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。
過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。
我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。
實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。
Traditionally, electoral redistricting was done manually which was time consumming, inefficient, and hard to maintain fairness. One of the most famous biased electoral redistricting in human history was proposed by Elbridge Gerry in 1812, socalled the Gerrymandering districting. After that, fairness and objectivity are required in every electoral redistricting and, hence, come to the era of automatic redistricting.
We have proposed a series of automatic electoral redistricting mechanisms that were emphasized on producing huge amount of feasible solutions and selecting the right solutions from them. However, we did not consider avoiding over partitioning a county in the proposed mechanisms. In this thesis, we developed a new mechanism for electoral redistricting which not only avoiding the over partitioning problem but also start the redistricting by chosing a better set of seeds.
Using a set of better seeds, we can get a better set of initial electoral districts through the help of centroidal Voronoi diagram. Then, we adjust the population in every district followed by reducing the partitioning number of each county. Since adjusting the county partitioning number may violate the population requirement of the districts, we shall check the population requirement of all the districts again before checking compactness of all the districts. Finally, we applied the county partitioning number reduction process once more to reduce the partitioning number as many as we can.
In the experiments, we used Taipei city to verify our mechanism. Four set of seeds were used to generate different redistricting solutions. We compared our results with the result announced by the Central Election Commission (CEC) and found that CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also used the administrative districts’ center as the seeds to generate the fifth redistricting solutions and obtained the same conclusion, i. e., CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also demonstrated that different redistricting results may change the election outcomes. |
| Reference: | [1].李俊瑩，“應用基因演算法重劃選區”，碩士論文，政治大學資訊科學系，西元2006年
[2].何瑁鎧、李俊瑩、劉克鑛、游清鑫，“選區重劃之分析與探討”，TAAI 2005
[3].謝長紘，“計算幾何學在選區劃分上之分析與應用”，碩士論文，政治大學資訊科學系，西元2008年
[4].何瑁鎧、謝長紘，“計算幾何學在選區劃分上之分析與應用”，TAAI2008
[5].許宏敏，“多重選區劃分之分析與研究”，碩士論文，政治大學資訊科學系，西元2009年
[6].何瑁鎧、許宏敏，”多重選區劃分之分析與研究”，NCS2009
[7]. S.Hess, J.Weaver, H.Siegfeldt, J.Whealn and P.Zitlau, “Nonpartisan Political Redistricting by Computer” Operations Research 13, 1965
[8]. F. Bacao, V.Lobo, and M. Painho. “Applying genetic algorithms to zone design” Springer-Verlag , 2004
[9]. Gerrymandering, http://en.wikipedia.org/wiki/Gerrymandering
[10]. Voronoi diagram, http://en.wikipedia.org/wiki/Voronoi_diagram
[11]. Centroidal Voronoi diagram, http://en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation
[12]. Texas style gerrymandering, http://www.commoncause.org/site/pp.asp?c=dkLNK1MQIwG&b=4849387 |
| Description: | 碩士
國立政治大學
資訊科學學系
95753029
98 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0095753029 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 302901.pdf | | 9321Kb | Adobe PDF2 | 989 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
