This is a talk about user interface of Google Maps: a tale of an amazingly efficient design, and the simple geometry behind it.

As a reminder, Google Maps was launched as a web application in 2005 after the acquisition by Google of Where2, an Australian startup.

In 2007 Google Maps became the default map application on just released iPhones, with the Android version launched a year later.

In 2012 Apple developed its own version of the application, Apple Maps. As the technology matured, other apps emerged, but they share the key features I am interested in.

This talk focusses on the ease of navigation of the viewport space. A viewport is what you see on the screen, - a rectangular fragment of a map.

A viewport in this setting is a rectangle aligned with the coordinate axes of the resulting plane (we ignore rotations, which do not change much in our the story), with a fixed aspect ratio.

A natural way to think about a viewport is to imagine that you're viewing the planar map below through a rectangular window (``port``) while hovering above it at a certain height. With this in mind, we can describe a viewport by fixing the point on the plane $(x,y)$ above which we hover, and the height $h$.

This identifies the spacecollection of viewports into the three-dimensional halfspace $(x,y,h)\in \Real^3, h>0$. We will call this collection the viewport space $\vp:=\{(x,y,h), x,y\in\Real, h\in\Real_{> 0}\}$.

For now this is just a collection of points.

The structure we need is that of a metric space: we need to equip $V$ with a metric, i.e., a distance function $d$.

As the tools of navigating the viewport space are zooming in and out, and scrolling in all directions, let's define this distance function somewhat loosely, as how many finger movements you need to get from one viewport to another.

There is no canonical way to define this function: one could use the total muscle energy, ionic flux needed to steer these muscles, or cortical oxygen expenditure,

But one way or another, one gets a distance function \[ (v_1, v_2)\mapsto d_f(v_1,v_2), \] which we call the finger distance between the viewports $v_2=(x_1,y_1,h_1)$ and $v_2=(x_2,y_2, h_2)$.

The following should be evident:

These two observations show that, while the finger metric is nearly impossible to quantify experimentally, it possesses, from the first principles, a significant group of symmetries; in fact, these symmetries act transitively on the viewport space $\vp$.

One more property of the finger metric is important: the distance is realized by the steps of bounded size. One scrolls, or one zooms in or out, but each of these movements changes the viewport in a limited way.

The navigation between viewports that are far apart is done by those small steps.

In geometry, one often uses the concept of length space, where the distance between any pair of points can be obtained by finding the shortest path between two points (a broad class of examples: Riemannian manifolds)

In our finger metric, we cannot really hope to have a length space, but the palliative of short steps is good enough.

Let's introduce the mathematical conuerpart of the viewport space with the finger metric: the $3$-dimensional hyperbolic space, - its halfspace model.

Recall that the half-space model of the $3$-dimensional hyperbolic space is the open half-space $\vp$ (i.e., as a collection of points it is the same as the viewport space).

What we need to make it into a metric space is a distance function. It is a path space with the distance which we will characterize by its properties.

Properties of the hyperbolic mertic:

One can immediately derive from these invariance properties, that the Riemannian metric on the half-space model of the hyperbolic space is given (after, perhaps, some rescaling of the vertical coordinate) by \[ \frac{\sqrt{dx^2+dy^2+dh^2}}{h}. \]

Besides horizontal translations and dilatations, the hyperbolic space possesses one more type of symmetries, the inversions, the mappings like \[ (x,y,h)\mapsto \frac{(x,y,h)}{x^2+y^2+h^2}, \] an involution preserving point-wise the unit (hemi-)sphere, and set-wise, the rays through the origin.

A geodesic line is a trajectory such that the length of any short enough subinterval equals the distance between the endpoints of the interval (one can equivalently says that about a geodesic trajectory defines a local isometry).

It is clear that any two points in $\vp$ sitting one above the other, - and above the same point on the ideal boundary (i.e., the horizontal plane $\{h=0\}$), - the unique geodesic connecting them is the vertical segment.

The uniqueness of this geodesic segment also implies that this vertical straight segment is the shortest line connecting two points in $\vp$ one above the other.

Inversions take vertical straight lines to semi-circles in vertical planes with the center on $\{h=0\}$. Hence, for any pair of points in $\vp$ with heights relatively small compared to the Euclidean distance between their projections to the ideal plane, the geodesic trajectory connecting them first shoots up, and then descends back, traversing almost half a circle, like a ballistic missile.

This geodesic looks curved only to us, using the Euclidean space to describe hyperbolic geometry; for the native dwellers of $\vp$, these half-circles are perfectly straight. On the other hand, for them what we consider a straight line at the constant height $h$ would be curving up...

It seems quite clear that the finger metric and the hyperbolic metric should be strongly related: they are defined on the same set, $\vp$ and share quite a few symmetries: the shifts and the dilatations.

This relationship turns out to be a quasiisometry.

Quasiisometries are not quite isometries, but are not too far away from them. Here's the formal

Definition
One says that $f:X\to Y$ is quasiisometry if for some $C>0, L>1$ \[ \frac{1}{L}d_X(x,x')-C\leq d_Y(f(x), f(x'))\leq L d_X(x,x')+C. \]

Proposition

These space $\vp$ with the finger metric and hyperbolic metric are naturally quasi-isometric.

Indeed, the unit ball in the finger metric centered at any point is squeezed between two balls in the standard hyperbolic metric of radii $L$ and $1/L$, for some $L$. Existence of a transformation preserving both metrics and taking that point to any other point makes it true uniformly. Hence, with potential correction for the first and last step, the lengths of the paths realizing either metric is bounded from above and below by the inequalities \[ \frac{1}{L}d_X(x,x')-C\leq d_Y(f(x), f(x'))\leq L d_X(x,x')+C. \]

The notion of quasiisometric spaces is meaningful only at the large scale, where the additive constant $C$ becomes irrelevant.

One might wonder if the presence of that multiplicaive slack factor $L>1$ gives too much freedom to distort the geodesic (or quasi-geodesic) paths.

For example, for Euclidean spaces, in two quasiisometric metric structures on the same space, long geodesics between same endpoints can be very far away from each other.

An amazing fact is that for hyperbolic spaces, and spaces quasiisometric to hyperbolic ones, this does not happen.

One immediate corollary of the definition is that any path realizing the finger distance between a couple of points is necessarily a $C$-quasi-geodesic in the hyperbolic metric.
It means that the finger distance between any pair of points along the path is bounded by $C$ times the hyperbolic distance between the points: one can just take the hyperbolic geodesic connecting these points and split it into the small steps of the finger metric.

However, apriori, there could be a shorter path which is very far away from the hyperbolic geodesic...

One of the most salient properties of the quasi-geodesic paths in hyperbolic space is that they sheepishly follow the actual hyperbolic geodesic lines.

This remarkable fact is known as the Morse lemma and is at the foundation of the beautiful theory of Gromov hyperbolic spaces.

Recall that a path metric space is called Gromov hyperbolic if its triangles are thin: for some fixed parameter $\delta$, for any three points $A, B$ and $C$, the geodesic connecting $A$ and $B$ is withinthe union of $\delta$-neighborhoods of the geodesics connecting $A$ and $C$ and $C$ and $B$.

A Euclidean space is obviously not Gromov hyperbolic. But our $3$-dimensional hyperbolic space is!

Morse Lemma

In a $\delta$-hyperbolic space, the Hausdorff distance between a quasi-geodesic (with additive and multiplicative slacks $C$ and $L$) and a geodesic segment sharing the same endpoints is bounded by a constant depending only on $C$, $L$ and $\delta$ and not on the length of the geodesic.

Morse lemma tells us that the optimal path in the finger metric is always be at a bounded distance from the optimal trajectory in the hyperbolic metric on the viewport space which we know precisely.

So, while an exact computation of finger distance or finger geodesic paths between a pair of viewports is a meaningless, we know that an optimal navigation path zooms out and then in, just like the geodesic path of the $3$-hyperbolic space.

THE END