Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

Nearest-neighbor search is a very natural and universal problem in computer science. Often times, the problem size necessitates approximation. In this thesis, I present new paradigms for nearest-neighbor search (along with new algorithms and theory in these paradigms) that make nearest-neighbor search more usable and accurate. First, I consider a new notion of search error, the rank error, for an approximate neighbor candidate. Rank error corresponds to the number of possible candidates which are better than the approximate neighbor candidate. I motivate this notion of error and present new efficient algorithms that return approximate neighbors with rank error no more than a user specified amount. Then I focus on approximate search in a scenario where the user does not specify the tolerable search error (error constraint); instead the user specifies the amount of time available for search (time constraint). After differentiating between these two scenarios, I present some simple algorithms for time constrained search with provable performance guarantees. I use this theory to motivate a new space-partitioning data structure, the max-margin tree, for improved search performance in the time constrained setting. Finally, I consider the scenario where we do not require our objects to have an explicit fixed-length representation (vector data). This allows us to search with a large class of objects which include images, documents, graphs, strings, time series and natural language. For nearest-neighbor search in this general setting, I present a provably fast novel exact search algorithm. I also discuss the empirical performance of all the presented algorithms on real data.

Dans cette thèse, nous étudions le problème du réflecteur. Etant données une source lumineuse et une cible à éclairer avec une certaine distribution d'intensité, il s'agit de construire une surface réfléchissant la lumière issue de la source vers la cible avec la distribution d'intensité prescrite. Ce problème se pose dans de nombreux domaines tels que l'art ou l'architecture. Le domaine qui nous intéresse ici est le domaine automobile. En effet, cette thèse Cifre est réalisée en partenariat avec l'entreprise Optis qui développe des logiciels de simulation de lumière et de conception optique utilisés dans les processus de fabrication des phares de voiture. Les surfaces formant les réflecteurs des phares de voiture doivent répondre à un certain nombre de critères imposés par les fabricants ainsi que les autorités de contrôle nationales et internationales. Ces critères peuvent être objectifs comme par exemple l'encombrement du véhicule ou encore le respect des normes d'éclairage mais peuvent également être subjectifs comme l'aspect esthétique des surfaces. Notre objectif est de proposer des outils industrialisables permettant de résoudre le problème du réflecteur tout en prenant en compte ces critères. Dans un premier temps, nous nous intéresserons au cas de sources lumineuses ponctuelles. Nous reprenons les travaux d'Oliker, Glim, Cafarrelli et Wang qui montrent que le problème du réflecteur peut être formulé comme un problème de transport optimal. Cette formulation du problème est présentée et mise en œuvre dans un cas discret. Dans un second temps, nous cherchons à prendre en compte les critères imposés par les fabricants de phares de voitures. Nous nous sommes intéressés ici aux contraintes d'encombrement et d'esthétique. La solution choisie consiste à utiliser des surfaces de Bézier définies comme le graphe d'une certaine fonction paramétrée par un domaine du plan. Les surfaces de Bézier permettent d'obtenir des surfaces lisses et la paramétrisation par un domaine du plan permet de gérer l'encombrement et le style d'un réflecteur. Nous avons proposé une méthode heuristique itérative par point fixe pour obtenir ce type surface. Enfin, dans un dernier temps, nous prenons en compte des sources lumineuses non ponctuelles. L'approche proposée consiste à adapter itérativement les paramètres du réflecteur de façon à minimiser une distance entre intensité souhaitée et intensité réfléchie. Ceci nous a conduits à proposer une méthode d'évaluation rapide de l'intensité réfléchie par une surface. Les méthodes développées durant cette thèse ont fait l'objet d'une implémentation dans un cadre industriel en partenariat avec l'entreprise Optis. / The far-field reflector problem consists in building a surface that reflects light from a given source back into a target at infinity with a prescribed intensity distribution. This problem arises in many fields such as art or architecture. In this thesis, we are interested in applications to the car industry. Indeed, this thesis is conducted in partnership with the company Optis that develops lighting and optical simulation software used in the design of car headlights. Surfaces in car headlight reflectors must satisfy several constraints imposed by manufacturers as well as national and international regulatory authorities. These constraints can be objective such as space requirements or compliance with lighting legal standards but can also can be subjective such as the aesthetic aspects of surfaces. Our goal is to provide industrializable tools to solve the reflector problem while taking into account these constraints. First, we focus on the case of point light sources. We rely on the work of Oliker, Glim, Cafarrelli and Wang who show that the reflector problem can be formulated as an optimal transport problem. This formulation of the problem is presented and implemented in a discrete case. In a second step, we take into account some of the constraints imposed by car headlight manufacturers, such as the size and the style of the reflector. The chosen solution consists in using Bezier surfaces defined as the graph of a function parameterized over a planar domain. Bezier surfaces allow to obtain smooth surfaces and the parameterization over a planar domain allows to control the size and style of the reflector. To build the surface, we propose a heuristic based on a fixed-point algorithm. Finally, we take into account extended light sources. We present an approach that iteratively adapts the parameters of the reflector by minimizing the distance between the desired intensity and the reflected intensity. This led us to propose a method that efficiently evaluates the reflection of light on the surface. Methods developed in this thesis were implemented in an industrial setting at our partner company Optis.

Le volume des données décrivant les solides tridimensionnels est sans cesse en augmentation. Une des principales causes de ce phénomène est le gain en résolution des modalités d'acquisition, qu'elles soient volumiques ou surfaciques. Par voie de conséquence, l'analyse de ces informations devient de plus en plus coûteuse et lourde à mettre en oeuvre, requérant des capacités de traitement ou de stockage importantes. Une phase de traitement, en aval du processus de numérisation est indispensable : les données doivent être structurées non seulement pour accélérer leur gestion mais aussi pour améliorer et favoriser la compréhension de leur contenu. Enfin, cette phase se doit d'être flexible afin d'être applicable à des domaines variés d'expertise. Nous proposons au travers de ce travail de thèse un modèle permettant de transformer tout solide numérisé en une entité répondant aux critères énoncés précédemment. Le Squelette Ellipsoïdal (ou E-Squelette) décompose les structures géométriques en sous-structures pertinentes tout en prélevant les informations importantes aux yeux de l'expert. En sortie de ce processus, on dispose de capacités de vision multi-échelle de la géométrie, enrichie des informations extraites. Des comparaisons dépendant de l'échelle de vision sont autorisées entre E-Squelettes, assurant le suivi temporel et la reconnaissance automatique d'objets solides 3D. Enfin, les données présentent de très importants taux de compression, et peuvent être transmises de manière progressive par réseau. L'erreur d'approximation est mesurable et contrôlable en terme de géométrie, ce qui garantit le contrôle de la validité des données transformées. Nous montrerons comment le E-Squelette s'applique à l'imagerie médicale et peut enrichir les moyens d'observation et de diagnostic.

Le lancer de rayon est un algorithme permettant de représenter des scènes 3D de façon très réaliste. Son principe, simple et puissant, repose sur les lois de l'optique géométrique : l'image que voit un observateur est le fruit des interactions entre des photons 6mis par des sources lumineuses et des objets possédant des propriétés géométriques et optiques. L'utilisation d'un modèle basé sur la physique permet une bonne approche des phénomènes naturels suivants : l'éclairement par des sources lumineuses, la réflexion de la lumière sur des objets et la transmission de la lumière à travers des objets transparents. L'algorithme dérivant de ce modèle possède pourtant un inconvénient majeur : le temps de traitement d'une image est très important. Bien que de nombreuses méthodes d'accélération aient été proposées pour tenter d'améliorer sa vitesse d'exécution, ce problème demeure bien présent. Toutefois, avec le développement actuel des machines parallèles à mémoire distribuée et des réseaux d'ordinateurs, une voie d'accélération très prometteuse se développe : la parallélisation. De plus, la mise en commun des capacités ''mémoire" de chaque composante d'une architecture parallèle rend possible le traitement de scènes comportant un plus grand nombre d'objets aux propriétés de plus en plus complexes. Le chapitre 1 présente l'algorithme de lancer de rayon ainsi que les accélérations séquentielles proposées dans la littérature. D apparaît que les techniques les plus efficaces sont basées soit sur l'utilisation de volumes englobants soit sur des subdivisions de l'espace. Malgré ces optimisations, la parallélisation demeure la source d'accélération au plus fort potentiel. Le chapitre 2 recense les différents types d'architectures parallèles et expose les familles d'algorithmes utilisées pour la parallélisation du lancer de rayon sur des machines parallèles à mémoire distribuée. Deux stratégies permettent une distribution de la base de données : 1' envoi de rayons et l'envoi d'objets. Dans le chapitre 3, après avoir présenté nos contraintes, nous comparons les algorithmes parallèles pouvant y répondre grâce à leur modélisation. Les résultats obtenus vont nous amener à proposer deux nouveaux algorithmes de parallélisation basés sur un nouveau type de flot. Enfin, dans le chapitre 4 nous présentons nos résultats expérimentaux et leur analyse. Nos tests sont réalisés sur des machines massivement parallèles et sur un réseau de stations de travail.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

En quelques années, les maillages ont conquis une position prédominante parmi les différents modes de représentation informatique d'objets géométriques. Plus particulièrement, les maillages à base de simplexes -- les triangles pour la représentation de surfaces plongées en 3D, les tétraèdres pour la représentation de volumes -- semblent être actuellement les plus répandus. Le développe- ment rapide des applications manipulant ces structures géométriques dans des domaines aussi divers que le calcul par éléments finis, la simulation chirurgi- cale, ou les jeux vidéo a très vite soulevé le problème d'un codage efficace et adapté à la visualisation. L'expansion du World Wide Web, qui nécessite une représentation compacte et progressive des données pour garantir la convivial- ité de l'interface homme-machine, a fini de conférer à ce problème une place centrale dans la recherche en informatique. Ainsi, depuis 1995, de nombreux algorithmes ont été proposés pour la com- pression de maillages triangulaires, en utilisant le plus souvent l'approche suiv- ante : les sommets du maillage sont codés dans un ordre établi pour contenir par- tiellement la topologie (ou connectivité) du maillage. Parallèlement, quelques règles simples permettent de prédire la position du sommet courant à partir des positions de ses voisins qui ont déjà été codés. Dans ce mémoire, nous avons choisi de donner plutôt la priorité à la compression des positions des sommets. Nous décrivons un ensemble de méthodes de codage progressif, sans perte d'information, adaptées à une large classe de structures géométriques (non nécessairement triangulaires ni manifold, de genre quelconque), et généralisables à n'importe quelle dimension. Les taux de compression obtenus se positionnent avantageusement par rapport aux méthodes progressives actuelles les plus ef- ficaces : par exemple, pour le cas particulier des maillages triangulaires sur- faciques, des taux moyens autour de 3,6 bits par sommet sont atteints sur des modèles usuels pour le codage de la connectivité.

Dans cette thèse, nous étudions le problème du réflecteur. Etant données une source lumineuse et une cible à éclairer avec une certaine distribution d'intensité, il s'agit de construire une surface réfléchissant la lumière issue de la source vers la cible avec la distribution d'intensité prescrite. Ce problème se pose dans de nombreux domaines tels que l'art ou l'architecture. Le domaine qui nous intéresse ici est le domaine automobile. En effet, cette thèse Cifre est réalisée en partenariat avec l'entreprise Optis qui développe des logiciels de simulation de lumière et de conception optique utilisés dans les processus de fabrication des phares de voiture. Les surfaces formant les réflecteurs des phares de voiture doivent répondre à un certain nombre de critères imposés par les fabricants ainsi que les autorités de contrôle nationales et internationales. Ces critères peuvent être objectifs comme par exemple l'encombrement du véhicule ou encore le respect des normes d'éclairage mais peuvent également être subjectifs comme l'aspect esthétique des surfaces. Notre objectif est de proposer des outils industrialisables permettant de résoudre le problème du réflecteur tout en prenant en compte ces critères. Dans un premier temps, nous nous intéresserons au cas de sources lumineuses ponctuelles. Nous reprenons les travaux d'Oliker, Glim, Cafarrelli et Wang qui montrent que le problème du réflecteur peut être formulé comme un problème de transport optimal. Cette formulation du problème est présentée et mise en œuvre dans un cas discret. Dans un second temps, nous cherchons à prendre en compte les critères imposés par les fabricants de phares de voitures. Nous nous sommes intéressés ici aux contraintes d'encombrement et d'esthétique. La solution choisie consiste à utiliser des surfaces de Bézier définies comme le graphe d'une certaine fonction paramétrée par un domaine du plan. Les surfaces de Bézier permettent d'obtenir des surfaces lisses et la paramétrisation par un domaine du plan permet de gérer l'encombrement et le style d'un réflecteur. Nous avons proposé une méthode heuristique itérative par point fixe pour obtenir ce type surface. Enfin, dans un dernier temps, nous prenons en compte des sources lumineuses non ponctuelles. L'approche proposée consiste à adapter itérativement les paramètres du réflecteur de façon à minimiser une distance entre intensité souhaitée et intensité réfléchie. Ceci nous a conduits à proposer une méthode d'évaluation rapide de l'intensité réfléchie par une surface. Les méthodes développées durant cette thèse ont fait l'objet d'une implémentation dans un cadre industriel en partenariat avec l'entreprise Optis. / The far-field reflector problem consists in building a surface that reflects light from a given source back into a target at infinity with a prescribed intensity distribution. This problem arises in many fields such as art or architecture. In this thesis, we are interested in applications to the car industry. Indeed, this thesis is conducted in partnership with the company Optis that develops lighting and optical simulation software used in the design of car headlights. Surfaces in car headlight reflectors must satisfy several constraints imposed by manufacturers as well as national and international regulatory authorities. These constraints can be objective such as space requirements or compliance with lighting legal standards but can also can be subjective such as the aesthetic aspects of surfaces. Our goal is to provide industrializable tools to solve the reflector problem while taking into account these constraints. First, we focus on the case of point light sources. We rely on the work of Oliker, Glim, Cafarrelli and Wang who show that the reflector problem can be formulated as an optimal transport problem. This formulation of the problem is presented and implemented in a discrete case. In a second step, we take into account some of the constraints imposed by car headlight manufacturers, such as the size and the style of the reflector. The chosen solution consists in using Bezier surfaces defined as the graph of a function parameterized over a planar domain. Bezier surfaces allow to obtain smooth surfaces and the parameterization over a planar domain allows to control the size and style of the reflector. To build the surface, we propose a heuristic based on a fixed-point algorithm. Finally, we take into account extended light sources. We present an approach that iteratively adapts the parameters of the reflector by minimizing the distance between the desired intensity and the reflected intensity. This led us to propose a method that efficiently evaluates the reflection of light on the surface. Methods developed in this thesis were implemented in an industrial setting at our partner company Optis.

[pt] Pesquisas na área de estrutura de dados são fundamentais para aumentar a generalidade e eficiência computacional da representacão de modelos geometricos. Neste trabalho, apresentamos duas estruturas de dados topológicas escalonáveis, uma para superfícies triânguladas, chamada CHE (Compact Half--Edge), e outra para malhas de tetraedros, chamada CHF (Compact Half--Face). Tais estruturas são compostas de diferentes níveis, que nos possibilitam alterar a quantidade de dados armazenados com objetivo de melhorar sua eficiência computacional. O uso de APIs baseadas no conceito de objeto, e de haran»ca de classes, possibilitam uma interface única para cada função em todos os níveis das estruturas. A CHE e a CHF requerem pouca memória e são simples de implementar já que substituem o uso de ponteiros pelo de contêineres genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase the generality and computational effciency of geometric models` representation. In this work, we present two new scalable topological data structures, one for triangulated surfaces, called CHE (Compact Half { Edge ), and the another for tetrahedral meshes, called CHF (Compact Half { Face ). Such structures are composed of different levels, that enable us to modify the amount of data stored with the objective to improve its computational effciency. The use of APIs based in the object concept and class inheritance, makes possible an unique interface for each function at any level. CHE and CHF requires very few memory and are simple to implement since they substitute the use of pointers by generic containeres and arithmetical rules.

M.Sc (Computer Science) / Facial modelling and animation is considered one of the most challenging areas in the animation world. Since Parke and Waters’s (1996) comprehensive book, no major work encompassing the entire field of facial animation has been published. This thesis covers Parke and Waters’s work, while also providing a survey of the developments in the field since 1996. The thesis describes, analyses, and compares (where applicable) the existing techniques and practices used to produce the facial animation. Where applicable, the related techniques are grouped in the same chapter and described in a chronological fashion, outlining their differences, as well as their advantages and disadvantages. The thesis is concluded by exploratory work towards a talking head for Northern Sotho. Facial animation and lip synchronisation of a fragment of Northern Sotho is done by using software tools primarily designed for English. / Computing