Unlike the previous two posts it will not be obvious how what we will discuss connects to phylogeny. Furthermore, we will be diving into a noticeably more mathematically dense content this time. I will try to use some analogies and visual aids through out this post in order to make the material slightly more accessible.

## Introduction

Geometry is a wonderful subject (even if I struggled with it in high school) that makes appearances in many aspects of various sciences (including social ones). However, musing about geometry at large is better left to people who are (a) more proficient in the study of it, and (b) have an acumen for writing more lengthy works, hence I will simply point you in the direction of Jordan Ellenberg’s *Shape*. What we will concern ourselves with today is a more specific slice of the geometry in which we will look at *metric spaces* of *non-positive curvature*. I will not define the notion of a metric space again, as you can simply navigate either to the previous post in the series or Wikipedia. The bulk of this post will consist of defining *non-positive curvature*, and then we will follow up with a few properties of such spaces, and some examples.

Most of the content that follows will adopt the definitions and notation from Bridson and Haefliger, 2013.

## Geodesics

Geodesics are a natural notion extending the concept of the “shortest” path curve to general metric space framework. More precisely, given a metric space a * geodesic* from to is the map s.t. and . We will call a metric space a

*geodesic space*if for any there exists a geodesic from to . Furthermore, if for all pairs of points such geodesic is unique we will call such space

*uniquely geodesic*(see Bridson and Haefliger, 2013, pp. 4-8 for additional details and examples).

For example, the classic Euclidean space is uniquely geodesic with the geodesics given by straight lines, i.e. for any two points we have the geodesic given by . On a sphere geodesic between two points is the arc segment obtained by intersecting a plane through , and the center of the sphere with the surface (i.e. the great circle arc). An example of a geodesic triangle on a sphere is given below (image courtesy of Wikipedia).

Note, that a sphere is not a *uniquely geodesic* space, since any pair of diametrically opposed points has an infinite set of possible geodesics between them.

## Triangles

Just like the notion of a geodesic extends our naïve understanding of the shortest paths, the notion of a *geodesic triangle* (Bridson and Haefliger, 2013, p. 158) extends our notion of a triangle. Given a metric space a * geodesic triangle* is a set of tree points called

*vertices*and a choice of three geodesic segments joining them called

*sides*, we will denote such a triangle or more briefly . Note, that the later notation is not precise, as in the case of a non-uniquely geodesic space there is not necessarily a unique choice of a geodesic between two vertices. Finally, we will write to indicate that belongs to the union .

In order to define a CAT(*k*) space we also need the notion of a comparison triangle. In order to avoid a lengthy (and somewhat involved) discussion of the nuances about the model spaces and corresponding notation, we will focus on three general types of model spaces: Euclidean *n-*dimensional space, the *n-*sphere, and hyperbolic *n-*space. We already defined geodesics in the case of . For the *n-*sphere we will define the metric via cosine distance where the inner product is in the corresponding embedding and the corresponding geodesics are given by *minimal great arcs* (for full definition and description see Bridson and Haefliger, 2013, pp. 16-17). For the hyperbolic *n-*space we will use the same construction as Bridson and Haefliger, 2013 (p. 18-20) by considering the space which consists of with bilinear form and defining . The distance on this space will be given by (similarly to the sphere case, see Bridson and Haefliger, 2013, pp. 18-23 for details).

Finally, a ** comparison triangle** is a triangle in the model space that satisfies , , and . A point for is called a

*if . Note, that for we need an additional condition on the perimeter of a triangle to guarantee existence of a*

**comparison point***comparison triangle*, for the purposes of this post we will state the condition, but not elaborate on it in detail.

## CAT(*k*)

So what’s a cat? It’s a gorgeous animal that many humans have as a pet. Many cats are fluffy, and so is mine. Also cats are silly and generally cool to have around. However, this post is not about these kinds of cats.

The term “CAT(*k*)” space was coined by Mikhail Gromov and consists of three initials honoring: Élie Cartan, Alexander D. Alexandrov, and Victor A. Toponogov. Now, we will define a *CAT(k)* space. Let be a metric space and let be a real number. Let be a geodesic triangle in with perimeter less than (the diameter of the space, this is the condition need to guarantee the existence of comparison triangle). Then we say that satisfies the ** CAT(k) inequality** if for the corresponding comparison triangle and all with corresponding comparison points the inequality is satisfied. Thus, for a we will call a

**space if is geodesic and all its geodesic triangles satisfy the**

*CAT(k)**CAT(k) inequality*. For , we relax definition by only requiring to be -geodesic and only requiring the inequality condition for triangles of perimeter bounded by .

Finally, we will call a space to be of curvature at most if it is locally a *CAT(k)* space. Hence, any space that is (locally) CAT(0) is a space on *non-positive curvature* (in the Alexandrov sense).

Intuitively speaking the triangles in a CAT(*k*) space have to be thinner than the ones in the corresponding model space. In particular, triangles in CAT(0) spaces are thinner than those in the regular Euclidean space (namely given two points on the sides of a triangle the distance between them in CAT(0) space is less than or equal to the distance between the corresponding comparison points in the Euclidean space). The illustration below shows three model spaces (sphere, plane, and hyperbolical paraboloid) and a cat drawn in each space. You can see that sphere cat is chubbier than the flat cat, which is chubbier than the hyperbolic cat, turns out triangles in these spaces are also of different chubbiness.

For the rest of the post we will focus specifically on the case of the CAT(0) spaces, as they present the most interest to us in the follow up posts.

An immediate, but important consequence of the definition of a CAT(*k*) space is that any CAT(0) space is *uniquely geodesic*. Note, that being *uniquely geodesic* also implies that a space is contractible (the converse does not hold, there are contractible spaces that are not *uniquely geodesic*, a simple example is the closed upper hemisphere which is clearly contractible, and also not uniquely geodesic for the same reason a sphere isn’t).

Next, we will briefly describe some interesting spaces which under certain conditions turn out to be CAT(0).

## My CAT is a cubical complex!

Let be the unit interval, then we call the *n-*fold product the unit ** cube**. We will let denote a point by convention. Since we will be mainly operating in dimensions, we will use the term “face” to describe any-dimensional face of the cube. Thus, the faces of are $\{0\}, \{1\}$ (the 0-dimensional faces), and (the 1-dimensional face). Analogously, for a

**face****is a subset which can be written as where each is a face of . The dimension of the face will be the sum of dimensions of , and we also note that a**

*k*-dimensional face will be isometric to .

Now, we are ready to define a *cubical complex* (Def. 7.32 from Bridson and Haefliger, 2013) in a similar vein to the definition of a simplicial complex (for those familiar with the latter construction). A ** cubical complex** is the quotient of a disjoint union of cubes by an equivalence relation with the restrictions of the natural projection satisfying

- for every the map is injective;
- if then there is an isometry from a face onto a face such that .

Note, that in general a cubical complex needs not be a CAT(0) space. However, the following theorem of Gromov, 1987 gives the necessary and sufficient conditions for a cubical complex to be CAT(0).

**Theorem 1.** A cubical complex with the intrinsic Euclidean metric is CAT(0) if and only if is connected, simply connected, and for all natural : if three -cubes of share a common -cube and pairwise share common distinct -cubes, then they are contained within a -cube in .

## A bit of perspective

In many cases the underlying geometry of the solution space can make or break our ability to solve problems efficiently. For example, many interesting discrete problems are NP-hard, and often do not even have good approximations (for a deeper dive Google “inapproximability results”, Khot, 2010 gives a great overview). In general, computing geodesics is a hard problem, but in certain spaces we can still efficiently compute (meaning in polynomial time) or approximate geodesics. CAT(0) cubical complexes are one particular class of “nice” spaces, meaning that geodesics can be computed or approximated well enough in polynomial time (Owen, and Provan, 2010, Hayashi, 2021). Implications of these algorithmic results mean that in certain phylogenetic (and robotics) problems we are able to efficiently compute distance between two points in the space, and reconstruct the optimal path between them (or at least do so up to error).

## Code and data availability

All code used in this post is available in the following Jupyter notebook.

## What’s next

The next post in the series will take us back to the world of phylogeny, but this time armed with the knowledge about CAT(0) spaces. We will try to make sense of defining *nice* metrics on the space of phylogenetic trees with branch lengths, and learn a thing or two in the process. Essentially, the idea for the remainder of this stretch of the series will be to work our way through the paper of Gavryushkin and Drummond, 2016 on the space of ultrametric phylogenetic trees.

## References

Bridson, Martin R., and André Haefliger. *Metric spaces of non-positive curvature*. Vol. 319. Springer Science & Business Media, 2013. https://doi.org/10.1007/978-3-662-12494-9

Gavryushkin, Alex, and Alexei J. Drummond. “The space of ultrametric phylogenetic trees.” *Journal of theoretical biology* 403 (2016): 197-208. arXiv:1410.3544

Gromov, Mikhael. “Hyperbolic groups.” In *Essays in group theory*, pp. 75-263. Springer, New York, NY, 1987. https://doi.org/10.1007/978-1-4613-9586-7_3

Hayashi, Koyo. “A polynomial time algorithm to compute geodesics in CAT (0) cubical complexes.” *Discrete & Computational Geometry* 65, no. 3 (2021): 636-654. arXiv:1710.09932

Khot, Subhash. “Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry.” In *Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures*, pp. 2676-2697. 2010. https://cs.nyu.edu/~khot/papers/icm-khot.pdf

Owen, Megan, and J. Scott Provan. “A fast algorithm for computing geodesic distances in tree space.” *IEEE/ACM Transactions on Computational Biology and Bioinformatics* 8, no. 1 (2010): 2-13. https://doi.org/10.1109/TCBB.2010.3

Pingback: Phylogenetic Vignettes: 𝛕-space – Nicolae's Homepage

Pingback: Phylogenetic Vignettes: Owen-Provan algorithm – Nicolae's Homepage