Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.

Thesis (Ph.D.)--Mississippi State University. Department of Physics and Astronomy. / Title from title screen. Includes bibliographical references.

Ces travaux s'inscrivent dans la thématique de l'inférence géométrique dont le but est de répondre au problème suivant : étant donné un objet géométrique dont on ne connaît qu'une approximation, peut-on estimer de manière robuste ses propriétés? On se place dans cette thèse dans le cas où l'approximation est un nuage de points ou un ensemble digital dans un espace euclidien de dimension finie. On montre tout d'abord un résultat de stabilité d'un estimateur de normale basé sur l'analyse en composante principale, ainsi qu'un résultat de convergence multigrille d'un estimateur du Voronoi Covariance Measure qui utilise des matrices de covariance de cellules de Voronoi. Ces deux résultats, comme la plupart des résultats en inférence géométrique, utilisent la stabilité de la fonction distance à un compact. Cependant, la présence d'un seul point aberrant suffit pour que les hypothèses des résultats de stabilité ne soient pas satisfaites. La distance à une mesure est une fonction distance généralisée introduite récemment qui est robuste aux points aberrants. Dans ce travail, on généralise le Voronoi Covariance Measure à des fonctions distances généralisées et on montre que cet estimateur appliqué à la distance à une mesure est robuste aux points aberrants. On en déduit en particulier un estimateur de normale très robuste. On présente également des résultats expérimentaux qui montrent une forte robustesse des estimations de normales, courbures, directions de courbure et arêtes vives. Ces résultats sont comparés favorablement à l'état de l'art. / The purpose of geometric inference is to answer the following problem : Given a geometric object that is only known through an approximation, can we get a robust estimation of its properties? We consider in this thesis the case where the approximation is a point cloud or a digital set in a finite dimensional Euclidean space. We first show a stability result for a normal estimator based on the principal component analysis, as well as a result of multigrid convergence of an estimator of the Voronoi covariance measure, which uses covariance matrices of Voronoi cells. As most of geometric inference results, these two last results use the robustness of the distance function to a compact set. However, the presence of a single outlier is sufficient to make the assumptions of these results not satisfied. The distance to a measure is a generalized distance function introduced recently, that is robust to outliers. In this work, we generalize the Voronoi Covariance Measure to generalized distance functions and we show that this estimator applied to the distance to a measure is robust to outliers. We deduce a very robust normal estimator. We present experiments showing the robustness of our approach for normals, curvatures, curvature directions and sharp features estimation. These results are favorably compared to the state of the art.

Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-10T10:56:09Z (GMT). No. of bitstreams: 1 Strapasson_JoaoEloir_D.pdf: 1100322 bytes, checksum: 054aeab4b36f30144155ce6b1668659a (MD5) Previous issue date: 2007 / Resumo: Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) / Abstract: The research developed here is related and inspired by problems in coding theory. It is presented in two parts. In the first we focus on the search for the minimum nonvanishing vector of a lattice, specially in the case of a projection of the ndimensional integer lattice in the direction of one of its vectors. This is a problem of high computational complexity which is related to the search for efficient joint sourcechannel continuous coding. In the second part we deal with flat torus graphs generated by a quotient of lattices and which are labeled by a a cyclic group of isometries. We show that any circulant graph is isomorphic to one of these graphs and hence associated to a spherical code. Through these isomorphism a complete classification of circulant graphs of genus one and the genus of an arbitrarily high order class of circulant graphs is obtained. / Doutorado / Geometria Topologia / Doutor em Matemática

Orientador : Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T14:39:59Z (GMT). No. of bitstreams: 1 Siqueira_RogerioMonteirode_D.pdf: 1994309 bytes, checksum: 7735d63966bc2d9b5c84ccac989c3289 (MD5) Previous issue date: 2006 / Resumo: Códigos esféricos euclidianos com simetrias são órbitas finitas de grupos de matrizes ortogonais. Tais códigos são também conhecidos como códigos de grupo. Neste trabalho, os códigos de grupo comutativo em dimensão par são caracterizados sobre toros planos, subvariedades da esfera. Em particular, se o grupo de matrizes for cíclico, o código gerado está contido em um nó que se enrola em um tora. Se a dimensão for ímpar, todo código de grupo comutativo mora em anti-primas cujas bases estão contidas em dois toros planos. Tal caracterização permitiu a construção de limitantes para a cardinalidade destas constelações de pontos em termos da distância mínima destes códigos e da densidade de empacotamento de um reticulado associado. Utilizando o método de Biglieri e Elia, que procura o vetor inicial cujo respectivo código de grupo cíclico tem a melhor distância mínima, apresentamos também os melhores códigos de grupo cíclico em dimensão quatro até 100 pontos / Abstract: Euclidean spherical codes with symmetries are orbits of finite orthogonal matrix groups. These codes are also known as group codes. ln this work, the commutative group codes in even dimensions are viewed on flat tori, which are submanifolds of the sphere. Also, if the matrix group is cyclic, the generated code lies on a knot which wraps around a torus. If the dimension is odd, every commutative group code lies on an anti-prism whose bases are contained in two flat tori. This interpretation lead us to build upper bounds for the cardinality of these constellations involving their minimum distance and the packing density of an associated lattice. Using a method by Biglieri and Elia, which searchs the initial vector for a cyclic group in order to achieve the best minimum distance, we also present the best cyclic group codes in dimension four up to 100 points / Doutorado / Matematica / Doutor em Matemática

La théorie de l'homologie formalise la notion de trou dans un espace. Pour un sous-ensemble de l'espace Euclidien, on définit une séquence de groupes d'homologie, dont leurs rangs sont interprétés comme le nombre de trous de chaque dimension. Ces groupes sont calculables quand l'espace est décrit d'une façon combinatoire, comme c'est le cas pour les complexes simpliciaux ou cubiques. À partir d'un objet discret (un ensemble de pixels, voxels ou leur analogue en dimension supérieure) nous pouvons construire un complexe cubique et donc calculer ses groupes d'homologie.Cette thèse étudie trois approches relatives au calcul de l'homologie sur des objets discrets. En premier lieu, nous introduisons le champ de vecteurs discret homologique, une structure combinatoire généralisant les champs de vecteurs gradients discrets, qui permet de calculer les groupes d'homologie. Cette notion permet de voir la relation entre plusieurs méthodes existantes pour le calcul de l'homologie et révèle également des notions subtiles associés. Nous présentons ensuite un algorithme linéaire pour calculer les nombres de Betti dans un complexe cubique 3D, ce qui peut être utilisé pour les volumes binaires. Enfin, nous présentons deux mesures (l'épaisseur et l'ampleur) associés aux trous d'un objet discret, ce qui permet d'obtenir une signature topologique et géométrique plus intéressante que les simples nombres de Betti. Cette approche fournit aussi quelques heuristiques permettant de localiser les trous, d'obtenir des générateurs d'homologie ou de cohomologie minimaux, d'ouvrir et de fermer les trous. / Homology theory formalizes the concept of hole in a space. For a given subspace of the Euclidean space, we define a sequence of homology groups, whose ranks are considered as the number of holes of each dimension. Hence, b0, the rank of the 0-dimensional homology group, is the number of connected components, b1 is the number of tunnels or handles and b2 is the number of cavities. These groups are computable when the space is described in a combinatorial way, as simplicial or cubical complexes are. Given a discrete object (a set of pixels, voxels or their analog in higher dimension) we can build a cubical complex and thus compute its homology groups.This thesis studies three approaches regarding the homology computation of discrete objects. First, we introduce the homological discrete vector field, a combinatorial structure which generalizes the discrete gradient vector field and allows to compute the homology groups. This notion allows to see the relation between different existing methods for computing homology. Next, we present a linear algorithm for computing the Betti numbers of a 3D cubical complex, which can be used for binary volumes. Finally, we introduce two measures (the thickness and the breadth) associated to the holes in a discrete object, which provide a topological and geometric signature more interesting than only the Betti numbers. This approach provides also some heuristics for localizing holes, obtaining minimal homology or cohomology generators, opening and closing holes.

Dans ce travail de thèse , je présente comment extraire les géométries discrètes de l'espace-temps de la formulation covariante de la gravitaté quantique à boucles, qui est appelé le formalisme de la mousse de spin. LQG est une théorie quantique de la gravité qui non-perturbativement quantifie la relativité générale indépendante d'un fond fixe. Il prédit que la géométrie de l'espace est quantifiée, dans lequel l'aire et le volume ne peuvent prendre que la valeur discrète. L'espace de Hilbert cinématique est engendré par les fonctions du réseau de spin. L'excitation de la géométrie peut être parfaitement visualisée comme des polyèdres floue qui collées à travers leurs facettes. La mousse de spin définit la dynamique de la LQG par une amplitude de la mousse de spin sur un complexe cellulaire avec un état du réseau de spin comme la frontiére. Cette thèse présente deux résultats principaux. Premièrement, la limite semi-classique de l'amplitude de la mousse de spin sur un complexe simplicial arbitraire avec une frontière est complètement étudiée. La géométrie discrète classique de l'espace-temps est reconstruite et classée par les configurations critiques de l'amplitude de la mousse de spin. Deuxièmement, la fonction de trois-point de LQG est calculé. Il coïncide avec le résultat de la gravité discrète. Troisièmement, la description des géométries discrètes de hypersurfaces nulles est explorée dans le cadre de la LQG. En particulier, la géométrie nulle est décrit par une structure singulière euclidienne sur la surface de type espace à deux dimensions définie par un feuilletage de l'espace-temps par hypersurfaces nulles. / In this thesis, I will present how to extract discrete geometries of space-time fromthe covariant formulation of loop quantum gravity (LQG), which is called the spinfoam formalism. LQG is a quantum theory of gravity that non-perturbative quantizesgeneral relativity independent from a fix background. It predicts that the geometryof space is quantized, in which area and volume can only take discrete value. Thekinematical Hilbert space is spanned by Penrose's spin network functions. The excita-tion of geometry can be neatly visualized as fuzzy polyhedra that glued through theirfacets. The spin foam defines the dynamics of LQG by a spin foam amplitude on acellular complex, bounded by the spin network states. There are three main results inthis thesis. First, the semiclassical limit of the spin foam amplitude on an arbitrarysimplicial cellular complex with boundary is studied completely. The classical discretegeometry of space-time is reconstructed and classified by the critical configurations ofthe spin foam amplitude. Second, the three-point function from LQG is calculated.It coincides with the results from discrete gravity. Third, the description of discretegeometries of null hypersurfaces is explored in the context of LQG. In particular, thenull geometry is described by a Euclidean singular structure on the two-dimensionalspacelike surface defined by a foliation of space-time by null hypersurfaces. Its quan-tization is U(1) spin network states which are embedded nontrivially in the unitaryirreducible representations of the Lorentz group.

Les travaux effectués durant cette thèse portent sur l’appariement de formes planes basé sur une squelettisation hiérarchique. Dans un premier temps, nous avons abordé la création d’un squelette de forme grâce à un algorithme associant des outils de la géométrie discrète et des filtres. Cette association permet d’acquérir un squelette regroupant les propriétés désirées dans le cadre de l’appariement. Néanmoins, le squelette obtenu reste une représentation de la forme ne différenciant pas les branches représentant l’allure générale de celles représentant un détail de la forme. Or, lors de l’appariement, il semble plus intéressant d’associer des branches ayant le même ordre d’importance, mais aussi de donner plus de poids aux associations décrivant un aspect global des formes. Notre deuxième contribution porte sur la résolution de ce problème. Elle concerne donc la hiérarchisation des branches du squelette, précédemment créé, en leur attribuant une pondération reflétant leur importance dans la forme. À cet effet, nous lissons progressivement une forme et étudions la persistance des branches pour leur attribuer un poids. L’ultime étape consiste donc à apparier les formes grâce à leur squelette hiérarchique modélisé par un hypergraphe. En d’autres termes, nous associons les branches deux à deux pour déterminer une mesure de dissimilarité entre deux formes. Pour ce faire, nous prenons en compte la géométrie des formes, la position relative des différentes parties des formes ainsi que de leur importance. / The works performed during this thesis focuses on the matching of planar shapes based on a hierarchical skeletonisation. First, we approached the creation of a shape skeleton using an algorithm combining the tools of discrete geometry and filters. This combination allows to acquire a skeleton gathering the desired properties in the context of matching. Nevertheless, the resulting skeleton remains a representation of the shape, which does not differentiate branches representing the general shape of those coming from a detail of the shape. But when matching, it seems more interesting to pair branches of the same order of importance, but also to give more weight to associations describing an overall appearance of shapes. Our second contribution focuses on solving this problem. It concerns the prioritization of skeletal branches, previously created by assigning a weight reflecting their importance in shape. To this end, we gradually smooth a shape and study the persistence of branches to assign a weight. The final step is to match the shapes with their hierarchical skeleton modeled as a hypergraph. In other words, we associate the branches two by two to determine a dissimilarity measure between two shapes. To do this, we take into account the geometry of the shapes, the relative position of different parts of the shapes and their importance.

L'étude non destructive du bois à partir de scanners à rayons X nécessite d’imaginer de nouvelles solutions adaptées à l'analyse des images. Préoccupation à la fois de la recherche agronomique et du milieu industriel des scieries, la segmentation des nœuds de bois est un défi majeur en termes de robustesse aux spécificités de chaque espèce et aux conditions d'acquisition des images. Les travaux menés dans cette thèse permettent de proposer un processus de segmentation en deux phases. Il isole d'abord chaque nœud dans une zone réduite puis segmente le nœud unique de chaque zone. Les solutions proposées pour chaque phase permettent d'intégrer les connaissances sur l'organisation interne du tronc et les mécanismes inhérents à sa croissance, à travers des outils classiques du traitement et de l'analyse d'image. La première phase repose en grande partie sur un principe de détection du mouvement emprunté à l'analyse vidéo et revisité. Deux approches de segmentation sont ensuite proposées, considérant pour l'une les coupes tomographiques initiales, et pour l'autre de nouvelles coupes ré-échantillonnées pour chaque nœud, orthogonalement à sa trajectoire. L'intégralité du processus a été implémenté dans un logiciel dédié aussi bien à l'expérimentation et la validation de l'approche qu'aux échanges interdisciplinaires. Le support applicatif du bois souligne la capacité de spécialisation des algorithmes génériques du traitement et de l'analyse d'image, et la pertinence de l'intégration de connaissances a priori dans cette optique / The non-destructive study of wood from X-Ray CT scanners requires to imagine new solutions adapted to analysis of images. Relating both agronomic research and industrial sector of sawmills, segmentation of wood knots is a major challenge in terms of robustness to specificities of each species and to image acquisition conditions. The works carried out in this thesis allow to propose a segmentation process in two phases. It first isolates each knot in a reduced area then it segments the unique knot of each area. Proposed solutions for each phase allow to integrate knowledges about internal organization of trunk and mechanisms inherent to its growth, through classical tools of image analysis and processing. The first phase is essentially based on a movement detection principle borrowed from video analysis and revisited. Two segmentation approaches are then proposed, considering for one the initial CT slices and for the other news slices resampled for each knot orthogonally to its trajectory. The complete process has been implemented in a software dedicated both for experimentation and validation of approach, and to interdisciplinary dialogs. The applicative support of wood emphasizes the specialization abilities of generic image analysis and processing algorithms, and the relevance to integrate priori knowledges in this perspective

La présence de spécularité sur un objet est un problème récurrent qui limite l'application de nombreuses méthodes de segmentation. En effet, les spécularités sont des zones ayant une intensité très élevée et perturbent énormément la détection dès lors que l'on utilise la notion de gradient de l'image. Les travaux menés dans cette thèse permettent de proposer une nouvelle méthode de détection d'un objet tubulaire métallique dans une image. La méthode s'affranchit de la notion de gradient en utilisant la notion de profil d'intensité. Nous proposons dans ce manuscrit, un processus qui parcourt des zones rectangulaires prédéfinies de l'image, par balayage d'un segment discret à la recherche d'un profil d'intensité référence. Ces travaux s'inscrivent dans une collaboration avec Numalliance, une entreprise qui fabrique des machines-outils. Cette collaboration permet de mettre en pratique cette méthode dans le cadre d'un système de contrôle qualité automatique et temps-réel des pièces manufacturées par les machines-outils. Pour cela, la méthode présentée doit être rapide, robuste aux spécularités et à l'environnement industriel tout en étant suffisamment précise pour permettre de conclure sur la conformité ou non de la pièce / The presence of specularity on an object is a recurring problem that limits the application of many segmentation methods. Indeed, specularities are areas with a very high intensity and greatly disturb the detection when the notion of gradient of the image is used. The work carried out in this thesis makes it possible to propose a new detection method for a metallic tubular object in an image. The method avoids the notion of gradient by using the notion of intensity profile. We propose in this manuscript a process which traverses predefined rectangular areas of the image by scanning a discrete segment in search of a reference intensity profile. This work is part of a collaboration with Numalliance, a company that manufactures machine tools. This collaboration enables this method to be put into a real industrial application as part of an automatic and real-time quality control system for parts manufactured by machine tools. To this end, the method presented must be fast, robust to the specularities and to the industrial environment while being sufficiently precise to make it possible to conclude on the conformity or not of the part