Dans de nombreux domaines d'applications, une variété plongée dans l'espace euclidien est souvent représentée par un échantillon de points. Nous définissons dans cette thèse un système de coordonnées associé à un tel échantillon sur la variété qui généralise les coordonnées naturelles définies par Sibson. Nous exhibons ses propriétés mathématiques fondamentales ainsi que son application à l'interpolation d'une fonction définie sur la variété. Nous introduisons la notion d'atlas de Voronoï, défini comme un ensemble de cellules approximant le diagramme de Voronoï restreint à la variété et montrons son application à la reconstruction de surface et au remaillage. Enfin, nous étendons les propriétés des coordonnées naturelles aux diagrammes de puissance et proposons une synthèse des méthodes d'interpolation par coordonnées naturelles. Cette dernière détaille des preuves omises dans les articles originaux.

Un robot manipulateur parallèle est composé de deux solides, une plate-forme et une base, reliés par des chaînes cinématiques articulées et motorisées permettant leur mouvement relatif. Le problème du modèle géométrique direct des robots parallèles est essentiel. Il consiste a déterminer la position et l'orientation de la plate-forme par rapport a un repère de base lorsque les variables articulaires sont fixées. Ce problème revient a considérer le placement d'un solide quelconque sur six sphères de rayons et de centres fixés. Il présente deux facettes, une géométrique et l'autre algébrique, menant a diverses méthodes à mettre en oeuvre. Le modèle géométrique direct est connu pour admettre au plus quarante solutions complexes. Nous présentons une approche consistant a utiliser des capteurs additionnels pour simplifier et résoudre ce problème. Nous utilisons ou développons toute une gamme de méthodes symboliques et parfois numériques permettant la résolution dans ce contexte précis. Les résultats obtenus permettent de définir des architectures de robot ayant un nombre minimum de solutions pour la résolution du modèle géométrique direct, Voire même des solutions explicites ou uniques.

Aquesta tesi tracta del disseny, implementació i discussió d'algoritmes per resoldre problemes de visibilitat i bona-visibilitat utilitzant el hardware gràfic de l'ordinador. Concretament, s'obté una discretització dels mapes de multi-visibilitat i bona-visibilitat a partir d'un conjunt d'objectes de visió i un conjunt d'obstacles. Aquests algoritmes són útils tant per fer càlculs en dues dimensions com en tres dimensions. Fins i tot ens permeten calcular-los sobre terrenys. / In this thesis we design, implement and discuss algorithms that run in the graphics hardware for solving visibility and good-visibility problems. In particular, we compute a discretization of the multi-visibility and good-visibility maps from a set of view objects (points or segments) and a set of obstacles. This computation is carried out for two-dimensional and three-dimensional spaces and even over terrains, which in computational geometry are defined as a 2.5D space.

Αυτή η Διδακτορική Διατριβή πραγματεύεται το θέμα της ομαδοποίησης δεδομένων (clustering), καθώς και εφαρμογές των τεχνικών αυτών σε πραγματικά προβλήματα. Η παρουσίαση των επιμέρους θεμάτων και αποτελεσμάτων της διατριβής αυτής οργανώνεται ως εξής: Στο Κεφάλαιο 1 παρέχουμε τον ορισμό της Υπολογιστικής Νοημοσύνης σαν τομέας ερευνάς, και αναλύουμε τα ξεχωριστά τμήματα που τον αποτελούν. Για κάθε ένα από αυτά παρουσιάζεται μια σύντομη περιγραφή. Το Κεφάλαιο 2, ασχολείται με την ανάλυση του ερευνητικού πεδίου της ομαδοποίησης. Κάθε ένα από τα χαρακτηριστικά της αναλύεται ξεχωριστά και γίνεται μια επισκόπηση των σημαντικότερων αλγόριθμων ομαδοποίησης. Το Κεφάλαιο 3, αφιερώνεται στη παρουσίαση του αλγορίθμου UKW, που κατά την εκτέλεση του έχει την ικανότητα να προσεγγίζει το πλήθος των ομάδων σε ένα σύνολο δεδομένων. Επίσης παρουσιάζονται πειραματικά αποτελέσματα με σκοπό τη μελέτη της απόδοσης του αλγορίθμου. Στο Κεφάλαιο 4, προτείνεται μια επέκταση του αλγορίθμου UKW, σε μετρικούς χώρους. Η προτεινόμενη επέκταση διατηρεί όλα τα πλεονεκτήματα του αλγορίθμου UKW. Τα πειραματικά αποτελέσματα που παρουσιάζονται επίσης σε αυτό το κεφάλαιο, συγκρίνουν την προτεινόμενη επέκταση με άλλους αλγορίθμους. Στο επόμενο κεφάλαιο παρουσιάζουμε τροποποιήσεις του αλγορίθμου με στόχο την βελτίωση των αποτελεσμάτων του. Οι προτεινόμενες τροποποιήσεις αξιοποιούν πληροφορία από τα τοπικά χαρακτηριστικά των δεδομένων, ώστε να κατευθύνουν όσο το δυνατόν καλύτερα την αλγοριθμική διαδικασία. Το Κεφάλαιο 6, πραγματεύεται επεκτάσεις του αλγορίθμου σε κατανεμημένες Βάσεις δεδομένων. Για τις διάφορες υποθέσεις που μπορούν να γίνουν όσον αφορά τη φύση του περιβάλλοντος επικοινωνίας, παρουσιάζονται κατάλληλοι αλγόριθμοι. Στο Κεφάλαιο 7, εξετάζουμε την περίπτωση δυναμικών βάσεων δεδομένων. Σε ένα τέτοιο μη στατικό περιβάλλον αναπτύσσεται μια επέκταση του αλγορίθμου UKW, που ενσωματώνει τη δυναμική δομή δεικτοδότησης Bkd-tree. Επιπλέον παρουσιάζονται θεωρητικά αποτελέσματα για την πολυπλοκότητα χειρότερης περίπτωσης του αλγορίθμου. Το Κεφάλαιο 8, μελετά την εφαρμογή αλγορίθμων ομαδοποίησης σε δεδομένα γονιδιακών εκφράσεων. Επίσης προτείνεται και αξιολογείται ένα υβριδικό σχήμα που καταφέρνει να αυτοματοποιήσει την όλη διαδικασία επιλογής γονιδίων και ομαδοποίησης. Τέλος, η παρουσίαση του ερευνητικού έργου αυτής της διατριβής ολοκληρώνεται στο Κεφάλαιο 9 που ασχολείται με την ανάπτυξη υβριδικών τεχνικών που συνδυάζουν την ομαδοποίηση και τα Τεχνητά Νευρωνικά Δίκτυα, και αναδεικνύει τις δυνατότητες τους σε δύο πραγματικά προβλήματα. / This Doctoral Dissertation appoints the issue of data Clustering, as well as the applications of these kind of methods in real world problems. The presentation of the individual results of this dissertation is organised as follows: In Chapter 1, the definition of Computational Intelligence is provided as a research area. For each distinct part of this area a short description is supplied. Chapter 2, deals with the analysis of the research area of Clustering per se, and its characteristics are analysed separably. Moreover, we provide a review of the most representative clustering algorithms. Chapter 3, is devoted to the presentation of the UKW algorithm, that is able to endogenously provide approximations for the number of clusters in a dataset, during its execution. Furthermore, the included experimental results demonstrate the algorithm's efficiency. In Chapter 4, an extension of the UKW algorithm to metric spaces is proposed. This extension preserves all the advantages of the original algorithm. The included experimental results compare the proposed extension to other approaches. In the next chapter we present modifications of the UKW algorithm that scope to improve its efficiency. This is performed through the utilisation of information from the local characteristics of the data, so as to direct more efficiently the whole clustering procedure. Chapter 6, deals with extensions of the algorithm in distributed data bases. For the various assumptions that can be postulated for the nature of the communication environment different algorithms are proposed. In Chapter 7, we consider the case of dynamic databases. In such a non-static environment, an algorithm is developed that draws form the principles of the UKW algorithm, and embodies the dynamic indexing Bkd-tree data structure. Moreover, theoretical results are presented regarding the worst case complexity of the algorithm. Chapter 8, studies the application of clustering algorithms in gene expression data. Besides, it is proposed and evaluated, a hybrid algorithmic scheme that manages to automate the whole procedure of gene selection and clustering. Finally, the presentation of the research work of this dissertation is fulfilled in Chapter 9. This Chapter is devoted to the development of hybrid techniques that combine clustering methods and Artificial Neural Networks, and demonstrate their abilities in two real world problems.

Depuis quelques années, l'évolution des techniques d'acquisition a entraîné une généralisation de l'utilisation d'objets 3D très dense, représentés par des nuages de points de plusieurs millions de sommets. Au vu de la complexité de ces données, il est souvent nécessaire de les analyser pour en extraire les structures les plus pertinentes, potentiellement définies à plusieurs échelles. Parmi les nombreuses méthodes traditionnellement utilisées pour analyser des signaux numériques, l'analyse dite scale-space est aujourd'hui un standard pour l'étude des courbes et des images. Cependant, son adaptation aux données 3D pose des problèmes d'instabilité et nécessite une information de connectivité, qui n'est pas directement définie dans les cas des nuages de points. Dans cette thèse, nous présentons une suite d'outils mathématiques pour l'analyse des objets 3D, sous le nom de Growing Least Squares (GLS). Nous proposons de représenter la géométrie décrite par un nuage de points via une primitive du second ordre ajustée par une minimisation aux moindres carrés, et cela à pour plusieurs échelles. Cette description est ensuite derivée analytiquement pour extraire de manière continue les structures les plus pertinentes à la fois en espace et en échelle. Nous montrons par plusieurs exemples et comparaisons que cette représentation et les outils associés définissent une solution efficace pour l'analyse des nuages de points à plusieurs échelles. Un défi intéressant est l'analyse d'objets 3D acquis dans le cadre de l'étude du patrimoine culturel. Dans cette thèse, nous nous étudions les données générées par l'acquisition des fragments des statues entourant par le passé le Phare d'Alexandrie, Septième Merveille du Monde. Plus précisément, nous nous intéressons au réassemblage d'objets fracturés en peu de fragments (une dizaine), mais avec de nombreuses parties manquantes ou fortement dégradées par l'action du temps. Nous proposons un formalisme pour la conception de systèmes d'assemblage virtuel semi-automatiques, permettant de combiner à la fois les connaissances des archéologues et la précision des algorithmes d'assemblage. Nous présentons deux systèmes basés sur cette conception, et nous montrons leur efficacité dans des cas concrets.

L'ensemble des thématiques abordées s'inscrivent dans le contexte de la modélisation et du calcul géométrique.

De nos jours, les objets virtuels sont devenus omniprésents. On les trouve dans de nombreux domaines comme le divertissement (cinéma, jeux vidéo, etc.), la conception assistée par ordinateur ou encore la réalité virtuelle. Nous nous intéressons en particulier à la modélisation d'objets 3D dans le domaine de la création artistique. Ici, la création d'images riches nécessite de faire appel à des modèles très détaillés et donc extrêmement complexes. Les surfaces de subdivision, traditionnellement utilisées dans ces domaines, voient leur complexité croître rapidement lorsqu'on ajoute des détails, et la gestion de la connectivité du maillage de contrôle devient trop contraignante. Une approche standard pour gérer la complexité de tels modèles est d'utiliser des représentations différentes pour la forme générale de la surface et les détails. Cependant, ces détails sont représentés par des cartes matricielles qui ne possèdent pas la plupart des avantages des représentations vectorielles, et cela complexifie certaines tâches, comme par exemple l'animation. Dans cette thèse, nous proposons deux nouvelles représentations vectorielles, la première pour les surfaces de base, la deuxième pour les détails. Nous utilisons pour cette dernière une représentation vectorielle appelée images de diffusion permettant de créer des variations lisses à l'aide d'un ensemble réduit de contraintes. Cela nous permet de représenter aussi bien la géométrie que la couleur ou d'autres paramètres nécessaires au rendu de façon purement vectoriel, en conservant des contrôles de haut niveau. Notre première contribution est une représentation de surfaces, baptisée LS3, issue de la combinaison entre surfaces de subdivision et -point set surfaces. Cette approche réduit notablement les artefacts des surfaces de subdivision aux alentours de sommets dits extraordinaires, qui sont connus pour poser problème. Nous présentons une analyse numérique des propriétés de ces surfaces, qui tend à montrer que du point de vue de la continuité elles se comportent au moins aussi bien que les schémas de subdivision linéaires traditionnels. Notre deuxième contribution est un solveur pour les images de diffusion dont le principal avantage est de produire en sortie une autre représentation vectorielle légère et très rapide à évaluer. Nous illustrons la force de note solveur sur de nombreux exemples difficiles ou impossibles à réaliser avec les méthodes précédentes. Pour conclure, nous montrons comment combiner nos deux contributions pour obtenir une représentation de surface entièrement vectorielle capable de représenter des détails sans avoir à manipuler la connectivité d'un maillage.

Un problème fondamental en géométrie algorithmique est celui du calcul de la topologie d'une courbe plane donnée par son équation implicite. Ce problème peut être vu comme celui du calcul d'un graphe qui approche la courbe et qui possède la même topologie que cette dernière. Une étape importante dans les algorithmes calculant la topologie d'une courbe plane concerne le calcul des points singuliers et points extrêmes (en x) de celle-ci. Ce problème se ramène naturellement à celui de la résolution de systèmes bivariés définis par la courbe et ses dérivées par rapport aux variables qui la définissent. Cette thèse porte sur l'étude, l'élaboration et l'implantation d'algorithmes robustes et efficaces pour la résolution de systèmes définis par des polynômes en deux variables à coefficients entiers. Plus précisément, nous nous somme intéressé au calcul d'une Représentation Univariée Rationnelle des solutions. Une telle représentation est constitué d'un polynôme univarié et de deux fonctions rationnelles qui envois les racines du polynôme univarié sur les coordonnées des points solutions du système. Nous présentons dans un premier temps un algorithme théorique pour calculer la RUR d'un système bivarié qui améliore la meilleure borne de complexité connue d'un facteur d^2, ou d désigne le degré des polynômes de départ, et qui permet d'obtenir une nouvelle borne sur la taille des polynômes de cette RUR. Dans un second temps, nous présentons un algorithme de calcul de RUR efficace en pratique. Cet algorithme, basé sur des choix aléatoires et sur l'utilisation du calcul multi-modulaire est probabiliste. Nous en présentons une première version Monte-Carlo, puis nous montrons comment tester la correction du résultat ce qui fourni un algorithme Las-Vegas. Cet algorithme est efficace à la fois en théorie et en pratique à en juger par l'analyse de complexité en moyenne et les nombreux testes effectués.

An Euler diagram C = {c_1, c_2,..., c_n} is a collection of n simple closed curves (i.e., Jordan curves) that partition the plane into connected subsets, called regions, each of which is enclosed by a unique combination of curves. Typically, Euler diagrams are used to visualize the distribution of discrete characteristics across a sample population; in this case, each curve represents a characteristic and each region represents the sub-population possessing exactly the combination of containing curves' properties. Venn diagrams are a subclass of Euler diagrams in which there are 2^n regions representing all possible combinations of curves (e.g., two partially overlapping circles). In this dissertation, we study the Euler Diagram Generation Problem (EDGP), which involves constructing an Euler diagram with a prescribed set of regions. We describe a graph-theoretic model of an Euler diagram's structure and use this model to develop necessary-and-sufficient existence conditions. We also use the graph-theoretic model to prove that the EDGP is NP-complete. In addition, we study the related Area-Proportional Euler Diagram Generation Problem (w-EDGP), which involves constructing an Euler diagram with a prescribed set of regions, each of which has a prescribed area. We develop algorithms for constructing area-proportional Euler diagrams composed of up to three circles and rectangles, as well as diagrams with an unbounded number of curves and a region of common intersection. Finally, we present implementations of our algorithms that allow the dynamic manipulation and real-time construction of area-proportional Euler diagrams.

TEIXEIRA, Daniel Nascimento. Uma técnica de decomposição a priori para geração paralela de malhas bidimensionais. 2014. 94 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-15T19:57:36Z No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-15T19:58:41Z (GMT) No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Made available in DSpace on 2016-06-15T19:58:41Z (GMT). No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) Previous issue date: 2014 / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits. / Este trabalho descreve uma técnica de decomposição de domínios bidimensionais para geração em paralelo de malhas. Esta técnica funciona tanto para memória distribuída quanto compartilhada, além de permitir que se utilize qualquer estrutura de dados que gere regiões quadrangulares paralelas aos eixos para decompor o domínio dado como entrada. Pode se utilizar por exemplo, uma árvore quaternária (quadtree) ou uma partição binária do espaço (bsp). Além disso, qualquer processo de geração de malha que respeite os pré-requisitos estabelecidos pode ser empregado nos subdomínios criados, como as técnicas de Delaunay ou Avanço de Fronteira, dentre outras. A técnica proposta é dita a priori porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomínio é feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nível de refinamento orienta a criação das arestas que são definidas a partir da discretização das fronteiras das células internas. Essa maneira de estimar carga produz resultados que representam, com boa precisão, o número de elementos a serem gerados em cada subdomínio. Isso contribui para um bom particionamento do domínio, fazendo com que a geração de malha em paralelo seja significativamente mais rápida do que a geração serial. Além disso, a qualidade da malha gerada em paralelo é qualitativamente equivalente àquela gerada serialmente, dentro de limites aceitáveis.