Orientadores: Sueli Irene Rodrigues Costa, João Eloir Strapasson / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-24T22:37:48Z (GMT). No. of bitstreams: 1 Campello_A._D.pdf: 21969130 bytes, checksum: 2383d030b9ec589aaedae38670dbb458 (MD5) Previous issue date: 2014 / Resumo: O conteúdo desta tese reside na interface entre Matemática Discreta (particularmente reticulados) e Teoria da Informação. Dividimos as contribuições originais do trabalho em quatro capítulos, de modo que os dois primeiros são relativos a resultados teóricos acerca de duas importantes classes de reticulados (os reticulados q-ários e os reticulados projeção), e os dois últimos referem-se a aplicações em codificação contínua fonte-canal. Nos primeiros capítulos, exibimos resultados sobre decodificação de reticulados q-ários e sobre ladrilhamentos associados a códigos corretores de erros perfeitos na norma l_p. No que tange a reticulados projeção, nossas contribuições incluem o estudo de sequências de projeção de um dado reticulado n-dimensional convergindo para qualquer reticulado k-dimensional fixado, k < n, incluindo uma análise de convergência de tais sequências. Esses novos resultados relativos a projeções estendem e aprimoram recentes trabalhos no tema e são elementos de base para as aplicações consideradas no restante da tese. Nos dois últimos capítulos, consideramos o problema de transmitir uma fonte com alfabeto contínuo através de um canal gaussiano no caso em que a dimensão da fonte, k, é menor que a dimensão do canal, n. Para fontes unidimensionais, exibimos códigos baseados em curvas na superfície de toros planares com performance significativamente superior aos propostos anteriormente na literatura no que diz respeito ao erro quadrático médio atingido. Para k > 1, mostramos como aplicar projeções de reticulados para obter códigos cujo erro quadrático médio possui decaimento ótimo com respeito à relação sinal-ruído do canal (chamados de assintoticamente ótimos). Através de técnicas provenientes da bela teoria de dissecção de poliedros, apresentamos as primeiras construções de códigos assintoticamente ótimos para fontes com dimensão maior do que 1 / Abstract: The contents of this thesis lie in the interface between Discrete Mathematics (particularly lattices) and Information Theory. The original contributions of this work are organized so that the first two chapters are devoted to theoretical results on q-ary and projection lattices, whereas the last ones are related to the construction of continuous source-channel codes. In the first chapters, we exhibit results on decoding q-ary lattices and on finding tilings associated to perfect error-correcting codes in the l_p norm. Regarding projection lattices, our contributions include the study of sequences of projections of a given n-dimensional lattice converging to any k-dimensional target lattice, as well as a convergence analysis of such sequences. These new results on projections extend and improve recent works on the topic and serve as building blocks for the applications to be developed throughout the last part of the thesis. In the last two chapters, we consider the problem of constructing mappings for the transmission of a continuous alphabet source over a Gaussian channel, when the channel dimension, n, is strictly greater than the source dimension, k. For one-dimensional sources, we exhibit codes based on curves on flat tori with performance significantly superior to the previous proposals in the literature with respect to the mean squared error achieved. For k > 1, we show how to apply projections of lattices to obtain codes whose mean squared error decays optimally with respect to the signal-to-noise ratio of the channel (referred to as asymptotically optimal codes). Through techniques from the rich theory of dissections of polyhedra, we present the first constructions of provenly asymptotically optimal codes for sources with dimension greater than 1 / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Sueli Irene Rodrigues Costa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica. / Made available in DSpace on 2018-08-20T13:21:10Z (GMT). No. of bitstreams: 1 Tsuchiya_LucianaYoshie_M.pdf: 11296327 bytes, checksum: 3b12c518b500ac555263de03beead341 (MD5) Previous issue date: 2012 / Resumo: Reticulados no 'R^n' são conjuntos discretos de pontos gerados como combinações inteiras de vetores linearmente independentes. A estrutura e as propriedades de reticulados vêm sendo exploradas em diversas áreas, dentre elas a Teoria da Informação. Neste trabalho fizemos um estudo de reticulados q-ários na métrica da soma, os quais estão relacionados aos códigos q-ários. Iniciamos com o estudo de reticulados gerais abordando questões como, densidade de empacotamento, determinação da região de Voronoi, equivalência de reticulados e processos de decodificação, fazendo um paralelo destas questões na métrica euclidiana e na métrica da soma. Em seguida, no Capitulo 2, tratamos brevemente os conceitos de códigos corretores de erros, onde os códigos q-ários estão inseridos e códigos lineares definidos sobre corpos finitos. No estudo dos códigos q-ários consideramos a distancia de Lee que e uma alternativa a usual métrica de Hamming. Por fim, no Capitulo 3, abordamos os reticulados q-ários que são obtidos a partir de códigos q-ários pelo processo conhecido como Construção A. Estudamos uma forma de se decodificar um reticulado q-ário via a Construção A, usando a decodificação do código e vice-versa e discutimos um algoritmo de decodificação (Lee Sphere Decoding) para reticulados q-ários que possuem matriz geradora de formato especial / Abstract: Lattices in 'R^n' are discrete sets of points generated as integer combinations of linearly independent vectors. The structure and properties of lattices have been explored in several areas, including Information Theory. In this work, we study q-ary lattices which are obtained from q-ary codes in the sum metric. We begin the study of general lattices, approaching topics as packing density, Voronoi regions, lattice equivalence and decoding processes, considering both the Euclidean and sum metric. In Chapter 2, we introduce some error correcting codes concepts focusing on q-ary codes and the more general class of linear codes defined over finite fields. In the study of q-ary codes, we consider the Lee distance, as an extension and alternative to the usual Hamming metric. Finally, in Chapter 3, we approach the q-ary latt ices, which are obtained from q-ary codes via the so called Construction A. We study a q-ary lattice decoding process, relate it to the associate code decoding and discuss a decoding algorithm for lattices which have special generator matrices / Mestrado / Matematica / Mestre em Matemática

The topic of this thesis is motivated by recent developments in Architectural Geometry, namely Eike Schling’s asymptotic gridshells and progress in solutions for paneling freeform facades. An asymptotic gridshell is fabricated from flat straight lamellas of bendable material such as sheet metal. These strips are then arranged in a grid-like spatial structure, such that the lamellas are orthogonal to a reference surface, which however is not materialized. Differential geometry then tells us that the strips must follow asymptotic curves of that reference surface. The actual construction is simplified if angles at nodes are constant. If that angle is a right angle, one gets minimal surfaces as reference surfaces. If the angle is constant, one obtains negatively curved surfaces with a constant ratio of principal curvatures (CRPC surfaces). Their characteristic parameterizations are equi-angular asymptotic parameterizations. We are also interested in the positively curved CRPC surfaces. Due to the relation between curvatures, they have a one-parameter family of curvature elements, which facilitates cost-effective paneling solutions through mold-reuse. Our approach to positively curved CRPCS surfaces is again based on equi-angular characteristic parameterizations. These characteristic parameterizations are conjugate and symmetric with respect to the principal curvature directions. After a review of the required results from classical surface theory, we first present a derivation of rotational CRPC surfaces. By simple geometric considerations one can find their characteristic parameterizations. In this way we add some new insight to this known class of surfaces. However, it turns out to be very hard to come up with explicit results on non-rotational CRPC surfaces. This is in big contrast to the special case of minimal surfaces which are characterized be the constant principal curvature ratio -1. Due to the difficulties in handling smooth CRPC surfaces, we turn to discrete models in form of constrained quad meshes. The discrete models belong to the area of Discrete Differential Geometry. There, one does not discretize equations from the smooth theory, but fundamental concepts of the theory. We introduce the basic structures needed in this context: asymptotic nets, conjugate nets and principal symmetric nets. The latter are a recent development in discrete differential geometry and characterized by spherical vertex stars. This means that a vertex of the quad mesh and its four connected neighbors lie on a sphere. If that sphere degenerates to a plane at all vertices, one has the classical discrete asymptotic parameterization as an A-net. Several ways to discretize the constant intersection angle are presented. The actual computation of discrete CRPC surfaces is performed with numerical optimization with an appropriately regularized Gauss-Newton algorithm for solving a nonlinear least squares problem. Optimization requires initial configurations. Those can come from the known classes of CRPC surfaces such as rotational surfaces of minimal surfaces. The latter case yields some surprising results on negatively curves CRPC surfaces of nontrivial topology. In general, such discrete models can serve as a guiding line for future research on the theoretical side. This is briefly indicated in the final discussion on future research directions.

This dissertation presents recent contributions in tropical geometry with a view towards positivity, and on certain semialgebraic sets which are constructed from polytopes. Tropical geometry is an emerging field in mathematics, combining elements of algebraic geometry and polyhedral geometry. A key in establishing this bridge is the concept of tropicalization, which is often described as mapping an algebraic variety to its 'combinatorial shadow'. This shadow is a polyhedral complex and thus allows to study the algebraic variety by combinatorial means. Recently, the positive part, i.e. the intersection of the variety with the positive orthant, has enjoyed rising attention. A driving question in recent years is: Can we characterize the tropicalization of the positive part? In this thesis we introduce the novel notion of positive-tropical generators, a concept which may serve as a tool for studying positive parts in tropical geometry in a combinatorial fashion. We initiate the study of these as positive analogues of tropical bases, and extend our theory to the notion of signed-tropical generators for more general signed tropicalizations. Applying this to the tropicalization of determinantal varieties, we develop criteria for characterizing their positive part. Motivated by questions from optimization, we focus on the study of low-rank matrices, in particular matrices of rank 2 and 3. We show that in rank 2 the minors form a set of positive-tropical generators, which fully classifies the positive part. In rank 3 we develop the starship criterion, a geometric criterion which certifies non-positivity. Moreover, in the case of square-matrices of corank 1, we fully classify the signed tropicalization of the determinantal variety, even beyond the positive part. Afterwards, we turn to the study of polytropes, which are those polytopes that are both tropically and classically convex. In the literature they are also established as alcoved polytopes of type A. We describe methods from toric geometry for computing multivariate versions of volume, Ehrhart and h^*-polynomials of lattice polytropes. These algorithms are applied to all polytropes of dimensions 2,3 and 4, yielding a large class of integer polynomials. We give a complete combinatorial description of the coefficients of volume polynomials of 3-dimensional polytropes in terms of regular central subdivisions of the fundamental polytope, which is the root polytope of type A. Finally, we provide a partial characterization of the analogous coefficients in dimension 4. In the second half of the thesis, we shift the focus to study semialgebraic sets by combinatorial means. Intersection bodies are objects arising in geometric tomography and are known not to be semialgebraic in general. We study intersection bodies of polytopes and show that such an intersection body is always a semialgebraic set. Computing the irreducible components of the algebraic boundary, we provide an upper bound for the degree of these components. Furthermore, we give a full classification for the convexity of intersection bodies of polytopes in the plane. Towards the end of this thesis, we move to the study of a problem from game theory, considering the correlated equilibrium polytope $P_G$ of a game G from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes, and prove that it is a semialgebraic set for any game. Through the use of oriented matroid strata, we propose a structured method for classifying the possible combinatorial types of $P_G$, and show that for (2 x n)-games, the algebraic boundary of each stratum is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for (2 x 3)-games.:Introduction 1. Background 2. Tropical Positivity and Determinantal Varieties 3. Multivariate Volume, Ehrhart, and h^*-Polynomials of Polytropes 4. Combinatorics of Correlated Equilibria

Cut problems on graphs are a well-known and intensively studied class of optimization problems. In this thesis, we study the maximum cut problem, the maximum bond problem, and the minimum multicut problem through their associated polyhedra, i.e., the cut polytope, the bond polytope, and the multicut dominant, respectively. Continuing the research on the maximum cut problem and the cut polytope, we present a linear description for cut polytopes of K_{3,3}-minor-free graphs as well as an algorithm solving the maximum cut problem on these graphs in the same running time as planar maximum cut. Moreover, we give a complete characterization of simple and simplicial cut polytopes. Considering the maximum cut problem from an algorithmic point of view, we propose an FPT-algorithm for the maximum cut problem parameterized by the crossing number. We start the structural study of the bond polytope by investigating its basic properties and the effect of graph operations on the bond polytope and its facet-defining inequalities. After presenting a linear-time reduction of the maximum bond problem to the maximum bond problem on 3-connected graphs, we discuss valid and facet defining inequalities arising from edges and cycles. These inequalities yield a complete linear description for bond polytopes of 3-connected planar (K_5-e)-minor-free graphs. This polytopal result is mirrored algorithmically by proposing a linear-time algorithm for the maximum bond problem on (K_5-e)-minor-free graphs. Finally, we start the structural study of the multicut dominant. We investigate basic properties, which gives rise to lifting and projection results for the multicut dominant. Then, we study the effect of graph operations on the multicut dominant and its facet-defining inequalities. Moreover, we present facet-defining inequalities supported on stars, trees, and cycles as well as separation algorithms for the former two classes of inequalities.

Le contexte est la géométrie discrète dans Zn. Il s'agit de décrire les courbes et surfaces discrètes composées de voxels: les définitions usuelles de droites et plans discrets épais se comportent mal quand on passe à des ensembles courbes. Comment garantir un bon comportement topologique, les connexités requises, dans une situation qui généralise les droites et plans discrets?Le calcul de données sur ces courbes, normales, tangentes, courbure, ou des fonctions plus générales, fait appel à des moyennes utilisant des masques. Une question est la pertinence théorique et pratique de ces masques. Une voie explorée, est le calcul de masques fondés sur la marche aléatoire. Une marche aléatoire partant d'un centre donné sur une courbe ou une surface discrète, permet d'affecter à chaque autre voxel un poids, le temps moyen de visite. Ce noyau permet de calculer des moyennes et par là, des dérivées. L'étude du comportement de ce processus de diffusion, a permis de retrouver des outils classiques de géométrie sur des surfaces maillées, et de fournir des estimateurs de tangente et de courbure performants. La diversité du champs d'applications de ce processus de diffusion a été mise en avant, retrouvant ainsi des méthodes classiques mais avec une base théorique identique.} motsclefs{Processus Markovien, Géométrie discrète, Estimateur tangentes, normales, courbure, Noyau de diffusion, Analyse d'images / The context of discrete geometry is in Zn. We propose to discribe discrete curves and surfaces composed of voxels: how to compute classical notions of analysis as tangent and normals ? Computation of data on discrete curves use average mask. A large amount of works proposed to study the pertinence of those masks. We propose to compute an average mask based on random walk. A random walk starting from a point of a curve or a surface, allow to give a weight, the time passed on each point. This kernel allow us to compute average and derivative. The studied of this digital process allow us to recover classical notions of geometry on meshes surfaces, and give accuracy estimator of tangent and curvature. We propose a large field of applications of this approach recovering classical tools using in transversal communauty of discrete geometry, with a same theorical base.

L'imagerie médicale est une ressource de données principale pour différents types d'applications. Bien que les images concrétisent beaucoup d'informations sur le cas étudié, toutes les connaissances a priori du médecin restent implicites. Elles jouent cependant un rôle très important dans l'interprétation et l'utilisation des images médicales. Dans cette thèse, des connaissances anatomiques a priori sont intégrées dans deux applications médicales. Nous proposons d'abord une chaîne de traitement automatique qui détecte, quantifie et localise des anévrismes dans un arbre vasculaire segmenté. Des lignes de centre des vaisseaux sont extraites et permettent la détection et la quantification automatique des anévrismes. Pour les localiser, une mise en correspondance est faite entre l'arbre vasculaire du patient et un arbre vasculaire sain. Les connaissances a priori sont fournies sous la forme d'un graphe. Dans le contexte de l'identification des sous-parties d'un organe représenté sous forme de maillage, nous proposons l'utilisation d'une ontologie anatomique, que nous enrichissons avec toutes les informations nécessaires pour accomplir la tâche de segmentation de maillages. Nous proposons ensuite un nouvel algorithme pour cette tâche, qui profite de toutes les connaissances a priori disponibles dans l'ontologie. / Medical imaging is a principal data source for different applications. Even though medical images represent a lot of knowledge concerning the studied case, all the a priori knowledge known by the specialist remains implicit. Nevertheless this a priori knowledge has a major role in the interpretation and the use of the images. In this thesis, anatomical a priori knowledge is integrated in two medical applications. First, an automatic processing pipeline is proposed in order to detect, quantify and localize aneurysms on a segmented cerebrovascular tree. Centerlines of blood vessels are extracted and then used to automatically detect aneurysms and quantify them. To localize aneurysm, a matching is made between the cerebrovascular tree of the patient and a healthy one. The a priori knowledge, in this case, is represented by a graph. In the context of identifying sub-parts of an organ represented by a mesh, we propose the use of an anatomical ontology. This ontology is first enhanced by all information necessary to achieve the task of mesh segmenting. A new algorithm using this ontology to accomplish the segmentation task is then proposed.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. / In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented.

Une des thématiques abordée par l'équipe Image et Vidéo-Communication est la reconstruction tomographique discréte à l'aide de la transformée Mojette. Ma thèse s'inscrit dans le cadre de la reconstruction tomographique médicale. La transformée Mojette est une version discrète exacte de la transformée de Radon qui est l'outil mathématique permettant la reconstruction tomographique. Pour évaluer la qualité des reconstructions, nous avons utilisé des fantômes numériques 2D simples (objet carré, rond) en absence puis en présence de bruit. Le coeur de mon travail de thèse est la reconstruction d'un objet à l'aide d'un algorithme de rétroprojection filtrée exacte Mojette en absence de bruit s'appuyant sur la géométrie discrète. Pour un nombre fini de projections dépendant de la taille de l'objet à reconstruire la reconstruction est exacte. La majorité des tomographes industriels utilisent l'algorithme de rétroprojection de projections filtrées (Filtered Back Projection ou FBP) pour reconstruire la région d'intérêt. Cet algorithme possède deux défauts théoriques, un au niveau du filtre utilisé, l'autre au niveau de la rétroprojection elle-même. Nous avons pu mettre au point un algorithme de Mojette FBP. Cet algorithme fait partie des méthodes directes de reconstruction. Il a aussi été testé avec succès en présence de bruit. Cet algorithme permet une équivalence continu-discret lors de la reconstruction. L'étape de projection/rétroprojection Mojette présente la particularité intéressante de pouvoir être décrit par une matrice Toeplitz bloc Toeplitz. Pour utiliser cette propriété nous avons mis en oeuvre un algorithme de gradient conjugué.

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.