• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 10
  • 2
  • Tagged with
  • 12
  • 12
  • 5
  • 5
  • 5
  • 4
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Analyse de complexité d'enveloppes convexes aléatoires / Complexity analysis of random convex hulls

Thomasse, Rémy 18 December 2015 (has links)
Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGAL. / In this thesis, we give some new results about the average size of convex hulls made of points chosen in a convex body. This size is known when the points are chosen uniformly (and independently) in a convex polytope or in a "smooth" enough convex body. This average size is also known if the points are independently chosen according to a centered Gaussian distribution. In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and a upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2. The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases. In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in C++ and integrated in the CGAL library.
2

Modélisation et optimisation numérique pour la reconstruction d'un polyèdre à partir de son image gaussienne généralisée

Zouaki, Hamid 04 July 1991 (has links) (PDF)
On présente un algorithme, pour retrouver la représentation surfacique d'un polyèdre convexe a partir de la donnée de son image gaussienne généralisée, notée e.g.i. Cet algorithme base sur un théorème de Minkowski, est du a J. J. Little (1983). Cette reconstruction d'un polyèdre a partir de son e.g.i., se fera via la resolution d'un probleme d'optimisation convexe. Après avoir défini l'e.g.i. Comme mode de représentation d'objets convexes, ainsi que les propriétés qu'elle possède, nous détaillons la methode de reconstruction. Des améliorations sont introduites, allant dans le sens de rendre l'algorithme suffisamment efficace. Le schéma général de l'algorithme est présenté, avec des commentaires sur le traitement numérique. Enfin, quelques exemples sont fournis, pour illustrer la methode
3

Simplification polyédrique optimale pour le rendu

Charrier, Emilie 04 December 2009 (has links) (PDF)
En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure
4

Différentes propriétés de marches aléatoires avec contraintes géométriques et dynamiques / Different properties of random walks under geometric and dynamic constraints

Chupeau, Marie 05 July 2016 (has links)
Nous déterminons d’abord l’impact d’un plan infini réfléchissant sur l’espace occupé par une marche brownienne bidimensionnelle à un temps fixé, que nous caractérisons par le périmètre moyen de son enveloppe convexe (plus petit polygone convexe contenant toute la trajectoire). Nous déterminons également la longueur moyenne de la portion du plan visitée par le marcheur, et la probabilité de survie d’un marcheur brownien dans un secteur angulaire absorbant.Nous étudions ensuite le temps mis par un marcheur sur réseau pour visiter tous les sites d’un volume, ou une partie d’entre eux. Nous calculons la moyenne de ce temps, dit de couverture, à une dimension pour une marche aléatoire persistante. Nous déterminons également la distribution du temps de couverture et d’autres observables assimilées pour la classe des processus non compacts, qui décrivent un large spectre de recherches aléatoires.Dans un troisième temps, nous calculons et analysons la probabilité de sortie conditionnelle d’un marcheur brownien évoluant dans un intervalle se dilatant ou se contractant à vitesse constante.Enfin, nous étudions plusieurs aspects du modèle du marcheur aléatoire “affamé”, qui meurt si les visites de nouveaux sites, grâce auxquelles il engrange des ressources, ne sont pas suffisamment regulières. Nous en proposons un traitement de type champ moyen à deux dimensions, puis nous déterminons l’impact de la régénération des ressources sur les propriétés de survie du marcheur. Nous considérons finalement un modèle d’exploitation de parcelles de nourriture prenant explicitement en compte le mouvement du marcheur, qui se ramène de manière naturelle au modèle du marcheur aléatoire affamé. / We first determine the impact of an infinite reflecting wall on the space occupied by a planar Brownian motion at a fixed observation time. We characterize it by the mean perimeter of its convex hull, defined as the minimal convex polygon enclosing the whole trajectory. We also determine the mean length of the visited portion of the wall, and the survival probability of a Brownian walker in an absorbing wedge.We then study the time needed for a lattice random walker to visit every site of a confined volume, or a fraction of them. We calculate the mean value of this so-called cover time in one dimension for a persistant random walk. We also determine the distribution of the cover time and related observables for the class of non compact processes, which describes a wide range of random searches.After that, we calculate and analyze the splitting probability of a one-dimensional Brownian walker evolving in an expanding or contracting interval.Last, we study several aspects of the model of starving random walk, where the walker starves if its visits to new sites, from which it collects resources, are not regular enough. We develop a mean-field treatment of this model in two dimensions, then determine the impact of regeneration of resources on the survival properties of the walker. We finally consider a model of exploitation of food patches taking explicitly into account the displacement of the walker in the patches, which can be mapped onto the starving random walk model.
5

Diagramme de Voronoi généralisé pour un ensemble de polygones : algorithmes, réalisation et application en analyse de formes

Hu, Hai-Tao 01 July 1991 (has links) (PDF)
.
6

Courbes de Bézier en géométrie algorithmique : approximation et cohérence topologique

Neagu, Manuela 05 May 1998 (has links) (PDF)
Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.
7

Enveloppe convexe des codes de Huffman finis / The convex hull of Huffman codes

Nguyen, Thanh Hai 10 December 2010 (has links)
Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.
8

Approche probabiliste des particules collantes et système de gaz sans pression

Moutsinga, Octave 16 June 2003 (has links) (PDF)
A chaque instant $t$, nous construisons la dynamique des particules collantes dont la masse est distribuée initialement suivant une fonction de répartition $F_0$, avec une vitesse $u_0$, à partir de l'enveloppe convexe $H(\cdot,t)$ de la fonction $m\in (0,1)\mapsto \int_a^m\big( F_0^(-1)(z) + tu_0\big(F_0^(-1)(z)\big)\big)dz$. Ici, $F_0^(-1)$ est l'une des deux fonctions inverses de $F_0$. Nous montrons que les deux processus stochastiques $X_t^-(m)= \partial_m^-H(m,t),\; X_t^+(m) = \partial_m^+H(m,t)$, définis sur l'espace probabilisé $([0, 1], (\cal B), \lambda)$, sont indistinguables et ils modélisent les trajectoires des particules. Le processus $X_t:= X_t^- = X_t^+$ est une solution de l'équation $(EDS): \; \frac(dX_t)(dt) =\E[ u_0(X_0)/X_t]$, telle que $P(X_0 \leq x) = F_0(x)\,\,\forall x$. L'inverse $M_t:= M(\cdot,t)$ de la fonction $m\mapsto \partial_mH(m,t)$ est la fonction de répartition de la masse à l'instant $t$. Elle est aussi la fonction de répartition de la variable aléatoire $X_t$. On montre l'existence d'un flot $(\phi(x,t,M_s, u_s))_( s < t)$ tel que $X_t= \phi(X_s,t,M_s,u_s)$, où $u_s(x) = \E[ u_0(X_0)/X_s = x]$ est la fonction vitesse des particules à l'instant $s$. Si $\frac(dF_0^n)(dx)$ converge faiblement vers $\frac(dF_0)(dx)$, alors la suite des flots $\phi(\cdot,\cdot,F_0^n,u_0)$ converge uniformément, sur tout compact, vers $\phi(\cdot,\cdot,F_0,u_0)$. Ensuite, nous retrouvons et étendons certains résultats des équations aux dérivées partielles, à savoir que la fonction $(x,t)\mapsto M(x,t)$ est la solution entropique d'une loi de conservation scalaire de donnée initiale $F_0$, et la famille $\big(\rho(dx,t) = P(X_t\in dx),\, u(x,t) = \E[ u_0(X_0)/X_t = x]\big)_(t >0)$ est une solution faible du système de gaz sans pression de données initiales $\frac(dF_0(x))(dx), u_0$. Cette thèse contient aussi d'autres solutions de l'équation différentielle stochastique $(EDS)$ ci-dessus.
9

Quelques propositions pour la mise en oeuvre d'algorithmes combinatoires

Tallot, Didier 28 June 1985 (has links) (PDF)
Le travail, exposé dans ce rapport, se divise en deux parties. La première partie a fait l'objet d'un rapport de recherche publié en Avril 1984 [Tall]. La deuxième partie résulte d'un travail qui s'est déroulé de juin 1984 i juin 1985. Pour produire des images de hautes qualités, on est obligé de manipuler des grandes quantités de données. D'où l' intérêt d'étudier des algorithmes et des structures de données efficaces pour résoudre ~es problèmes géométriques. On pourra ainsi obtenir des méthodes efficaces pour la manipulation de données graphiques. On peut citer i ce propos, les travaux pionners de SHAMOS dans le domaine de la complexité géométrique [Sham]. La deuxième partie contient la description d 'un logiciel interactif *de manipulation de graphes et d'ordres. A notre connaissnce, la plus ancienne réalisation de ce type de logiciel est le "Graph theory interactive system" de WOLFBERG [Wolf]. Suivant les travaux de GUIDO sur CABRI (CAhier de BRouillon Informatisé), nous desirons offrir un poste de travail sur les graphes pour des chercheurs en théorie des graphes. CABRI est une bonne approche du problème, mais reste d'un emploi malaisé. Nous avons donc étudiés de nouveau le problème en nous attachant à décrire une meilleure interface utilisateur. Nous nous sommes inspirés des travaux sur les logiciels interactif existant, comme ceux développés chez XEROX, au PALO-ALTO RESEARCH CENTER (Smit] chez NIEVERGELT [Sere].
10

Simplification polyédrique optimale pour le rendu / Optimal polyhedral simplification for rendering

Charrier, Emilie 04 December 2009 (has links)
En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c’est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s’avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s’agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d’autre d’une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l’épaisseur d’un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure / In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension

Page generated in 0.0515 seconds