傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。 過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。 我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。 實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。 / 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.

[pt] Uma boa representação de malhas tridimensionais é fundamental para a renderização de objetos e para simulações numéricas. Ocorre, entretanto, que, quando objetos são capturados através de sensores, é comum existir super amostragem em algumas regiões e/ou sub amostragem em outras. Para resolver esse problema existem diversas técnicas na literatura de reamostragem da malha. Recentemente uma abordagem mais generalizada para uma representação utilizando malhas de triângulos e com boas garantias matemáticas gerando malhas com triângulos muito próximos aos triângulos de Delaunay vem ganhando destaque. O grande problema desta técnica para a aplicação de objetos com bordas (buracos ou malha aberta) é que ela faz um efeito de erosão nas bordas. Para uma aplicação em que as bordas e buracos devem representar aproximadamente a mesma região isso é um grande problema. Neste trabalho apresentamos uma abordagem geométrica para a reamostragem da representação do objeto que resolve este problema aplicado em dados de horizonte sísmico. / [en] A good mesh representation of tridimensional objects is necessary not only to render algorithms but also to support numerical simulations. Objects captured via sensors, e.g., seismic acquisition and laser scanning, have an intrinsic error in its representation of objects. Furthermore, this unprocessed data does not generate a good description of the objects, portraying it inadequately or incorrectly. The existing literature on resampling representations contains various techniques to resolve this problem. In particular, a general approach using triangle mesh has recently gained attention. One benefit of this technique is its mathematical guarantees generating triangles meshes that closely approximate Delaunay triangles. The main drawback to this technique occurs in its application to objects with borders, such as holes or mesh intersections. In this work, we present a new method to re-mesh the object representation taking into account the simplification of the curves that represent the holes. We apply this technique to seismic horizon data.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d’éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres / Depending on the specific method used to build a 3D structural model, and on the exact purpose of this model, its mesh must be adapted so that it enforces criteria on element types, maximum number of elements, and mesh quality. Meshing methods developed for applications others than geomodeling forbid any modification of the input model, that may be desirable in geomodeling to better control the number of elements in the final mesh and their quality. The objective of this thesis is to develop meshing methods that fulfill this requirement to better manage the geometrical complexity of B-Rep geological structural models. An analysis of the sources of geometrical complexity in those models is first proposed. The introduced measures are a first step toward the definition of tools allowing objective comparisons of structural models and permit to characterize the model zones that are more complicated to mesh. We then introduce two original meshing methods based on Voronoi diagrams: the first for surface remeshing, the second for hybrid gridding. The key ideas of these methods are identical: (1) the use of a centroidal Voronoi optimization to have a globally controlled number of elements of good quality, and (2) combinatorial considerations to locally build the final mesh while sometimes modifying the initial model. The surface remeshing method is automatic and permits to simplify a model at a given resolution. The gridding method generates a hybrid volumetric mesh. Prisms and pyramids fill the very thin layers of the model while the remaining regions are filled with tetrahedra