Thesis (Ph. D.)--Florida State University, 2006. / Advisor: Philip Bowers, Florida State University, College of Arts and Sciences, Dept. of Mathematics. Title and description from dissertation home page (viewed Sept. 15, 2006). Document formatted into pages; contains ix, 98 pages. Includes bibliographical references.

No description available.

In an interval society, voters are represented by intervals on the real line, corresponding to their approval sets on a linear political spectrum. I imagine the society to be a representative democracy, and ask how to choose members of the society as representatives. Following work in mathematical psychology by Coombs and others, I develop a measure of the compatibility (political similarity) of two voters. I use this measure to determine the popularity of each voter as a candidate. I then establish local “agreeability” conditions and attempt to find a lower bound for the popularity of the best candidate. Other results about certain special societies are also obtained

L’objet de ce travail est l’utilisation de certains formalismes non classiques (analyses non standard, analyses constructives) afin de proposer des bases théoriques nouvelles autour des problèmes de discrétisations d’objets continus. Ceci est fait en utilisant un modèle discret du système des nombres réels appelé droite d’Harthong-Reeb ainsi que la méthode arithmétisation associée qui est un processus de discrétisation des fonctions continues. Cette étude repose sur un cadre arithmétique non standard. Dans un premier temps, nous utilisons une version axiomatique de l’arithmétique non standard. Puis, dans le but d’améliorer le contenu constructif de notre méthode, nous utilisons une autre approche de l’arithmétique non standard découlant de la théorie des Ω-nombres de Laugwitz et Schmieden. Cette seconde approche amène à une représentation discrète et multi-résolution de fonctions continues.Finalement, nous étudions dans quelles mesures, la droite d’Harthong-Reeb satisfait les axiomes de Bridges décrivant le continu constructif. / The aim of this work is to introduce new theoretical basis for the discretization of continuous objects using non classical formalisms. This is done using a discrete model of the continuum called the Harthong-Reeb line together with the related arithmetization method which is a discretisation process of continuous functions. This study stands on a nonstandard arithmetical framework. Firstly, we use an axiomatic version of nonstandard arithmetic. In order to improve the constructive content of our method, the next step is to use another approach of nonstandard arithmetic deriving from the theory of Ω-numbers by Laugwitzand Schmieden. This second approach leads to a discrete multi-resolution representation of continuous functions. Afterwards, we investigate to what extent the Harthong-Reeb line fits Bridges axioms of the constructive continuum.

Dans cette thèse, nous nous intéressons à la reconnaissance des primitives discrètes multi-échelles. Nous considérons qu'une primitive discrète multi-échelles est une superposition de primitives discrètes de différentes échelles ; et nous proposons des approches qui permettent de déterminer les caractéristiques d'une primitive discrète ou d'une partie d'une primitive discrète.Nous proposons une nouvelle approche de reconnaissance de sous-segment discret qui se base sur des propriétés portant sur l'ordre des restes arithmétiques de la droite discrète. Nous établissons des liens entre les points d'appuis du sous-segment discret et les points ayant des restes arithmétiques minimaux et maximaux sur la droite discrète. D'après les résultats de nos comparaisons, cette approche se relève être plus efficace que des approches existantes.Nous nous intéressons ensuite à des approches de reconnaissance d'arcs et de cercles discrets par le centre généralisé. Nous étudions le dual de la médiatrice généralisée et proposons de calculer le centre généralisé par des calculs de visibilité dans l'espace dual afin de réduire son temps de calcul. Cette approche est valide aussi bien dans une grille régulière que dans une grille irrégulière isothétique.Finalement, nous nous intéressons à des approches de reconnaissance de droite discrète par la préimage généralisée. Nous utilisons la notion de frontière afin de diminuer le nombre d'éléments rentrant dans le calcul de la préimage généralisée ; ce qui simplifie le calcul et réduit le temps de calcul. Cette approche s'applique aussi dans une grille régulière comme dans une grille irrégulière isothétique. / This thesis is about discrete geometry and particularly recognition of multi-scale discrete primitives. We consider that a multiscale discrete primitive is a superimposition of many discrete primitives of different scales. Then we propose approaches of recognition of discrete primitives or parts of a discrete primitives.Firstly we propose a new approach for the recognition of digital subsegment that is based on properties of the sequence of arithmetic remainders of the digital straight line. We show there are sorne links between the leaning points of the digital subsegment and the points that have the minimal and maximal arithmetic remainders on the digital straight line. Based on the results of comparisons with others approaches, the approach seems more efficient. Secondly we present sorne work on improving digital rings and circles recognition by general circumcenter. We use the dual of the generalized bissector in order to simplify the computation of the intersections of generalized bissectors as a polygon stabbing problem. The dual of the generalized bissector is computed likely for pixels of a regular grid or paves of an irregular isothetic grid. Finaly we present some work on improving digital straight line recogrutlon by generalized preimage. To reduce the number of elements to take into account for the computation of the generalized preimage we introduce the concept of boundary. The approach based on boundary could be used in a regular grid or an irregular isothetic grid.

Les appareils d'acquisition d'image 3D sont désormais omniprésents dans plusieurs domaines scientifiques, dont l'imagerie biomédicale, la science des matériaux ou encore l'industrie. La plupart de ces appareils (IRM, scanners à rayons X, micro-tomographes, microscopes confocal, PET scans) produisent un ensemble de données organisées sur une grille régulière que nous nommerons des données digitales, plus couramment des pixels sur des images 2D et des voxels sur des images 3D. Lorsqu'elles sont bien récupérées, ces données approchent la géométrie de la forme capturée (comme des organes en imagerie biomédicale ou des objets dans l'ingénierie). Dans cette thèse, nous nous sommes intéressés à l'extraction de la géométrie sur ces données digitales, et plus précisément, nous nous concentrons à nous approcher des quantités géométriques différentielles comme la courbure sur ces objets. Ces quantités sont les ingrédients critiques de plusieurs applications comme la reconstruction de surface ou la reconnaissance, la correspondance ou la comparaison d'objets. Nous nous focalisons également sur les preuves de convergence asymptotique de ces estimateurs, qui garantissent en quelque sorte la qualité de l'estimation. Plus précisément, lorsque la résolution de l'appareil d'acquisition est augmenté, notre estimation géométrique est plus précise. Notre méthode est basée sur les invariants par intégration et sur l'approximation digitale des intégrations volumiques. Enfin, nous présentons une méthode de classification de la surface, qui analyse les données digitales dans un système à plusieurs échelles et classifie les éléments de surface en trois catégories : les parties lisses, les parties planes, et les parties singulières (discontinuités de la tangente). Ce type de détection de points caractéristiques est utilisé dans plusieurs algorithmes géométriques, comme la compression de maillage ou la reconnaissance d'objet. La stabilité aux paramètres et la robustesse au bruit sont évaluées en fonction des méthodes de la littérature. Tous nos outils pour l'analyse de données digitales sont appliqués à des micro-structures de neige provenant d'un tomographe à rayons X, et leur intérêt est évalué et discuté. / 3D image acquisition devices are now ubiquitous in many domains of science, including biomedical imaging, material science, or manufacturing. Most of these devices (MRI, scanner X, micro-tomography, confocal microscopy, PET scans) produce a set of data organized on a regular grid, which we call digital data, commonly called pixels in 2D images and voxels in 3D images. Properly processed, these data approach the geometry of imaged shapes, like organs in biomedical imagery or objects in engineering. In this thesis, we are interested in extracting the geometry of such digital data, and, more precisely, we focus on approaching geometrical differential quantities such as the curvature of these objects. These quantities are the critical ingredients of several applications like surface reconstruction or object recognition, matching or comparison. We focus on the proof of multigrid convergence of these estimators, which in turn guarantees the quality of estimations. More precisely, when the resolution of the acquisition device is increased, our geometric estimates are more accurate. Our method is based on integral invariants and on digital approximation of volumetric integrals. Finally, we present a surface classification method, which analyzes digital data in a multiscale framework and classifies surface elements into three categories: smooth part, planar part, and singular part (tangent discontinuity). Such feature detection is used in several geometry pipelines, like mesh compression or object recognition. The stability to parameters and the robustness to noise are evaluated with respect to state-of-the-art methods. All our tools for analyzing digital data are applied to 3D X-ray tomography of snow microstructures and their relevance is evaluated and discussed.

In 1946, Erdös posed the distinct distances problem, which asks for the minimum number of distinct distances that any set of n points in the real plane must realize. Erdös showed that any point set must realize at least &Omega(n1/2) distances, but could only provide a construction which offered &Omega(n/&radic(log(n)))$ distances. He conjectured that the actual minimum number of distances was &Omega(n1-&epsilon) for any &epsilon > 0, but that sublinear constructions were possible. This lower bound has been improved over the years, but Erdös' conjecture seemed to hold until in 2010 Larry Guth and Nets Hawk Katz used an incidence theory approach to show any point set must realize at least &Omega(n/log(n)) distances. In this thesis we will explore how incidence theory played a roll in this process and expand upon recent work by Adam Sheffer and Cosmin Pohoata, using geometric incidences to achieve bounds on the bipartite variant of this problem. A consequence of our extensions on their work is that the theoretical upper bound on the original distinct distances problem of &Omega(n/&radic(log(n))) holds for any point set which is structured such that half of the n points lies on an algebraic curve of arbitrary degree.

[pt] No presente trabalho apresentamos um estudo de curvas silhuetas discretas sobre alguns tipos particulares de malhas, com o objetivo de avaliar propriedades dessas curvas. Nosso objeto de estudo são malhas quadrangulares, ou seja, onde todas as faces sejam quadriláteros e também sejam planares. Em particular dois tipos de malhas são discutidas: circular e cônica. Essas malhas são particularmente interessantes em arquitetura para modelagem de estrutura de vidros. A geração das malhas é feita aplicando-se um processo de otimização e em seguida, sobre essas malhas, definimos curvas discretas como candidatas a silhuetas e buscamos medidas de qualidade para essas curvas. / [en] In this work we study discrete silhouette curves on Planar Quad meshes (PQ meshes), with the objective of evaluate some properties of these curves. PQ meshes correspond to planar quadrilaterals meshes, and our interest is focused particularly on two kinds of meshes: Conical and Circular. They are interesting in architecture for design with glass structures. An optimization process is applied for the mesh generation and we follow defining discrete curves on the meshes to obtain silhouette and to measure their quality.

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