1,720,966 research outputs found
Hyperplans arithmétiques : connexité, reconnaissance & transformations
No full textThe discrete world is littered with discrete mathematical structures, designed to be easily manipulated by a computer while giving our brains the impression that they are beautiful continuous real shapes. Digital images can thus be seen as subsets of . In discrete geometry, we are interested in structures and seek to establish geometric or topological properties on these objects. While the questions we ask are relatively simple in Euclidean geometry, they become much more difficult in discrete geometry: no more division, no more limits, everything is just arithmetic. This thesis is also an opportunity to juggle many elementary notions of mathematics and computer science (linear algebra, rings, automata, real analysis, arithmetic, combinatorics) to solve discrete geometry questions.Le monde numérique est parsemé de structures mathématiques discrètes, destinées à être facilement manipulables par un ordinateur tout en donnant à notre cerveau l’impression d’être de belles formes réelles continues. Les images numériques peuvent ainsi être vues comme des sous-ensembles de Z^2. En géométrie discrète, nous nous intéressons aux structures de Z^d et cherchons à établir des propriétés géométriques ou topologiques sur ces objets. Si les questions que nous nous posons sont relativement simples en géométrie euclidienne, elles deviennent beaucoup plus difficiles en géométrie discrète : plus de division, adieu les limites, tout n’est plus qu’arithmétique. Cette thèse est également l'occasion de jongler avec de nombreuses notions élémentaires de mathématiques et d'informatique (algèbre linéaire, anneaux, automates, analyse réelle, arithmétique, combinatoire) pour résoudre des questions de géométrie discrète.Nous nous intéressons à des structures fondamentales de cette géométrie : les hyperplans arithmétiques. Ceux-ci ont en effet une définition très simple et purement arithmétique : un hyperplan arithmétique est l'ensemble des points entiers situés entre deux hyperplans (réels) affines parallèles. Nous parlons dans cette thèse de trois problèmes portant sur les hyperplans arithmétiques : - la connexité : un hyperplan arithmétique est-il composé d’un seul morceau ou de plusieurs ? Apport principal de ce manuscrit, nous étendons des résultats déjà connus pour la connexité par faces pour des voisinages quelconques. Si certains phénomènes demeurent dans le cas général, l'explosion combinatoire rend difficile l'adaptation des algorithmes connus pour résoudre le problème. Nous adoptons donc une approche analytique et prouvons des propriétés de connexité en étudiant la régularité d'une fonction. - la reconnaissance : comment connaître les caractéristiques d’un hyperplan arithmétique ? Problème plus classique de géométrie discrète, avec une littérature très riche, nous proposons pour le résoudre un algorithme de reconnaissance reposant sur l'arbre de Stern-Brocot généralisé. Nous introduisons notamment la notion de corde séparante qui caractérise géométriquement les zones auxquelles appartiennent les paramètres d'un hyperplan arithmétique. - les transformations douces : comment transformer continûment un hyperplan arithmétique via des translations ou rotations ? Approche discrète des transformations homotopiques, nous caractérisons les mouvements de pixels possibles dans une structure discrète tout en préservant ses propriétés géométriques.Au-delà de l’étude de ces problèmes et des résultats que nous avons pu obtenir, cette thèse montre l’intérêt d’utiliser des réels, et notamment de l’analyse réelle, pour mieux comprendre les hyperplans arithmétiques. Ces derniers sont en effet caractérisés en grande partie par leur vecteur normal, souvent considéré entier pour obtenir des propriétés de périodicité. Considérer des vecteurs normaux réels quelconques permet de gagner en souplesse, et de faire disparaître les phénomènes de bruit induits par les relations arithmétiques du vecteur. S’ouvrir de nouveau au réel est enfin un moyen de créer des ponts vers d’autres branches des mathématiques, comme la combinatoire des mots ou les systèmes de numération
Hyperplans arithmétiques : connexité, reconnaissance & transformations
No full textThe discrete world is littered with discrete mathematical structures, designed to be easily manipulated by a computer while giving our brains the impression that they are beautiful continuous real shapes. Digital images can thus be seen as subsets of . In discrete geometry, we are interested in structures and seek to establish geometric or topological properties on these objects. While the questions we ask are relatively simple in Euclidean geometry, they become much more difficult in discrete geometry: no more division, no more limits, everything is just arithmetic. This thesis is also an opportunity to juggle many elementary notions of mathematics and computer science (linear algebra, rings, automata, real analysis, arithmetic, combinatorics) to solve discrete geometry questions.Le monde numérique est parsemé de structures mathématiques discrètes, destinées à être facilement manipulables par un ordinateur tout en donnant à notre cerveau l’impression d’être de belles formes réelles continues. Les images numériques peuvent ainsi être vues comme des sous-ensembles de Z^2. En géométrie discrète, nous nous intéressons aux structures de Z^d et cherchons à établir des propriétés géométriques ou topologiques sur ces objets. Si les questions que nous nous posons sont relativement simples en géométrie euclidienne, elles deviennent beaucoup plus difficiles en géométrie discrète : plus de division, adieu les limites, tout n’est plus qu’arithmétique. Cette thèse est également l'occasion de jongler avec de nombreuses notions élémentaires de mathématiques et d'informatique (algèbre linéaire, anneaux, automates, analyse réelle, arithmétique, combinatoire) pour résoudre des questions de géométrie discrète.Nous nous intéressons à des structures fondamentales de cette géométrie : les hyperplans arithmétiques. Ceux-ci ont en effet une définition très simple et purement arithmétique : un hyperplan arithmétique est l'ensemble des points entiers situés entre deux hyperplans (réels) affines parallèles. Nous parlons dans cette thèse de trois problèmes portant sur les hyperplans arithmétiques : - la connexité : un hyperplan arithmétique est-il composé d’un seul morceau ou de plusieurs ? Apport principal de ce manuscrit, nous étendons des résultats déjà connus pour la connexité par faces pour des voisinages quelconques. Si certains phénomènes demeurent dans le cas général, l'explosion combinatoire rend difficile l'adaptation des algorithmes connus pour résoudre le problème. Nous adoptons donc une approche analytique et prouvons des propriétés de connexité en étudiant la régularité d'une fonction. - la reconnaissance : comment connaître les caractéristiques d’un hyperplan arithmétique ? Problème plus classique de géométrie discrète, avec une littérature très riche, nous proposons pour le résoudre un algorithme de reconnaissance reposant sur l'arbre de Stern-Brocot généralisé. Nous introduisons notamment la notion de corde séparante qui caractérise géométriquement les zones auxquelles appartiennent les paramètres d'un hyperplan arithmétique. - les transformations douces : comment transformer continûment un hyperplan arithmétique via des translations ou rotations ? Approche discrète des transformations homotopiques, nous caractérisons les mouvements de pixels possibles dans une structure discrète tout en préservant ses propriétés géométriques.Au-delà de l’étude de ces problèmes et des résultats que nous avons pu obtenir, cette thèse montre l’intérêt d’utiliser des réels, et notamment de l’analyse réelle, pour mieux comprendre les hyperplans arithmétiques. Ces derniers sont en effet caractérisés en grande partie par leur vecteur normal, souvent considéré entier pour obtenir des propriétés de périodicité. Considérer des vecteurs normaux réels quelconques permet de gagner en souplesse, et de faire disparaître les phénomènes de bruit induits par les relations arithmétiques du vecteur. S’ouvrir de nouveau au réel est enfin un moyen de créer des ponts vers d’autres branches des mathématiques, comme la combinatoire des mots ou les systèmes de numération
Hyperplans arithmétiques : connexité, reconnaissance & transformations
No full textThe discrete world is littered with discrete mathematical structures, designed to be easily manipulated by a computer while giving our brains the impression that they are beautiful continuous real shapes. Digital images can thus be seen as subsets of . In discrete geometry, we are interested in structures and seek to establish geometric or topological properties on these objects. While the questions we ask are relatively simple in Euclidean geometry, they become much more difficult in discrete geometry: no more division, no more limits, everything is just arithmetic. This thesis is also an opportunity to juggle many elementary notions of mathematics and computer science (linear algebra, rings, automata, real analysis, arithmetic, combinatorics) to solve discrete geometry questions.Le monde numérique est parsemé de structures mathématiques discrètes, destinées à être facilement manipulables par un ordinateur tout en donnant à notre cerveau l’impression d’être de belles formes réelles continues. Les images numériques peuvent ainsi être vues comme des sous-ensembles de Z^2. En géométrie discrète, nous nous intéressons aux structures de Z^d et cherchons à établir des propriétés géométriques ou topologiques sur ces objets. Si les questions que nous nous posons sont relativement simples en géométrie euclidienne, elles deviennent beaucoup plus difficiles en géométrie discrète : plus de division, adieu les limites, tout n’est plus qu’arithmétique. Cette thèse est également l'occasion de jongler avec de nombreuses notions élémentaires de mathématiques et d'informatique (algèbre linéaire, anneaux, automates, analyse réelle, arithmétique, combinatoire) pour résoudre des questions de géométrie discrète.Nous nous intéressons à des structures fondamentales de cette géométrie : les hyperplans arithmétiques. Ceux-ci ont en effet une définition très simple et purement arithmétique : un hyperplan arithmétique est l'ensemble des points entiers situés entre deux hyperplans (réels) affines parallèles. Nous parlons dans cette thèse de trois problèmes portant sur les hyperplans arithmétiques : - la connexité : un hyperplan arithmétique est-il composé d’un seul morceau ou de plusieurs ? Apport principal de ce manuscrit, nous étendons des résultats déjà connus pour la connexité par faces pour des voisinages quelconques. Si certains phénomènes demeurent dans le cas général, l'explosion combinatoire rend difficile l'adaptation des algorithmes connus pour résoudre le problème. Nous adoptons donc une approche analytique et prouvons des propriétés de connexité en étudiant la régularité d'une fonction. - la reconnaissance : comment connaître les caractéristiques d’un hyperplan arithmétique ? Problème plus classique de géométrie discrète, avec une littérature très riche, nous proposons pour le résoudre un algorithme de reconnaissance reposant sur l'arbre de Stern-Brocot généralisé. Nous introduisons notamment la notion de corde séparante qui caractérise géométriquement les zones auxquelles appartiennent les paramètres d'un hyperplan arithmétique. - les transformations douces : comment transformer continûment un hyperplan arithmétique via des translations ou rotations ? Approche discrète des transformations homotopiques, nous caractérisons les mouvements de pixels possibles dans une structure discrète tout en préservant ses propriétés géométriques.Au-delà de l’étude de ces problèmes et des résultats que nous avons pu obtenir, cette thèse montre l’intérêt d’utiliser des réels, et notamment de l’analyse réelle, pour mieux comprendre les hyperplans arithmétiques. Ces derniers sont en effet caractérisés en grande partie par leur vecteur normal, souvent considéré entier pour obtenir des propriétés de périodicité. Considérer des vecteurs normaux réels quelconques permet de gagner en souplesse, et de faire disparaître les phénomènes de bruit induits par les relations arithmétiques du vecteur. S’ouvrir de nouveau au réel est enfin un moyen de créer des ponts vers d’autres branches des mathématiques, comme la combinatoire des mots ou les systèmes de numération
Arithmetical hyperplanes : connexity, recognition and transformations
No full textLe monde numérique est parsemé de structures mathématiques discrètes, destinées à être facilement manipulables par un ordinateur tout en donnant à notre cerveau l'impression d'être de belles formes réelles continues. Les images numériques peuvent ainsi être vues comme des sous-ensembles de Z^2. En géométrie discrète, nous nous intéressons aux structures de Z^d et cherchons à établir des propriétés géométriques ou topologiques sur ces objets. Si les questions que nous nous posons sont relativement simples en géométrie euclidienne, elles deviennent beaucoup plus difficiles en géométrie discrète : plus de division, adieu les limites, tout n'est plus qu'arithmétique. Cette thèse est également l'occasion de jongler avec de nombreuses notions élémentaires de mathématiques et d'informatique (algèbre linéaire, anneaux, automates, analyse réelle, arithmétique, combinatoire) pour résoudre des questions de géométrie discrète. Nous nous intéressons à des structures fondamentales de cette géométrie : les hyperplans arithmétiques. Ceux-ci ont en effet une définition très simple et purement arithmétique : un hyperplan arithmétique est l'ensemble des points entiers situés entre deux hyperplans (réels) affines parallèles. Nous parlons dans cette thèse de trois problèmes portant sur les hyperplans arithmétiques : - la connexité : un hyperplan arithmétique est-il composé d'un seul morceau ou de plusieurs ? Apport principal de ce manuscrit, nous étendons des résultats déjà connus pour la connexité par faces pour des voisinages quelconques. Si certains phénomènes demeurent dans le cas général, l'explosion combinatoire rend difficile l'adaptation des algorithmes connus pour résoudre le problème. Nous adoptons donc une approche analytique et prouvons des propriétés de connexité en étudiant la régularité d'une fonction. - la reconnaissance : comment connaître les caractéristiques d'un hyperplan arithmétique ? Problème plus classique de géométrie discrète, avec une littérature très riche, nous proposons pour le résoudre un algorithme de reconnaissance reposant sur l'arbre de Stern-Brocot généralisé. Nous introduisons notamment la notion de corde séparante qui caractérise géométriquement les zones auxquelles appartiennent les paramètres d'un hyperplan arithmétique. - les transformations douces : comment transformer continûment un hyperplan arithmétique via des translations ou rotations ? Approche discrète des transformations homotopiques, nous caractérisons les mouvements de pixels possibles dans une structure discrète tout en préservant ses propriétés géométriques. Au-delà de l'étude de ces problèmes et des résultats que nous avons pu obtenir, cette thèse montre l'intérêt d'utiliser des réels, et notamment de l'analyse réelle, pour mieux comprendre les hyperplans arithmétiques. Ces derniers sont en effet caractérisés en grande partie par leur vecteur normal, souvent considéré entier pour obtenir des propriétés de périodicité. Considérer des vecteurs normaux réels quelconques permet de gagner en souplesse, et de faire disparaître les phénomènes de bruit induits par les relations arithmétiques du vecteur. S'ouvrir de nouveau au réel est enfin un moyen de créer des ponts vers d'autres branches des mathématiques, comme la combinatoire des mots ou les systèmes de numération.The digital world is littered with discrete mathematical structures, designed to be easily manipulated by a computer while giving our brains the impression of beautiful continuous real shapes. Digital images can thus be seen as subsets of Z^2. In discrete geometry, we are interested in the structures of Z^d and seek to establish geometric or topological properties on these objects. While the questions we ask are relatively simple in Euclidean geometry, they become much more difficult in discrete geometry: no more division, goodbye to limits, everything is just arithmetic. This thesis is also an opportunity to juggle many elementary notions of mathematics and computer science (linear algebra, rings, automata, real analysis, arithmetic, combinatorics) to solve discrete geometry questions. We are interested in the fundamental structures of this geometry: arithmetic hyperplanes. These have a very simple and purely arithmetical definition: an arithmetical hyperplane is the set of integer points lying between two parallel (real) affine hyperplanes. In this thesis, we discuss three problems involving arithmetic hyperplanes:- connectedness: is an arithmetic hyperplane composed of a single piece or of several pieces? The main contribution of this manuscript is to extend results already known for facewise connectedness for any neighbourhood. While certain phenomena remain in the general case, the combinatorial explosion makes it difficult to adapt known algorithms to solve the problem. We therefore adopt an analytical approach and prove connectivity properties by studying the regularity of a function. - recognition: how can we find out the characteristics of an arithmetic hyperplane? This is a more traditional problem in discrete geometry, with a very rich literature. To solve it, we propose a recognition algorithm based on the generalised Stern-Brocot tree. In particular, we introduce the notion of separating chord, which geometrically characterises the zones to which the parameters of an arithmetic hyperplane belong. - soft transformations: how can an arithmetic hyperplane be continuously transformed using translations or rotations? A discrete approach to homotopic transformations, we characterise the possible pixel movements in a discrete structure while preserving its geometric properties. Beyond the study of these problems and the results we were able to obtain, this thesis shows the interest of using the reals, and in particular real analysis, to better understand arithmetic hyperplanes. Arithmetic hyperplanes are largely characterised by their normal vector, which is often considered integer to obtain periodicity properties. Considering any real normal vectors provides greater flexibility and eliminates the noise induced by the arithmetic relationships of the vector. Finally, opening up to the real again is a way of building bridges to other branches of mathematics, such as word combinatorics or numbering systems
Statures and Sobrification Ranks of Noetherian Spaces
No full textThere is a rich theory of maximal order types of well-partial-orders (wpos),
pioneered by de Jongh and Parikh (1977) and Schmidt (1981). Every wpo is
Noetherian in its Alexandroff topology, and there are more; this prompts us to
investigate an analogue of that theory in the wider context of Noetherian
spaces.
The notion of maximal order type does not seem to have a direct analogue in
Noetherian spaces per se, but the equivalent notion of stature, investigated by
Blass and Gurevich (2008) does: we define the stature of a Noetherian
space as the ordinal rank of its poset of proper closed subsets. We obtain
formulas for statures of sums, of products, of the space of words on a space
, of the space of finite multisets on , in particular. They confirm
previously known formulas on wpos, and extend them to Noetherian spaces.
The proofs are, by necessity, rather different from their wpo counterparts,
and rely on explicit characterizations of the sobrifications of the
corresponding spaces, as obtained by Finkel and the first author (2020).
We also give formulas for the statures of some natural Noetherian spaces that
do not arise from wpos: spaces with the cofinite topology, Hoare powerspaces,
powersets, and spaces of words on with the so-called prefix topology.
Finally, because our proofs require it, and also because of its independent
interest, we give formulas for the ordinal ranks of the sobrifications of each
of those spaces, which we call their sobrification ranks.Comment: 68 pages, 1 figure, 1 table. Initial maps are now called ful
Sur la connexité des hyperplans arithmétiques
No full textInternational audienceDiscrete geometry is a geometry specific to computers that studies structures. It appears naturally in image analysis or 3D printing. Our goal is to find efficient algorithms to characterise these geometric structures and their properties.We are interested in a fundamental structure of discrete geometry, the arithmetic hyperplanes, and more particularly in their connectedness. Many works have studied a connectedness defined from the neighbourhood by faces and have allowed to observe a percolation phenomenon. These studies have also allowed to decide the connectedness of a plane in an efficient way. We propose an extension of these results in the case of connectivity defined from general neighbourhoods.Beyond the new concepts that this extension requires, the main contribution of the paper lies in the use of analysis to solve this arithmetic problem and in the design of an algorithm that decides the general connectedness problem. The study of the thickness of connectedness as a function reveals discontinuities at each rational point. However, a much more regular underlying structure appears in the irrational case. Thus, the consideration of irrational vectors allows a simpler approach to the connectedness of arithmetic hyperplanes.La géométrie discrète est une géométrie propre aux ordinateurs qui étudie les structures de . Celle-ci apparaît naturellement en analyse d'images ou en impression 3D. Notre but est de trouver des algorithmes efficaces pour caractériser ces structures géométriques et leurs propriétés.Nous nous intéressons à une structure fondamentale de la géométrie discrète, les hyperplans arithmétiques, et plus particulièrement à leur connexité. De nombreux travaux ont étudié une connexité définie à partir du voisinage par faces et ont permis d'observer un phénomène de percolation. Ces études ont également permis de décider la connexité d'un plan de manière efficace. Nous proposons une extension de ces résultats dans le cas de connexités définies à partir de voisinages généraux.Au-delà des nouveaux concepts que demande cette extension, l'apport principal de l'article réside dans l'utilisation de l'analyse pour résoudre ce problème arithmétique et dans la conception d'un algorithme qui décide le problème général de la connexité. L'étude de l'épaisseur de connexité en tant que fonction fait ressortir des discontinuités en chaque point rationnel. Toutefois, une fractale sous-jacente bien plus régulière apparaît dans le cas irrationnel. Ainsi, la considération de vecteurs irrationnels permet une approche plus simple de la connexité des hyperplans arithmétiques
On the connectedness of arithmetic hyperplanes
No full textsoumis à Therotical Computer ScienceWe are interested in a fundamental structure of discrete geometry, the arithmetic hyper-planes, and more particularly in their connectedness. Many works have studied a connectedness definedfrom the neighbourhood by faces and have observed a percolation phenomenon. We propose an exten-sion of these results in the case of connectivity defined from general neighbourhoods.Beyond the new concepts required by this extension, the main contribution of the article lies in the useof analysis to solve this arithmetic problem. The study of the connecting thickness as a function thenbrings out discontinuities at each rational point but an underlying fractal that is much more regularin the irrational case. Thus, the consideration of irrational vectors allows a simpler approach to theconnectedness of arithmetic hyperplanes
Autour de la ∆-numération
No full textInternational audienceIn this article we study a numeration system previously used to prove combinatorial properties in discrete geometry: the ∆-numeration. Since this system, introduced via the fully subtractive algorithm, has been seen mainly as a tool, we propose here to study it from the point of view of numeration systems. In particular, we make the link with βnumeration and Cantor real bases. We reintroduce the rewriting system introduced to calculate in ∆-numeration. This systems is based on the properties of the fully subtractive algorithm and is normalising. Finally, we study the ultimately periodic case, a special case of alternate bases, and show that the ultimately periodic words represent exactly the elements of Q[β] where β is the inverse of a Pisot number.Nous étudions dans cet article un système de numération utilisé auparavant pour prouver des propriétés combinatoires en géométrie discrète : la ∆-numération. Ce système, introduit via l'algorithme totalement soustractif, ayant été essentiellement vu en tant qu'outil, nous proposons ici de l'étudier du point de vue des systèmes de numération. Nous faisons notamment le lien avec la β-numération et les bases réelles de Cantor. Nous redonnons le système de réécriture introduit pour calculer en ∆-numération. Celui-ci est fondé sur les propriétés de l'algorithme totalement soustractif et est normalisant. Enfin, nous étudions le cas ultimement périodique, cas particulier des bases alternées, et montrons que les mots ultimement périodiques représentent exactement les éléments de Q[β] où β est l'inverse d'un nombre de Pisot
Autour de la ∆-numération
No full textInternational audienceIn this article we study a numeration system previously used to prove combinatorial properties in discrete geometry: the ∆-numeration. Since this system, introduced via the fully subtractive algorithm, has been seen mainly as a tool, we propose here to study it from the point of view of numeration systems. In particular, we make the link with βnumeration and Cantor real bases. We reintroduce the rewriting system introduced to calculate in ∆-numeration. This systems is based on the properties of the fully subtractive algorithm and is normalising. Finally, we study the ultimately periodic case, a special case of alternate bases, and show that the ultimately periodic words represent exactly the elements of Q[β] where β is the inverse of a Pisot number.Nous étudions dans cet article un système de numération utilisé auparavant pour prouver des propriétés combinatoires en géométrie discrète : la ∆-numération. Ce système, introduit via l'algorithme totalement soustractif, ayant été essentiellement vu en tant qu'outil, nous proposons ici de l'étudier du point de vue des systèmes de numération. Nous faisons notamment le lien avec la β-numération et les bases réelles de Cantor. Nous redonnons le système de réécriture introduit pour calculer en ∆-numération. Celui-ci est fondé sur les propriétés de l'algorithme totalement soustractif et est normalisant. Enfin, nous étudions le cas ultimement périodique, cas particulier des bases alternées, et montrons que les mots ultimement périodiques représentent exactement les éléments de Q[β] où β est l'inverse d'un nombre de Pisot
- …
