Cette thèse traite du problème de la tessellation volumétrique à partir des formes en trois dimensions, c’est-à-dire, étant donné une forme tridimensionnelle qui est habituellement représentée par sa surface au bord, comment subdiviser l’intérieur de la surface en formes plus petites, appelées cellules, de manière optimale selon plusieurs critères concernant l’exactitude, l’uniformité et la régularité. Nous considérons la tessellation de Voronoi centroidale qui est une approche efficace pour construire des tessellations volumétriques uniformes et régulières.Une tessellation de Voronoi centroidale (CVT) d’une forme peut être considérée comme une subdivision optimale avec les cellules dont les centres de masse, appelés centroides, sont répartis de manière optimale l’intérieur de la forme. CVTs ont été largement utilisés dans la vision par ordinateur et l’infographie en raison de leurs propriétés d’uniformité et de régularité qui sont indépendantes des variations de la forme. Cependant, les problèmes tels que comment évaluer la régularité d’une CVT et comment construire une CVT à partir des formes de types différents restent un défi.Nous proposons, comme contribution de cette thèse, que des critères de régularité basés sur des moments de second ordre normalisés des cellules. Ces critères de régularité permettent d’évaluer les tessellations volumétriques, et surtout, de comparer la régularité des différents CVTs sans l’hypothèse que leur forme et leur nombre de sites devraient être les mêmes. Nous proposons également une approche hiérarchique basée sur un schéma de subdivision qui préserve la régularité des cellules et l’optimalité locale des CVTs. Les résultats expérimentaux montrent que notre approche construit de manière plus efficace des CVTs plus régulières que les méthodes de l’état de l’art selon les critères de régularité.Une autre contribution est un nouvel algorithme de CVT pour les formes implicites et une comparaison approfondie entre l’algorithme Marching Cubes (MC), le raffinement de Delaunay et notre algorithme. L’idée clé de notre algorithme est l’utilisation des enveloppes convexes et l’amélioration locale pour construire des cellules au bord précises. Nous présentons une comparaison des trois algorithmes avec des critères différents, y compris la précision, la régularité et la complexité sur un grand nombre de données variantes. Les résultats montrent que MC est le plus rapide et que le notre construit les tessellations volumétriques les plus précises et les plus régulières.Nous explorons aussi les applications comme, par exemple, un framework d’animation des formes basées sur CVTs qui génère des animations plausibles avec une réelle dynamique. Le code source de l’ensemble des travaux de cette thèse est disponible en ligne dans le but de la recherche future. / This thesis addresses the problem of volumetric tessellations from three-dimensional shapes, i.e., given a three-dimensional shape that is usually represented by its boundary surface, how to optimally subdivide the interior of the surface into smaller shapes, called cells, according to several criteria concerning accuracy, uniformity and regularity. We consider centroidal Voronoi tessellation that is an effective approach for building uniform and regular volumetric tessellations.A centroidal Voronoi tessellation (CVT) of a shape can be viewed as an optimal subdivision with the cells whose centers of mass, called centroids, are optimally distributed inside the shape. CVTs have been widely used in computer vision and graphics because of their properties of uniformity and regularity that are immune to shape variations. However, the problems such as how to evaluate the regularity of a CVT and how to build a CVT from different types of shapes remain a challenge.One contribution of this thesis is that we propose regularity criteria based on the normalized second order moments of the cells. These regularity criteria allow evaluating volumetric tessellations and specially comparing the regularity of different CVTs without the assumption that their shape and number of sites should be the same. Meanwhile, we propose a hierarchical approach based on a subdivision scheme that preserves cell regularity and the local optimality of CVTs. Experimental results show that our approach performs more efficiently and builds more regular CVTs according to the regularity criteria than state-of-the-art methods.Another contribution is a novel CVT algorithm for implicit shapes and an extensive comparison of Marching Cubes, Delaunay refinement and our algorithm. The key of our algorithm is using convex hulls and the local improvement to build accurate boundary cells. We present a comparison of these three algorithms with different criteria including accuracy, regularity and complexity on a large number of variant data. The results show that Marching Cubes is the fastest one and our algorithm build more accurate and regular volumetric tessellations than the others.We also explore the applications such as a shape animation framework based on CVTs that generates plausible animations with real dynamics. And the source code of the whole work of this thesis is available online for the purpose of further research.

This thesis introduces a design combining an emerging area in robotics with a well established mathematical research topic: swarm intelligence and Voronoi tessellations, respectively. The main objective for this research is to design an economical and robust swarm system to achieve distributed control. This research combines swarm intelligence with Voronoi tessellations to localize a source and create formations. Extensive software coding must be implemented for this design, such as the development of a discrete centroidal Voronoi tessellation (CVT) algorithm. The ultimate purpose of this research is to advance the existing Mobile Actuator and Sensor Network (MASnet) platform to eventually develop a cooperative robot team that can sense, predict, and nally neutralize a diusion process. Previous work on the MASnet platform has served as a foundation for this research. While growing closer to the MASnet goal, results also provide stimulating discoveries for mathematical and swarm research areas.

[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.

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

Uma tendência crescente entre os pesquisadores da Robótica Móvel é a elaboração de sistemas robóticos descentralizados denominados enxames de robôs, nos quais a ação conjunta de cada agente leva à execução de tarefas de maneira mais robusta que quando realizada por um único robô. Um acréscimo adicional à robustez é conveniente em tais sistemas para que eles sejam de maior confiabilidade no mundo real. Neste trabalho, uma rede neural hierárquica desenvolvida para o aprendizado em tempo real inicialmente elaborada para o aprendizado de navegação de um único robô será estendida para controlar um enxame de robôs. O sistema realiza um balanceamento da influência de comportamentos implementados previamente em um robô de acordo com conhecimentos obtidos através da interação do mesmo com o ambiente. Cada robô possui sua própria rede neural, adquirindo seu conhecimento tanto independentemente quanto com o compartilhamento de informações com outros robôs. Espera-se que o uso de tal arquitetura permita uma adaptação mais rápida dos robôs ao ambiente, permitindo uma mudança em tempo real de seus parâmetros de acordo com as peculiaridades do ambiente no qual os robôs estão inseridos. A tarefa de escolta de um robô pelos demais é adotada para a avaliação de desempenho do modelo de rede neural proposto. Dois comportamentos são ponderados pela rede neural hierárquica: o de manutenção de uma distância preestabelecida a um agente e um outro de cobertura de área baseado em Diagramas Centroidais de Voronoi. Os testes foram feitos nos ambientes Player/Stage e indicam que a rede neural hierárquica torna os robôs capazes não apenas de aprender à medida que interagem com ambiente como de utilizar este conhecimento em tempo real para realizar a escolta de forma bem sucedida / A growing trend among Mobile Robotics researchers is developing robot swarms, in which a decentralized robot team solves tasks by combining simple behaviors. It is convenient to have mechanisms to increase a robot systems robustness. In this work, a neural network inspired in behavioral analysis is used to make robots from a swarm to learn how to act propoerly. This network combines two innate behaviors and, according to its experience, learns with the robots mistakes how to make this combination. Each robot has access to its own independent neural network, and can share its knowledge with neighboring robots. It is expected that such architecture learns by itself when to stimulate or supress each behaviors influence as it interacts with the environment. The task chosen to evaluate the proposed system is the escorting of a mobile agent. Two behaviors are balanced to achieve an escorting behavior: maintenance of a minimum distance between a robot and the escort target and an area coverage method based on Centroidal Voronoi Tessellations. Tests were meade using the Player/Stage simulator, and they show that the robots not only are capable of adapting themselves but also are able to use the stored knowledge to improve their effectiveness in doing the desired task

Uma tendência crescente entre os pesquisadores da Robótica Móvel é a elaboração de sistemas robóticos descentralizados denominados enxames de robôs, nos quais a ação conjunta de cada agente leva à execução de tarefas de maneira mais robusta que quando realizada por um único robô. Um acréscimo adicional à robustez é conveniente em tais sistemas para que eles sejam de maior confiabilidade no mundo real. Neste trabalho, uma rede neural hierárquica desenvolvida para o aprendizado em tempo real inicialmente elaborada para o aprendizado de navegação de um único robô será estendida para controlar um enxame de robôs. O sistema realiza um balanceamento da influência de comportamentos implementados previamente em um robô de acordo com conhecimentos obtidos através da interação do mesmo com o ambiente. Cada robô possui sua própria rede neural, adquirindo seu conhecimento tanto independentemente quanto com o compartilhamento de informações com outros robôs. Espera-se que o uso de tal arquitetura permita uma adaptação mais rápida dos robôs ao ambiente, permitindo uma mudança em tempo real de seus parâmetros de acordo com as peculiaridades do ambiente no qual os robôs estão inseridos. A tarefa de escolta de um robô pelos demais é adotada para a avaliação de desempenho do modelo de rede neural proposto. Dois comportamentos são ponderados pela rede neural hierárquica: o de manutenção de uma distância preestabelecida a um agente e um outro de cobertura de área baseado em Diagramas Centroidais de Voronoi. Os testes foram feitos nos ambientes Player/Stage e indicam que a rede neural hierárquica torna os robôs capazes não apenas de aprender à medida que interagem com ambiente como de utilizar este conhecimento em tempo real para realizar a escolta de forma bem sucedida / A growing trend among Mobile Robotics researchers is developing robot swarms, in which a decentralized robot team solves tasks by combining simple behaviors. It is convenient to have mechanisms to increase a robot systems robustness. In this work, a neural network inspired in behavioral analysis is used to make robots from a swarm to learn how to act propoerly. This network combines two innate behaviors and, according to its experience, learns with the robots mistakes how to make this combination. Each robot has access to its own independent neural network, and can share its knowledge with neighboring robots. It is expected that such architecture learns by itself when to stimulate or supress each behaviors influence as it interacts with the environment. The task chosen to evaluate the proposed system is the escorting of a mobile agent. Two behaviors are balanced to achieve an escorting behavior: maintenance of a minimum distance between a robot and the escort target and an area coverage method based on Centroidal Voronoi Tessellations. Tests were meade using the Player/Stage simulator, and they show that the robots not only are capable of adapting themselves but also are able to use the stored knowledge to improve their effectiveness in doing the desired task

Cet ouvrage aborde la génération de grilles de Voronoï sous contrainte pour réduire les erreurs liées à la géométrie des cellules lors de la simulation réservoir. Les points de Voronoï sont optimisés en minimisant des fonctions objectif correspondant à différentes contraintes géométriques. L'originalité de cette approche est de pouvoir combiner les contraintes simultanément : - la qualité des cellules, en plaçant les points de Voronoï aux barycentres des cellules ; - le raffinement local, en fonction d'un champ de densité [rho], correspondant à la perméabilité, la vitesse ou la vorticité ; - l'anisotropie des cellules, en fonction d'un champ de matrice M contenant les trois vecteurs principaux de l'anisotropie, dont l'un est défini par le vecteur vitesse ou par le gradient stratigraphique ; - l'orientation des faces des cellules, en fonction d'un champ de matrice M contenant les trois vecteurs orthogonaux aux faces, dont l'un est défini par le vecteur vitesse ; - la conformité aux surfaces du modèle structural, failles et horizons ; - l'alignement des points de Voronoï le long des puits. La qualité des grilles générées est appréciée à partir de critères géométriques et de résultats de simulation comparés à des grilles fines de référence. Les résultats indiquent une amélioration de la géométrie, qui n'est pas systématiquement suivie d'une amélioration des résultats de simulation / Voronoi grids are generated under constraints to reduce the errors due to cells geometry during flow simulation in reservoirs. The Voronoi points are optimized by minimizing objective functions relevant to various geometrical constraints. An original feature of this approach is to combine simultaneously the constraints: - Cell quality, by placing the Voronoi points at the cell barycenters. - Local refinement according to a density field rho, relevant to permeability, velocity or vorticity. - Cell anisotropy according to a matrix field M built with the three principal vectors of the anisotropy, which one is defined by the velocity vector or by the stratigraphic gradient. - Faces orientation according to a matrix field M built with the three vectors orthogonal to the faces, which one is defined by the velocity vector. - Conformity to structural features, faults and horizons. - Voronoï points alignment along well path. The quality of the generated grids is assessed from geometrical criteria and from comparisons of flow simulation results with reference fine grids. Results show geometrical improvements, that are not necessarily followed by flow simulation results improvements

This thesis is devoted to the problem of finding a suitable geometrical de- scription of the domain for the Finite Element Method (FEM). We present the most important methods used in generation and improvement of unstructured triangular meshes (grids) for two dimensional FEM. Possible measures of mesh quality are discussed with respect to their usage in linear Lagrange FEM. The relationship between mesh geometry (especially angles of particular triangles), discretization error and stiffness matrix condition number is examined. Two methods of mesh improvement, based on Centroidal Voronoi Tessellations (CVT) and Optimal Delaunay Triangulations (ODT), are discussed in detail and some results on convergence of CVT based methods are reviewed. Some aspects of these methods, e.g. the relation between density of boundary points and interior mesh vertices and the treatment of the boundary triangles is reconsidered in a new way. We have implemented these two methods and we discuss possible im- provements and new algorithms. A geometrically very interesting idea of recent alternative to FEM, Isogeometric Analysis (IGA), is outlined and demonstrated on a simple example. Several numerical tests are made in order to the compare the accuracy of solutions of isotropic PDEs obtained by FEM on bad mesh, mesh improved...

This thesis is concerned with the numerical solutions of initial value problems with ordinary differential equations and covers single step integration methods. focus is to study the numerical the various aspects of Specifically, its main methods of non-linear integration formula with a variety of means based on the Contraharmonic mean (C.M) (Evans and Yaakub [1995]), the Centroidal mean (C.M) (Yaakub and Evans [1995]) and the Root-Mean-Square (RMS) (Yaakub and Evans [1993]) for solving initial value problems. the applications of the second It includes a study of order C.M method for parallel implementation of extrapolation methods for ordinary differential equations with the ExDaTa schedule by Bahoshy [1992]. Another important topic presented in this thesis is that a fifth order five-stage explicit Runge Kutta method or weighted Runge Kutta formula [Evans and Yaakub [1996]) exists which is contrary to Butcher [1987] and the theorem in Lambert ([1991] ,pp 181). The thesis is organized as follows. An introduction to initial value problems in ordinary differential equations and parallel computers and software in Chapter 1, the basic preliminaries and fundamental concepts in mathematics, an algebraic manipulation package, e.g., Mathematica and basic parallel processing techniques are discussed in Chapter 2. Following in Chapter 3 is a survey of single step methods to solve ordinary differential equations. In this chapter, several single step methods including the Taylor series method, Runge Kutta method and a linear multistep method for non-stiff and stiff problems are also considered. Chapter 4 gives a new Runge Kutta formula for solving initial value problems using the Contraharmonic mean (C.M), the Centroidal mean (C.M) and the Root-MeanSquare (RMS). An error and stability analysis for these variety of means and numerical examples are also presented. Chapter 5 discusses the parallel implementation on the Sequent 8000 parallel computer of the Runge-Kutta contraharmonic mean (C.M) method with extrapolation procedures using explicit assignment scheduling Kutta RK(4, 4) method (EXDATA) strategies. A is introduced and the data task new Rungetheory and analysis of its properties are investigated and compared with the more popular RKF(4,5) method, are given in Chapter 6. Chapter 7 presents a new integration method with error control for the solution of a special class of second order ODEs. In Chapter 8, a new weighted Runge-Kutta fifth order method with 5 stages is introduced. By comparison with the currently recommended RK4 ( 5) Merson and RK5(6) Nystrom methods, the new method gives improved results. Chapter 9 proposes a new fifth order Runge-Kutta type method for solving oscillatory problems by the use of trigonometric polynomial interpolation which extends the earlier work of Gautschi [1961]. An analysis of the convergence and stability of the new method is given with comparison with the standard Runge-Kutta methods. Finally, Chapter 10 summarises and presents conclusions on the topics discussed throughout the thesis.

One of the main focus of research on multi-agent systems is that of coordination in a group of agents to solve problems that are beyond the capability of a single agent. Each agent in the multi-agent system has limited capacity and/or knowledge which makes coordination a challenging task. Applications of multi-agent systems in space and ocean exploration, military surveillance and rescue missions, require the agents to achieve some consensus in their motion. The consensus has to be achieved and maintained without a centralized controller. Multi-agent system research borrows ideas from the biological world where such motion consensus strategies can be found in the flocking of birds, schooling of fishes, and colony of ants. One such classes of strategies are the cyclic pursuit strategies which mimic the behavior of dogs, birds, ants, or beetles, where one agent pursues another in a cyclic manner, and are commonly referred to as the `bugs' problem, In the literature, cyclic pursuit laws have been applied to a swarm of homogenous agents, where there exists a predefined cyclic connection between agents and each agent follows its predecessor. At equilibrium, the agents reach consensus in relative positions. Equilibrium formation, convergence, rate of convergence, and stability are some of the aspects that have been studied under cyclic pursuit. In this thesis, the notion of cyclic pursuit has been generalized. In cyclic pursuit, usually agents are homogenous in the sense of having identical speeds and controller gains where an agent has an unique predecessor whom it follows. This is defined as the basic cyclic pursuit (BCP) and the sequence of connection among the agents is defined as the Pursuit sequence (PS). We first generalize this system by assuming heterogeneous speed and controller gains. Then, we consider a strategy where an agent can follow a weighted centroid of a group of other agents instead of a single agent. This is called centroidal cyclic pursuit (CCP). In CCP, the set of weights used by the agents are assumed to be the same. We generalize this further by considering the set of weights adopted by each agent to be different. This defines a generalized centroidal cyclic pursuit (GCCP). The behavior of the agents under BCP, CCP and GCCP are studied in this thesis. We show that a group of holonomic agents, under the cyclic pursuit laws ¡ BCP, CCP and GCCP ¡ can be represented as a linear system. The stability of this system is shown to depend on the gains of the agents. A stable system leads to a rendezvous of the agents. The point of rendezvous, also called the reachable point, is a function of the gains. In this thesis, the conditions for stability of the heterogeneous system of agents in cyclic pursuit are obtained. Also, the reachable point is obtained as a function of the controller gains. The reachable set, which is a region in space where rendezvous can occur, given the initial positions of the agents, are determined and a procedure is proposed for calculating the gains of the agents for rendezvous to occur at any desired point within the reachable set. Invariance properties of stability, reachable point and reachable set, with respect to the pursuit sequence and the weights are shown to exist for these linear cyclic pursuit laws. When the linear system is unstable, the agents are shown to exhibit directed motion. We obtain the conditions under which such directed motion is possible. The straight line asymptote to which the agents converge is characterized by the gains and the pursuit sequence of the agents. The straight lines asymptote always passes through a point, called the asymptote point, for given initial positions and gains of the agents. This invariance property of the asymptote point with respect to the pursuit sequence and the weights are proved. For non-homonymic agents, cyclic pursuit strategies give rise to a system of nonlinear state equations. It is shown that the system at equilibrium converges to a rigid polygonal formation that rotates in space. The agents move in concentric circles at equilibrium. The formation at equilibrium and the conditions for equilibrium are obtained for heterogeneous speeds and controller gains. The application of cyclic pursuit strategies to autonomous vehicles requires the satisfaction of some realistic restrictions like maximum speed limits, maximum latex limits, etc. The performances of the strategies with these limitations are discussed. It is also observed that the cyclic pursuit strategies can also be used to model some behavior of biological organisms such as schools of fishes.