De nos jours la protection des données numériques est un problème très important. Que ce soit pour des applications de confidentialité, de communication, de traçabilité ou d'identification par exemple, il est nécessaire de développer des techniques adaptées. Dans le cadre de cette thèse en collaboration avec la société STRATEGIES S.A., la méthode choisie pour la protection de maillages 3D est l'insertion de données cachées, également appelée tatouage numérique. Pour des données 3D, un des problèmes les plus importants est la phase de synchronisation qui intervient dans les algorithmes d'insertion et d'extraction des données. Cette phase permet de repérer, de sélectionner et d'ordonner les « zones » qui sont privilégiées pour la dissimulation d'information. Nous avons choisi d'orienter le manuscrit sur cette phase. Ainsi, nous proposons une classification des méthodes de tatouages en fonction de leur méthode de synchronisation. Puis en se basant sur des techniques de synchronisation par des structures de données, telle que les arbres couvrants de poids minimum, nous proposons une analyse théorique de cette structure. Dans un premier temps nous expliquons les raisons de la sensibilité des arbres à la mobilité des points. Puis connaissant ses faiblesses, nous proposons une autre technique de synchronisation toujours basée sur les arbres couvrants de poids minimum. / Data security is one of the main issue in computer science. We need to develop solutions for confidentiality, communication, fingerprinting or identification applications for exemple. In this thesis made with STRATEGIES S.A., the chosen method to protect 3D meshes is watermarking.Watermarking is divided in two steps, the embedding and the extraction. In both of them a synchronization phase is needed. It is one of the most important step for 3D mesh because it permits to look for areas available to embed information, and order them. All the thesis is devoted to the synchronization step. First of all, we propose a classification of watermarking techniques based on the type of synchronization method instead of evaluation criterions such as robustness or capacity.Then, from methods based on Euclidean minimum spanning tree, we propose a theoritical analysis of the mobility of the vertices in that kind of structure. First, we explain the reasons of the sensibility of the structure. Secondly, we propose another scheme based on the Euclidean minimum spanning tree knowing its fragility.

Proximity problems and point set embeddability problems are fundamental and well-studied in computational geometry and graph drawing. Examples of such problems that are of particular interest to us in this dissertation include: finding the closest pair among a set P of points, finding the k-nearest neighbors to each point p in P, answering reverse k-nearest neighbor queries, computing the Yao graph, the Semi-Yao graph and the Euclidean minimum spanning tree of P, and mapping the vertices of a planar graph to a set P of points without inducing edge crossings. In this dissertation, we consider so-called kinetic version of these problems, that is, the points are allowed to move continuously along known trajectories, which are subject to change. We design a set of data structures and a mechanism to efficiently update the data structures. These updates occur at critical, discrete times. Also, a query may arrive at any time. We want to answer queries quickly without solving problems from scratch, so we maintain solutions continuously. We present new techniques for giving kinetic solutions with better performance for some these problems, and we provide the first kinetic results for others. In particular, we provide: • A simple kinetic data structure (KDS) to maintain all the nearest neighbors and the closest pair. Our deterministic kinetic approach for maintenance of all the nearest neighbors improves the previous randomized kinetic algorithm. • An exact KDS for maintenance of the Euclidean minimum spanning tree, which improves the previous KDS. • The first KDS's for maintenance of the Yao graph and the Semi-Yao graph. • The first KDS to consider maintaining plane graphs on moving points. • The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1. • The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points. / Graduate

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe. / In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms.