Thesis (Ph. D.)--State University of New York at Binghamton, Department of Mathematical Sciences, 2008. / Includes bibliographical references.

Dans cette thèse, nous proposons une approche combinatoire novatrice fondée sur les matroïdes orientés pour l'étude quantitative de la forme de structures anatomiques 3D. Nous nous basons sur des points de repère qui ont été préalablement localisés par des experts sur la structure anatomique étudiée. La nouveauté de cette méthode provient de l'utilisation de matroïdes orientés. Ces outils mathématiques nous permettent de coder la position relative des points de repère de façon purement combinatoire, c'est-à-dire sans utiliser de notions d'angles ou de distances, en associant un signe (0, + ou -) à chaque sous-ensemble de (d+1) points de repère où d est la dimension de l'espace (dans notre cas 2 ou 3). Dans une première partie, nous supposons qu'il existe des contraintes d'ordres sur chaque axe de coordonnée pour les points de repère. Nous obtenons alors une caractérisation (en dimension 2 et 3) des sous-ensembles de points de repère dont le signe associé est constant, quelles que soient les valeurs des coordonnées satisfaisant les contraintes d'ordre. Dans une deuxième partie, nous cherchons à classifier un ensemble de modèles 3D, en les codant au préalable par ces listes de signes. Nous analysons d'abord comment s'appliquent les algorithmes de clustering classiques, puis nous décrivons comment caractériser des classes de façon directe, à l'aide des signes associés à quelques sous-ensembles de points de repère. Dans une troisième partie, nous détaillons les algorithmes et l'implémentation en machine de cette nouvelle méthode de morphométrie afin de pouvoir l'appliquer à des données réelles. Dans la dernière partie, nous appliquons la méthode sur trois bases de données composées chacune de plusieurs dizaines de points de repères relevés sur plusieurs dizaines à plusieurs centaines de structures crâniennes pour des applications en anatomie comparée, en orthodontie et sur des cas cliniques d'enfants présentant des déformations cranio-faciales. / In this thesis, we propose an innovative combinatorial method based on oriented matroids for the quantitative study of the shape of 3D anatomical structures. We rely on landmarks which were previously defined by experts on the studied anatomical structure. The novelty of this method results from the use of oriented matroids. These mathematical tools allow us to encode the relative position of landmarks in a purely combinatorial way, that is without using concepts of angles or distances, by associating a sign (0, + or -) for each subset of (d+1) landmarks where d is the dimension of space (in our case 2 or 3). In the first part, we assume that there exist constraints of orders on each coordinate axis for the landmarks. We obtain a characterization (in dimension 2 and 3) of the subsets of landmarks of which the associated sign is constant, regardless of the values of the coordinates satisfying the constraints of order. In a second part, we try to classify a set of 3D models, encoding in advance by these lists of signs. We first analyze how to apply classic clustering algorithms, and then describe how to characterize the classes directly, using signs associated with some subsets of landmarks. In the third part, we explain the algorithms and the implementation of this new morphometry method in order to apply it to real data. In the last part, we apply the method to three databases each consisting of several dozens of points defined on several dozens to several hundreds of cranial structures for applications in comparative anatomy, in orthodontics and on clinical cases of children with craniofacial deformities.

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)