Notes on Hyperbolic Geometry

And the limitations of Euclidean space for hierarchical data.

Note: This is a compilation of blocks of texts and images gathered from around the internet that I found informative and useful. Sources are listed at the bottom. Thanks to Maria who helped clarify some things.

1. Euclid's Postulates

Grade school mathematics is taught using Euclidean geometry. This assumes Euclid’s axioms (The Elements, 300 BC):

1. A straight line segment can be drawn joining any two points.
2. Any straight line segment can be extended indefinitely in a straight line.
3. Given any straight line segment, a circle can be drawn having the segment as radius and one endpoint as center.
4. All right angles are equal to each other.

However, the "Parallel Postulate" was a source of debate for centuries:

5. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two Right Angles, then the two lines inevitably must intersect each other on that side if extended far enough.

More recently rephrased as Playfair's axiom: In a plane, given a line and a point not on it, at most one line parallel to the given line can be drawn through the point. Attempts to prove it failed because it need not hold true in all cases — leading to the discovery of hyperbolic geometry.

2. Non-Euclidean Geometries

Hyperbolic surfaces can be found in nature. Two common examples are sea slugs (Figure 1) and lettuce (Figure 2). Their wavy structure indicates constant negative curvature, whereas a Euclidean surface has zero curvature and a sphere has positive curvature.

Figure 1: A sea slug.

Figure 2: Lettuce.

Gaussian Curvature

Gaussian curvature measures how a geometric object deviates from a flat plane. Figure 4 shows how a triangle behaves differently on differently curved surfaces.

Figure 3: Examples of the three different types of Gaussian curvature.

Figure 4: Deviation of a triangle under the three different types of Gaussian Curvature.

3. Hyperbolic Geometry and the Poincaré Disc Model

In hyperbolic geometry, for any given line R and point P not on R, there are at least two distinct lines through P that do not intersect R.

The Poincaré disc model represents hyperbolic space as an open disk where space gets infinitely more “dense” as we approach the boundary. Thus, the shortest paths (geodesics) are curved arcs perpendicular to the boundary.

Figure 5: A geodesic between points A and B.

Figure 6: Infinitely many lines through a point parallel to a given line.

Figures 7 & 8: Visualizing the density increase toward the boundary.

A few notable points:

1. The arcs never reach the circumference of the circle. This is analogous to the geodesic on the hyperboloid extending out the infinity, that is, as the arc approaches the circumference it's approaching the "infinity" of the plane.
2. This means distances at the edge of the circle grow exponentially as you move toward the edge of the circle (compared to their Euclidean distances).
3. Each arc approaches the circumference at a 90 degree angle, this just works out as a result of the math of the hyperboloid and the projection.
4. Lines that are parallel can actually diverge from each other (also known as "ultra parallel"). This is a consequence of changing Euclid's 5th postulate regarding parallel lines. In Figure 6, we see that we can have an infinite number of lines intersecting at a single point and still be parallel to another line.

4. Tessellation and Escher

Hyperbolic space is relatively easy to tessellate compared to Euclidean space. M. C. Escher used this to depict infinity in a finite space, inspired by the geometer H. S. M. Coxeter.

Figure 9: Coxeter’s tessellation.

Figure 10: “For me it remains an open question whether [this work] pertains to the realm of mathematics or to that of art.” — M. C. Escher

5. The Limitations of Euclidean Space

Consider a tree with branching factor $b$. The number of nodes grows exponentially with level $l$. In 2D Euclidean space, leaf nodes quickly get squeezed at the edge because we don't have enough "room" — circumference only grows linearly.

Figure 11: Siblings get closer as we move away from the root in Euclidean space.

6. Embedding Trees in Hyperbolic Space

Hyperbolic space matches the exponential growth of trees perfectly. The "distance" between points grows exponentially as we move toward the edge, eliminating the crowding effect.

Figure 12: A tree in hyperbolic space. Every node is actually equidistant from its parent.

The hyperbolic distance formula is:

$$d_{p}(\mathbf{x}, \mathbf{y})=\operatorname{arcosh}\left(1+2 \frac{\|\mathbf{x}-\mathbf{y}\|^{2}}{\left(1-\|\mathbf{x}\|^{2}\right)\left(1-\|\mathbf{y}\|^{2}\right)}\right)$$

Figure 13: Relative hyperbolic distance (red line) approaches the idealized graph distance as we move toward the boundary.

We can’t exactly achieve the graph distance in hyperbolic space, but we can get arbitrarily close! The tradeoff is that we have to push the points increasingly close to the edge of the disk.