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.

This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded. We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs. Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs. n−1 3 Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs. It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position. Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G). We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.

In this thesis, an approach is presented for the generation of grids suitable for the simulation of high Reynolds number viscous flows in complex three-dimensional geometries. The automatic and reliable generation of such grids is today on the biggest bottlenecks in the industrial CFD simulation environment.<p><p>In the proposed approach, unstructured tetrahedral grids are employed for the regions far from the viscous boundaries of the domain, while semi-structured layers of high aspect ratio prismatic and hexahedral elements are used to provide the necessary grid resolution inside the boundary layers and normal to the viscous walls. The definition of the domain model is based on the STEP ISO standard and the topological information contained in the model is used for applying the hierarchical grid generation parameters defined by the user. An efficient, high-quality and robust algorithm is presented for the generation of the unstructured simplicial (triangular of tetrahedral) part of the grid. The algorithm is based on the Delaunay triangulation and the internal grid points are created following a centroid or frontal approach. For the surface grid generation, a hybrid approach is also proposed similar to the volume.<p>Semi-structured grids are generated on the surface grid (both on the edges and faces of the domain) to improve the grid resolution around convex and concave ridges and corners, by aligning the grid elements in the directions of high solution gradients along the surface. A method is also developed for automatically setting the grid generation parameters related to the surface grid generation based on the curvature of the surface in order to obtain an accurate and smooth surface grid. Finally, a semi-structured prismatic/hexahedral grid generation algorithm is presented for the generation of the part of grid close to the viscous walls of the domain. The algorithm is further extended with improvements meant to increase the grid quality around concave and convex ridges of the domain, where the semi-structured grids are known to be inadequate.<p><p>The combined methodology is demonstrated on a variety of complex examples mainly from the automotive and aeronautical industry. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Cognitive radio (CR) is often described as a context-intelligent radio, capable of changing the transmit parameters dynamically based on the interaction with the environment it operates. The work in this thesis explores the problem of using received signal strength (RSS) measurements taken by a network of CR nodes to generate an interference map of a given geographical area and estimate the locations of multiple primary transmitters that operate simultaneously in the area. A probabilistic model of the problem is developed, and algorithms to address location estimation challenges are proposed. Three approaches are proposed to solve the localization problem. The first approach is based on estimating the locations from the generated interference map when no information about the propagation model or any of its parameters is present. The second approach is based on approximating the maximum likelihood (ML) estimate of the transmitter locations with the grid search method when the model is known and its parameters are available. The third approach also requires the knowledge of model parameters but it is actually based on generating samples from the joint posterior of the unknown location parameter with Markov chain Monte Carlo (MCMC) methods, as an alternative for the highly computationally complex grid search approach. For RF cartography generation problem, we study global and local interpolation techniques, specifically the Delaunay triangulation based techniques as the use of existing triangulation provides a computationally attractive solution. We present a comparative performance evaluation of these interpolation techniques in terms of RF field strength estimation and emitter localization. Even though the estimates obtained from the generated interference maps are less accurate compared to the ML estimator, the rough estimates are utilized to initialize a more accurate algorithm such as the MCMC technique to reduce the complexity of the algorithm. The complexity issues of ML estimators based on full grid search are also addressed by various types of iterative grid search methods. One challenge to apply the ML estimation algorithm to multiple emitter localization problem is that, it requires a pdf approximation to summands of log-normal random variables for likelihood calculations at each grid location. This inspires our investigations on sum of log-normal approximations studied in literature for selecting the appropriate approximation to our model assumptions. As a final extension of this work, we propose our own approximation based on distribution fitting to a set of simulated data and compare our approach with Fenton-Wilkinson's well-known approximation which is a simple and computational efficient approach that fits a log-normal distribution to sum of log-normals by matching the first and second central moments of random variables. We demonstrate that the location estimation accuracy of the grid search technique obtained with our proposed approximation is higher than the one obtained with Fenton-Wilkinson's in many different case scenarios.

No description available.

The dissertation covers phase transitions in the realm of the Anderson model of localization on topologically disordered Voronoi-Delaunay lattices. The disorder is given by random connections which implies correlations due to the restrictive lattice construction. Strictly speaking, the system features "strong anticorrelation", which is responsible for quenched long-range fluctuations of the coordination number. This attribute leads to violations of universal behavior in various system, e.g. Ising and Potts model, and to modifications of the Harris and the Imry-Ma criteria. In general, these exceptions serve to further understanding of critical phenomena. Hence, the question arises whether such deviations also occur in the realm of the Anderson model of localization in combination with random Voronoi-Delaunay lattice. For this purpose, four cases, which are distinguished by the spatial dimension of the systems and by the presence or absence of a magnetic field, are investigated by means of two different methods, i.e the multifractal analysis and the recursive Green function approach. The behavior is classified by the existence and type of occurring phase transitions and by the critical exponent v of the localization length. The results for the four cases can be summarized as follows. In two-dimensional systems, no phase transitions occur without a magnetic field, and all states are localized as a result of topological disorder. The behavior changes under the influence of the magnetic field. There are so-called quantum Hall transitions, which are phase changes between two localized regions. For low magnetic field strengths, the resulting exponent v ≈ 2.6 coincides with established values in literature. For higher strengths, an increased value, v ≈ 2.9, was determined. The deviations are probably caused by so-called Landau level coupling, where electrons scatter between different Landau levels. In contrast, the principle behavior in three-dimensional systems is equal in both cases. Two localization-delocalization transitions occur in each system. For these transitions the exponents v ≈ 1.58 and v ≈ 1.45 were determined for systems in absence and in presence of a magnetic field, respectively. This behavior and the obtained values agree with known results, and thus no deviation from the universal behavior can be observed.:1. Introduction 2. Random Voronoi-Delaunay lattice 2.1. Definition 2.2. Properties 2.3. Numerical construction 3. Anderson localization 3.1. Conventional Anderson transition 3.1.1. Fundamentals 3.1.2. Scaling theory of localization 3.1.3. Universality 3.2. Quantum Hall transition 3.2.1. Universality 3.3. Random Voronoi-Delaunay Hamiltonian 4. Methods 4.1. Multifractal analysis 4.1.1. Fundamentals 4.1.2. Box-size scaling 4.1.3. Partitioning scheme 4.1.4. Numerical realization 4.2. Recursive Green function approach 4.2.1. Fundamentals 4.2.2. Recursive formulation 4.2.3. Layer construction 4.3. Finite-size scaling approach 4.3.1. Scaling functions 4.3.2. Numerical determination 5. Electron behavior on 2D random Voronoi-Delaunay lattices 5.1. 2D orthogonal systems 5.2. 2D unitary systems 5.2.1. Density of states and principal behavior 5.2.2. Criticality in the lowest Landau band 5.2.3. Criticality in higher Landau bands 5.2.4. Edge states 6. Electron behavior on 3D random Voronoi-Delaunay lattices 6.1. 3D orthogonal systems 6.1.1. Pure connectivity disorder 6.1.2. Additional potential disorder 6.2. 3D unitary systems 6.2.1. Pure topological disorder 7. Conclusion Bibliography A. Appendices A.1. Quantum Hall effect on regular lattices A.1.1. Simple square lattice A.1.2. Triangular lattice A.2. Further quantum Hall transitions on 2D random Voronoi-Delaunay lattices Lebenslauf Publications / Diese Dissertation behandelt Phasenübergange im Rahmen des Anderson-Modells der Lokalisierung in topologisch ungeordneten Voronoi-Delaunay-Gittern. Die spezielle Art der Unordnung spiegelt sich u.a. in zufälligen Verknüpfungen wider, welche aufgrund der restriktiven Gitterkonstruktion miteinander korrelieren. Genauer gesagt zeigt das System eine "starke Antikorrelation", die dafür sorgt, dass langreichweitige Fluktuationen der Verknüpfungszahl unterdrückt werden. Diese Eigenschaft hat in anderen Systemen, z.B. im Ising- und Potts-Modell, zur Abweichung vom universellen Verhalten von Phasenübergängen geführt und bewirkt eine Modifikation von allgemeinen Aussagen, wie dem Harris- and Imry-Ma-Kriterium. Die Untersuchung solcher Ausnahmen dient zur Weiterentwicklung des Verständnisses von kritischen Phänomenen. Somit stellt sich die Frage, ob solche Abweichungen auch im Anderson-Modell der Lokalisierung unter Verwendung eines solchen Gitters auftreten. Dafür werden insgesamt vier Fälle, welche durch die Dimension des Gitters und durch die An- bzw. Abwesenheit eines magnetischen Feldes unterschieden werden, mit Hilfe zweier unterschiedlicher Methoden, d.h. der Multifraktalanalyse und der rekursiven Greensfunktionsmethode, untersucht. Das Verhalten wird anhand der Existenz und Art der Phasenübergänge und anhand des kritischen Exponenten v der Lokalisierungslänge unterschieden. Für die vier Fälle lassen sich die Ergebnisse wie folgt zusammenfassen. In zweidimensionalen Systemen treten ohne Magnetfeld keine Phasenübergänge auf und alle Zustände sind infolge der topologischen Unordnung lokalisiert. Unter Einfluss des Magnetfeldes ändert sich das Verhalten. Es kommt zur Ausformung von Landau-Bändern mit sogenannten Quanten-Hall-Übergängen, bei denen ein Phasenwechsel zwischen zwei lokalisierten Bereichen auftritt. Für geringe Magnetfeldstärken stimmen die erzielten Ergebnisse mit den bekannten Exponenten v ≈ 2.6 überein. Allerdings wurde für stärkere magnetische Felder ein höherer Wert, v ≈ 2.9, ermittelt. Die Abweichungen gehen vermutlich auf die zugleich gestiegene Unordnungsstärke zurück, welche dafür sorgt, dass Elektronen zwischen verschiedenen Landau-Bändern streuen können und so nicht das kritische Verhalten eines reinen Quanten-Hall-Überganges repräsentieren. Im Gegensatz dazu ist das Verhalten in dreidimensionalen Systemen für beide Fälle ähnlich. Es treten in jedem System zwei Phasenübergänge zwischen lokalisierten und delokalisierten Bereichen auf. Für diese Übergänge wurde der Exponent v ≈ 1.58 ohne und v ≈ 1.45 unter Einfluss eines magnetischen Feldes ermittelt. Dieses Verhalten und die jeweils ermittelten Werte stimmen mit bekannten Ergebnissen überein. Eine Abweichung vom universellen Verhalten wird somit nicht beobachtet.:1. Introduction 2. Random Voronoi-Delaunay lattice 2.1. Definition 2.2. Properties 2.3. Numerical construction 3. Anderson localization 3.1. Conventional Anderson transition 3.1.1. Fundamentals 3.1.2. Scaling theory of localization 3.1.3. Universality 3.2. Quantum Hall transition 3.2.1. Universality 3.3. Random Voronoi-Delaunay Hamiltonian 4. Methods 4.1. Multifractal analysis 4.1.1. Fundamentals 4.1.2. Box-size scaling 4.1.3. Partitioning scheme 4.1.4. Numerical realization 4.2. Recursive Green function approach 4.2.1. Fundamentals 4.2.2. Recursive formulation 4.2.3. Layer construction 4.3. Finite-size scaling approach 4.3.1. Scaling functions 4.3.2. Numerical determination 5. Electron behavior on 2D random Voronoi-Delaunay lattices 5.1. 2D orthogonal systems 5.2. 2D unitary systems 5.2.1. Density of states and principal behavior 5.2.2. Criticality in the lowest Landau band 5.2.3. Criticality in higher Landau bands 5.2.4. Edge states 6. Electron behavior on 3D random Voronoi-Delaunay lattices 6.1. 3D orthogonal systems 6.1.1. Pure connectivity disorder 6.1.2. Additional potential disorder 6.2. 3D unitary systems 6.2.1. Pure topological disorder 7. Conclusion Bibliography A. Appendices A.1. Quantum Hall effect on regular lattices A.1.1. Simple square lattice A.1.2. Triangular lattice A.2. Further quantum Hall transitions on 2D random Voronoi-Delaunay lattices Lebenslauf Publications

在無線網狀網路(Wireless Mesh Network)中，每個節點須幫助相鄰節點轉送資料及提供使用者網路存取，例如WLAN(IEEE 802.11s)、WMAN(IEEE 802.16)等，皆可利用多跳接方式將資料轉送至通訊閘道器(Gateway)。在無線網狀網路中，常利用密集佈建的方式來解決通訊死角的問題。當網路節點的密度增加時，無線訊號的干擾也會增強，並且各節點的效能會顯著下降。 在本研究中，將利用幾何學概念，解決網路干擾問題，並提出拓樸重建演算法來重建路徑，使網路干擾達到最小化。我們試著最小化節點與節點間的干擾，以提升整體無線網狀網路效能。我們將網路問題轉換成幾何問題，並定義在幾何圖形中線段交錯問題，之後驗證在幾何圖形中是否有線段交錯的現象發生。若發生線段交錯時，則將此線段從幾何圖形中移除，並且利用三角化演算法將此區域線段重新規劃，使相鄰節點間的干擾最小。當網路拓樸建立完成後，我們利用標準差公式將干擾較大的連線移除，使得網路效能提升。上述測試線段交錯及三角化多邊形演算法可在時間複雜度O(n log n)內找到干擾最小的解。最後，我們將利用網路模擬器(Network Simulator)驗證所提出的方法是否能達到預期的系統效能指標。 / In wireless mesh networks, such as WLAN (IEEE 802.11s), WMAN (IEEE 802.16), etc., each node should forward packets of neighboring nodes toward gateway using multi-hop routing mechanism. In wireless mesh network, as the density of network nodes increases, the RF interference will increase and the throughput of each node will drop rapidly. In our research, we use the geometry to resolve the RF interference problem by rebuilding network topology. We try to minimize the interference between neighboring nodes and improve the throughput in wireless mesh network. We transform the network topology problem into geometry problem and define the line intersection problem in geometric graph, then check path intersection in the geometric graph. If line intersection occurs in the graph, we remove the intersection line from the graph and re-plan the region by triangulation algorithm. When the network topology is built up, we use a standard deviation formula to improve network performance by removing longer links. The line intersection algorithm and triangulation algorithm, both of time complexity O(n log n), are used to find the minimal interference solution. At the end of our research, we use network simulator to verify if the proposed methods can help to meet all those performance expectations.

Le travail de recherche de cette thèse de doctorat s'inscrit dans le cadre du suivi médical des patients atteints de démences liées à l'âge à l'aide des caméras videos portées par les patients. L'idée est de fournir aux médecins un nouvel outil pour le diagnostic précoce de démences liées à l'âge telles que la maladie d'Alzheimer. Plus précisément, les Activités Instrumentales du Quotidien (IADL : Instrumental Activities of Daily Living en anglais) doivent être indexées automatiquement dans les vidéos enregistrées par un dispositif d'enregistrement portable. Ces vidéos présentent des caractéristiques spécifiques comme de forts mouvements ou de forts changements de luminosité. De plus, la tâche de reconnaissance visée est d'un très haut niveau sémantique. Dans ce contexte difficile, la première étape d'analyse est la définition d'un équivalent à la notion de " plan " dans les contenus vidéos édités. Nous avons ainsi développé une méthode pour le partitionnement d'une vidéo tournée en continu en termes de " points de vue " à partir du mouvement apparent. Pour la reconnaissance des IADL, nous avons développé une solution selon le formalisme des Modèles de Markov Cachés (MMC). Un MMC hiérarchique à deux niveaux a été introduit, modélisant les activités sémantiques ou des états intermédiaires. Un ensemble complexe de descripteurs (dynamiques, statiques, de bas niveau et de niveau intermédiaire) a été exploité et les espaces de description joints optimaux ont été identifiés expérimentalement. Dans le cadre de descripteurs de niveau intermédiaire pour la reconnaissance d'activités nous nous sommes particulièrement intéressés aux objets sémantiques que la personne manipule dans le champ de la caméra. Nous avons proposé un nouveau concept pour la description d'objets ou d'images faisant usage des descripteurs locaux (SURF) et de la structure topologique sous-jacente de graphes locaux. Une approche imbriquée pour la construction des graphes où la même scène peut être décrite par plusieurs niveaux de graphes avec un nombre de nœuds croissant a été introduite. Nous construisons ces graphes par une triangulation de Delaunay sur des points SURF, préservant ainsi les bonnes propriétés des descripteurs locaux c'est-à-dire leur invariance vis-à-vis de transformations affines dans le plan image telles qu'une rotation, une translation ou un changement d'échelle. Nous utilisons ces graphes descripteurs dans le cadre de l'approche Sacs-de-Mots-Visuels. Le problème de définition d'une distance, ou dissimilarité, entre les graphes pour la classification non supervisée et la reconnaissance est nécessairement soulevé. Nous proposons une mesure de dissimilarité par le Noyau Dépendant du Contexte (Context-Dependent Kernel : CDK) proposé par H. Sahbi et montrons sa relation avec la norme classique L2 lors de la comparaison de graphes triviaux (les points SURF). Pour la reconnaissance d'activités par MMC, les expériences sont conduites sur le premier corpus au monde de vidéos avec caméra portée destiné à l'observation des d'IADL et sur des bases de données publiques comme SIVAL et Caltech-101 pour la reconnaissance d'objets.

Dans cette thèse, nous étudions les problèmes de reconstruction statique et dynamique à partir de vues multiples et texturation, en s'appuyant sur des applications réelles et pratiques. Nous proposons trois méthodes de reconstruction destinées à l'estimation d'une représentation d'une scène statique/dynamique à partir d'un ensemble d'images/vidéos. Nous considérons ensuite le problème de texturation multi-vues en se concentrant sur la qualité visuelle de rendu..

De plus en plus d'applications ont pour objectif d'automatiser l'analyse des comportements humains afin d'aider ou de remplacer les experts qui réalisent actuellement ces analyses. Cette thèse traite de l'analyse des expressions faciales qui fournissent des informations clefs sur ces comportements. Les travaux réalisés portent sur une solution innovante permettant de définir efficacement une expression d'un visage, indépendamment de la morphologie du sujet. Pour s'affranchir des différences de morphologies entre les personnes, nous utilisons des modèles d'apparence spécifiques à la personne. Nous proposons une solution qui permet à la fois de tenir compte de l'aspect continu de l'espace des expressions et de la cohérence des différentes parties du visage entre elles. Pour ce faire, nous proposons une approche originale basée sur l'organisation des expressions. Nous montrons que l'organisation des expressions, telle que définie, est universelle et qu'elle peut être efficacement utilisée pour définir de façon unique une expression : une expression est caractérisée par son intensité et sa position relative par rapport aux autres expressions. La solution est comparée aux méthodes classiques basées sur l'apparence et montre une augmentation significative des résultats de reconnaissance sur 14 expressions non basiques. La méthode a été étendue à des sujets inconnus. L'idée principale est de créer un espace d'apparence plausible spécifique à la personne inconnue en synthétisant ses expressions basiques à partir de déformations apprises sur d'autres sujets et appliquées sur le neutre du sujet inconnu. La solution est aussi mise à l'épreuve dans un environnement multimodal plus complet dont l'objectif est la reconnaissance d'émotions lors de conversations spontanées. Les résultats montrent que la solution est efficace sur des données réelles et qu'elle permet l'extraction d'informations essentielles à l'analyse des émotions. Notre méthode a été mise en œuvre dans le cadre du challenge international AVEC 2012 (Audio/Visual Emotion Challenge) où nous avons fini 2nd, avec des taux de reconnaissance très proches de ceux obtenus par les vainqueurs. La comparaison des deux méthodes (la nôtre et celles des vainqueurs) semble montrer que l'extraction des caractéristiques pertinentes est la clef de tels systèmes.