No description available.

No description available.

Arbetet undersökte om det är möjligt att procedurellt generera giltiga och underhållande racerbanor för Formel 1 genom användandet av Voronoi diagram och self-avoiding random walk. En procedurell algoritm skapades och två enkäter konstruerades för att undersöka denna algoritms underhållningsvärde. Dessa enkäter distribuerades till kunniga individer inom racinggenren. Både algoritmen som helhet och dess dynamiska parametrar undersöktes. Det fastställdes att det är möjligt att procedurellt generera Formel 1 racerbanor som är underhållande med detta tillvägagångssätt. Vidare visar resultatet att en stor del av svarspersonerna finner artefaktens procedurella racerbanor underhållande, även i kontrast till riktiga racerbanor. Gynnsamma värden för artefaktens dynamiska parametrar i mån av ökad underhållning har också fastställts. En mer omfattande algoritm kan skapas utifrån detta arbete som tar hänsyn till exempelvis höjdskillnader och camber. Framtida arbeten kan då undersöka dessa delar av en racerbanas underhållningsvärde. Algoritmen kan även jämföras med andra procedurella metoder inom racing och andra spel. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p>

An image is a set of quantized intensity values that are sampled at a finite set of sample points on a two-dimensional plane. Images are crucial to many application areas, such as computer graphics and pattern recognition, because they discretely represent the information that the human eyes interpret. This thesis considers the use of triangular meshes for approximating intensity images. With the help of the wavelet-based analysis, triangular meshes can be efficiently constructed to approximate the image data. In this thesis, this study will focus on local image enhancement and mesh simplification operations, which try to minimize the total error of the reconstructed image as well as the number of triangles used to represent the image. The study will also present an optimal procedure for selecting triangle types used to represent the intensity image. Besides its applications to image and video compression, this triangular representation is potentially very useful for data storage and retrieval, and for processing such as image segmentation and object recognition. / Master of Science

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

La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.<br /><br />Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.<br /><br />L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.<br /><br />La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).<br /><br />Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.

La génomique structurale a donnée accès à un nombre remarquable d'informations sur le protéome. De nature essentiellement combinatoire---il apparaît que certaines protéines interagissent en complexe, elles gagnent à être complémentées par des modèles tridimensionnels pour étendre la connaissance jusqu'au niveau structural. Récemment, de tels modèles ont été reconstruits pour le pore nucléaire, en intégrant diverses données biophysiques et biochimiques. Cependant, la nature qualitative de ces modèles empêche une complète synergie entre ceux-ci et les données expérimentales. Cette thèse propose trois développements répondant à ces limitations. Premièrement, nous introduisons les modèles tolérancés pour représenter des formes aux contours incertains par un continuum de modèles. Nous montrons qu'un modèle tolérancé est équivalent à un diagramme de Voronoi additif multiplicatif, et nous développons le lambda-complexe, l'équivalent de l'alpha-complexe, pour un tel diagramme. Deuxièmement, nous utilisons les modèles tolérancés pour représenter des assemblages protéiques. Nous expliquons comment un modèle tolérancé peut être utilisé pour évaluer la stabilité des contacts entre les protéines et pour valider la cohérence d'un tel modèle vis à vis de données expérimentales. Troisièmement, nous proposons des outils pour comparer des graphes de contact entre protéines, issus d' une part d'un modèle tolérancé, et d'autre part d'un modèle connu à résolution atomique. L'ensemble de ces concepts et outils est utilisé pour sonder les reconstructions du pore nucléaire mentionnées ci-dessus.

Les travaux effectués lors de cette thèse concernent principalement la triangulation de Delaunay. On montre que la complexité en moyenne - en termes de sites inachevés - du processus de fusion multidimensionnelle dans l'hypothèse de distribution quasi-uniforme dans un hypercube est linéaire en moyenne. Ce résultat général est appliqué au cas du plan et permet d'analyser de nouveaux algorithmes de triangulation de Delaunay plus performants que ceux connus à ce jour. Le principe sous-jacent est de diviser le domaine selon des arbres bidimensionnels (quadtree, 2d-tree, bucket-tree. . . ) puis de fusionner les cellules obtenues selon deux directions. On étudie actuellement la prise en compte de contraintes directement pendant la phase de triangulation avec des algorithmes de ce type. De nouveaux algorithmes pratiques de localisation dans une triangulation sont proposés, basés sur la randomisation à partir d'un arbre binaire de recherche dynamique de type AVL, dont l'un est plus rapide que l'algorithme optimal de Kirkpatrick, au moins jusqu'à 12 millions de sites K Nous travaillons actuellement sur l'analyse rigoureuse de leur complexité en moyenne. Ce nouvel algorithme est utilisé pour construire " en-ligne " une triangulation de Delaunay qui est parmi les plus performantes des méthodes " en-ligne " connues à ce jour.

Cette thèse introduit une nouvelle approche pour la reconstruction de surface à partir d'acquisitions de nuages de points. Cette approche construit un complexe cellulaire à partir du nuage de points puis formule la reconstruction comme un problème d'étiquetage binaire des cellules de ce complexe sous un ensemble de contraintes de visibilité. La résolution du problème se ramène alors au calcul d'une coupe minimale s-t permettant d'obtenir efficacement une surface optimale d'après ces contraintes. Dans la première partie de cette thèse, l'approche est utilisée pour la reconstruction générique de surface. Une première application aboutit à un algorithme très robuste de reconstruction de surface à partir de nuages denses issus d'acquisitions laser. Une seconde application utilise une variante de cet algorithme au sein d'une chaîne de photo-modélisation en combinaison avec un raffinement variationnel photométrique. La chaîne complète est adaptée à la reconstruction de scènes de grande échelle et obtient d'excellents résultats en terme de complétude et de précision des reconstructions. La seconde partie de cette thèse considère le problème de la reconstruction directe de modèles géométriques simples à partir de nuages de points. Un algorithme robuste est proposé pour décomposer hiérarchiquement des nuages de points denses en formes issues d'un ensemble restreint de classes de formes. Lorsque que cet ensemble de classes est réduit aux plans seulement, la reconstruction de modèles de très faible complexité est possible. Une extension à d'autres classes de formes échange cet avantage contre la gestion de nuages de points plus difficiles.

Cette these est axee sur la cooperation entre l'analyse d'images et la geometrie algorithmique sur la base des diagrammes de Voronoi et de Delaunay. Le propos de l'analyse d'images est la description du contenu d'une image,en vue de son interpretation et d'une prise de decision. La geometrie algorithmique quant a elle consiste a trouver des algorithmes efficaces en vue de resoudre des problemes a caractere geometrique. Nous nous interesserons ici au probleme de representation des images par des partitionnements plus ou moins complexes, adaptes ou non au contenu informatif des images. Parmi ces partitionnements, nous developperons plus particulierement celui en regions de Voronoi. Nous aborderons ensuite le probleme du codage de formes tridimensionnelles par leur squelette qui est lie aux diagramme de Voronoi Generalise 3D. Nous montrerons enfin comment utiliser les partitionnements en region de Voronoi dans un contexte pyramidal controle par un reseau de Hopfield en vue de la segmentation, et dans un contexte markovien en vue de trouver un partitionnement repondant a une certaine optimalite.