Abstract Not Provided. / Thesis / Master of Science (MSc)

Let M_k^2 be the complete, simply connected, Riemannian 2-manifold of constant curvature k ± 0. Let E be a closed, simply connected subspace of M_k^2 with the property that every two points in E are connected by a rectifi able path in E. We show that E is CAT(k) under the induced path metric.

Dans cette thèse, nous étudions des problèmes algorithmiques dans les complexes CAT(0) planaires et rectangulaires munis d'une m ́etrique intrinsèque l_2. Nous proposons des algorithmes de calcul du plus court chemin dans les complexes CAT(0) planaires et rectangulaires et de construction de l'enveloppe convexe d'un ensemble fini de points dans les complexes CAT(0) planaires. E ́tant donné un complexe CAT(0) rectangulaire 2-dimensionnel K à n sommets, nous proposons un algorithme qui, pour toute paire de points calcule la distance et le plus court chemin en temps sous-lin ́eaire en nombre de sommets de K, en utilisant une structure de données de taille O(n^2). Le deuxième problème étudié est celui du plus court chemin entre un point-source donné et tout autre point dans un complexe CAT(0) planaire K a n sommets. Pour cela, nous proposons un algorithme qui, pour tout point y de K, étant donnée le point source x et la carte géodésique SPM(x), construit le plus court chemin γ(x,y) en temps O(n), en utilisant une structure de données de taille O(n^2). Enfin, nous nous intéressons au calcul de l'enveloppe convexe d'un ensemble de k points dans un complexe CAT(0) planaire à n sommets. Nous proposons un algorithme qui construit l'enveloppe convexe en temps O(n^2 + nk log k) en utilisant une structure de données de taille O(n^2 + k). / In this thesis, we study algorithmic problems in CAT(0) planar and rectangular complexes with an intrinsic l_2−metric. We present algorithms for some algorithmic problems, such as computing the shortest path and the convex hull of a finite set of points in CAT(0) planar and rectangular complexes. We present an efficient algorithm for answering two-point distance queries in a given CAT(0) rectangular complex K with n vertices. Namely, we show that for a CAT(0) rectangular complex K with n vertices, one can construct a data structure of size O(n^2) so that, given any two points in K, the shortest path can be computed in subliniar time of n. The second problem presented is computing shortest path from a single-source to the query point in a CAT(0) planar complex. We propose an algorithm which computes in O(n) time the shortest path between a given point and the query point in a CAT(0) planar complex with n vertices, using a given shortest path map and data structure of size O(n^2). Finally, we study the problem of computing the convex hull of a set of k points in a CAT(0) planar complex with n vertices. We describe an algorithm which computes the convex hull in O(n^2 + nk log k) time, using a data structure of size O(n^2 + k).

My dissertation focuses on the existence of metrics of non-positive curvature for the simplicial complexes constructed recently by Tom Brady and Daan Krammer for the braid groups and other Artin groups of finite type. In particular, for each Artin group of finite type, there is a recently constructed finite simplicial Eilenberg-Mac Lane space known as its Brady-Krammer complex. The Brady-Krammer complexes are highly symmetric objects. Prior work on the relationship between the Brady-Krammer complexes and the theory of CAT(0)spaces has produced some positive results in low-dimensions. More specifically, the Brady-Krammer complexes of dimension at most 3 have been shown to support piecewise Euclidean metrics of non-positive curvature. Similarly, the 4dimensional Brady-Krammer complexes of type A4 and type B4 also support such metrics. In every instance, the metrics assigned respect all of the symmetries alluded to above. The main results of my dissertation show that this pattern does not extend to the Brady-Krammer complexes of type F4 and D4. These are the first negative results known about the curvature of these Brady-Krammer complexes. The proofs of my main theorems involve a combination of combinatorial results and computer calculations. These negative results are particularly striking since Ruth Charney, John Meier and Kim Whittlesey have shown that a particular complex closely related to each Brady-Krammer complex admits an asymmetric metric satisfying a weak version of non-positive curvature. Thus, one corollary of my results is that the weak asymmetric version of a CAT(0) metric (initially defined by Mladen Bestvina) is strictly weaker than the traditional version.

My dissertation focuses on the existence of metrics of non-positive curvature for the simplicial complexes constructed recently by Tom Brady and Daan Krammer for the braid groups and other Artin groups of finite type. In particular, for each Artin group of finite type, there is a recently constructed finite simplicial Eilenberg-Mac Lane space known as its Brady-Krammer complex. The Brady-Krammer complexes are highly symmetric objects. Prior work on the relationship between the Brady-Krammer complexes and the theory of CAT(0)spaces has produced some positive results in low-dimensions. More specifically, the Brady-Krammer complexes of dimension at most 3 have been shown to support piecewise Euclidean metrics of non-positive curvature. Similarly, the 4dimensional Brady-Krammer complexes of type A4 and type B4 also support such metrics. In every instance, the metrics assigned respect all of the symmetries alluded to above. The main results of my dissertation show that this pattern does not extend to the Brady-Krammer complexes of type F4 and D4. These are the first negative results known about the curvature of these Brady-Krammer complexes. The proofs of my main theorems involve a combination of combinatorial results and computer calculations. These negative results are particularly striking since Ruth Charney, John Meier and Kim Whittlesey have shown that a particular complex closely related to each Brady-Krammer complex admits an asymmetric metric satisfying a weak version of non-positive curvature. Thus, one corollary of my results is that the weak asymmetric version of a CAT(0) metric (initially defined by Mladen Bestvina) is strictly weaker than the traditional version.