Les mots sturmiens sont une façon de coder les droites discrètes apériodiques. Ils ont été étudiés depuis la fin du 19ème siècle et disposent de nombreuses caractérisations. L'une d'elles, obtenue par Vuillon, est centrée sur la notion de mot de retour.Cette thèse a pour objet l'étude des mots sturmiens en dimension 2 vus comme codages des plans discrets apériodiques. L'objectif est d'aller vers une caractérisation des mots sturmiens bi-dimensionnels analogue à celle obtenue par Vuillon en dimension 1.Mais des problèmes propres à la dimension 2 rendent cette étude délicate, tels l'absence de concaténation de mots ou la difficulté à localiser un facteur au sein d'un mot. Afin d'y faire face, nous introduisons en dimension 2 les notions de motifs, motifs pointés, mots de localisation et mots de retour. Nous obtenons ainsi un prolongement à la dimension 2 d'un théorème de Morse et Hedlund concernant certains mots de retour dans un mot sturmien.Ce résultat nous permet d'établir un nouvel algorithme de fractions continues et nous permet de proposer, dans un cadre restreint, une notion de suite dérivée. / Sturmian words are a way to encode aperiodic discrete lines. They have been studied since the end of the 19th century and can be characterized in many ways. One of these characterizations, obtained by Vuillon, centers around the notion of return words.This thesis aims to study 2-dimensional Sturmian words as encodings of aperiodic discrete planes. It is a first step towards a characterization of 2-dimensional Sturmian words analogous to that of Vuillon in dimension 1.However, concerns specific to dimension 2, such as the impossibility to concatenate words or the difficulty to locate a factor inside a word make the study much trickier. To tackle this, we introduce in dimension 2 notions of patterns, pointed patterns, localization words and return words.We obtain a 2-dimensional version of a theorem of Morse and Hedlund concerning certain return words in a Sturmian word. This result enables us to establish a new continued-fractions algorithm and to introduce, in a restricted setting, a notion of derived sequence.

En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure

En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c’est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s’avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s’agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d’autre d’une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l’épaisseur d’un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure / In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension