Given $p/q, r/s \in \mathbb{Q}$, where $\gcd(p,q)=\gcd(r,s)=1$, choose the triangles in the Farey tessellation whose interior intersects the geodesic connecting $p/q$ and $r/s$ in $\mathbb{H}^2$:

alt text http://dl.dropbox.com/u/8592391/tree2.jpg

If $ps-qr=1$, then $d(p/q,r/s)=1$ and there is a geodesic of the Farey tessellation connecting the two points. Otherwise, there will be a non-trivial triangle intersecting the geodesic. The triangles may be grouped together into maximal collections of triangles sharing a common vertex (a "pivot"). Let $p_i$ be the number of triangles in the $i$th group. Associated to this sequence of grouped triangles is a canonical sequence $[p_1,p_2, \ldots, p_k]$, where $p_1>1, p_k>1$. Define $l([p_1,p_2,\ldots,p_k])=d(p/q,r/s)$.

alt text http://dl.dropbox.com/u/8592391/pivotseq2.jpg

Note that the sequence of triangles $[1,p_2, \ldots, p_k]$ is the same as the sequence $[1+p_2, \ldots, p_k]$, since the lone triangle shares a vertex with the pivot of the adjacent group, which is why we may assume that $p_1>1$, and similarly $p_k>1$.

The formula for the the Farey distance is computed inductively by $l([p_1,p_2,\ldots,p_k]) = 1+ l([p_2,\ldots,p_k])$, and for $k=1$, $l([p_1])= 2$ (we are assuming that $p_1>1$ when $k=1$, since otherwise $d(p/q,r/s)=1$). Here, if $p_2=1$, then $l([p_2,\ldots,p_k])=l([1+p_3,\ldots,p_k])$. To prove this formula, one can see that a shortest path from $p/q$ to $r/s$ must go through the adjacent pivot to $p/q$. If not, a case-by-case analysis shows that one can find a shorter path, unless $p_1=2$ and the path goes through the lower two edges of the first group of triangles. But then one can take an equal length path going through the first pivot.

To relate this to the continued fraction expansion, use an element of $A\in PGL_2(\mathbb{Z})$ such that $A(p/q)=\infty$, and $0\leq A(r/s) \leq 1/2$. Then $d(p/q,r/s)=d(A(p/q),A(r/s))=d(\infty,A(r/s))$. To compute the triangle sequence in this case, we may use the continued fraction expansion for $A(r/s)$ to get $[p_1,\ldots,p_k]$ via $A(r/s)=1/(p_1+1/(p_2+1/(\cdots +1/p_k)\cdots )))$:

alt text http://dl.dropbox.com/u/8592391/convex.jpg

In this example, $p/q=\infty=1/0$, $r/s=2/5$, and the continued fraction is $[2,2]$, since $2/5=1/(2+1/2)$.

Given $p/q, r/s \in \mathbb{Q}$, where $\gcd(p,q)=\gcd(r,s)=1$, choose the triangles in the Farey tessellation whose interior intersects the geodesic connecting $p/q$ and $r/s$ in $\mathbb{H}^2$:

If $ps-qr=1$, then $d(p/q,r/s)=1$ and there is a geodesic of the Farey tessellation connecting the two points. Otherwise, there will be a non-trivial triangle intersecting the geodesic. The triangles may be grouped together into maximal collections of triangles sharing a common vertex (a "pivot"). Let $p_i$ be the number of triangles in the $i$th group. Associated to this sequence of grouped triangles is a canonical sequence $[p_1,p_2, \ldots, p_k]$, where $p_1>1, p_k>1$. Define $l([p_1,p_2,\ldots,p_k])=d(p/q,r/s)$.

Note that the sequence of triangles $[1,p_2, \ldots, p_k]$ is the same as the sequence $[1+p_2, \ldots, p_k]$, since the lone triangle shares a vertex with the pivot of the adjacent group, which is why we may assume that $p_1>1$, and similarly $p_k>1$.

The formula for the the Farey distance is computed inductively by $l([p_1,p_2,\ldots,p_k]) = 1+ l([p_2,\ldots,p_k])$, and for $k=1$, $l([p_1])= 2$ (we are assuming that $p_1>1$ when $k=1$, since otherwise $d(p/q,r/s)=1$). Here, if $p_2=1$, then $l([p_2,\ldots,p_k])=l([1+p_3,\ldots,p_k])$. To prove this formula, one can see that a shortest path from $p/q$ to $r/s$ must go through the adjacent pivot to $p/q$. If not, a case-by-case analysis shows that one can find a shorter path, unless $p_1=2$ and the path goes through the lower two edges of the first group of triangles. But then one can take an equal length path going through the first pivot.

To relate this to the continued fraction expansion, use an element of $A\in PGL_2(\mathbb{Z})$ such that $A(p/q)=\infty$, and $0\leq A(r/s) \leq 1/2$. Then $d(p/q,r/s)=d(A(p/q),A(r/s))=d(\infty,A(r/s))$. To compute the triangle sequence in this case, we may use the continued fraction expansion for $A(r/s)$ to get $[p_1,\ldots,p_k]$ via $A(r/s)=1/(p_1+1/(p_2+1/(\cdots +1/p_k)\cdots )))$:

In this example, $p/q=\infty=1/0$, $r/s=2/5$, and the continued fraction is $[2,2]$, since $2/5=1/(2+1/2)$.

Given $p/q, r/s \in \mathbb{Q}$, where $\gcd(p,q)=\gcd(r,s)=1$, choose the triangles in the Farey tessellation whose interior intersects the geodesic connecting $p/q$ and $r/s$ in $\mathbb{H}^2$.

alt text http://math.berkeley.edu/%7Eianagol/tree2.pdf

If $ps-qr=1$, then $d(p/q,r/s)=1$ and there is a geodesic of the Farey tessellation connecting the two points. Otherwise, there will be a non-trivial triangle intersecting the geodesic. Associated to this sequence of triangles is a canonical sequence $[p_1,p_2, \ldots, p_k]$, where $p_1>1, p_k>1$. Define $l([p_1,p_2,\ldots,p_k])=d(p/q,r/s)$.

alt text http://dl.dropbox.com/u/8592391/pivotseq2.pdf

Note that the sequence of triangles $[1,p_2, \ldots, p_k]$ is the same as the sequence $[1+p_2, \ldots, p_k]$, since the lone triangle may be absorbed into the next sequence, which is why we may assume that $p_1>1$, and similarly $p_k>1$.

The formula for the the Farey distance is computed inductively by $l([p_1,p_2,\ldots,p_k]) = 1+ l([p_2,\ldots,p_k])$, and for $k=1$, $l(p_1)= 2$ (we are assuming that $p_1>1$, since otherwise $d(p/q,r/s)=1$). Here, if $p_2=1$, then $l([p_2,\ldots,p_k])=l([1+p_3,\ldots,p_k])$. To prove this formula, notice that in the diagram there is a sequence of $k+1$ "pivots", starting with $p/q$ and ending with $r/s$. One can see that a shortest path from $p/q$ to $r/s$ must go through the adjacent pivot. If not, a case-by-case analysis shows that one can find a shorter path, unless $p_1=2$ and the path goes through the lower two edges. But then one can take an equal length path going through the pivot.

To relate this to the continued fraction expansion, use an element of $A\in PGL_2(\mathbb{Z})$ such that $A(p/q)=\infty$, and $0\leq A(r/s) \leq 1/2$. Then $d(p/q,r/s)=d(A(p/q),A(r/s))=d(\infty,A(r/s))$. To compute the triangle sequence in this case, we may use the continued fraction expansion for $A(r/s)$ to get $[p_1,\ldots,p_k]$ via $A(r/s)=1/(p_1+1/(p_2+\cdots +1/p_k)\cdots )$:

convex http://math.berkeley.edu/%7Eianagol/convex.pdf

In this example, $p/q=\infty=1/0$, $r/s=2/5$, and the continued fraction is $[2,2]$, since $2/5=1/(2+1/2)$.

Given $p/q, r/s \in \mathbb{Q}$, where $\gcd(p,q)=\gcd(r,s)=1$, choose the triangles in the Farey tessellation whose interior intersects the geodesic connecting $p/q$ and $r/s$ in $\mathbb{H}^2$:

alt text http://dl.dropbox.com/u/8592391/tree2.jpg

If $ps-qr=1$, then $d(p/q,r/s)=1$ and there is a geodesic of the Farey tessellation connecting the two points. Otherwise, there will be a non-trivial triangle intersecting the geodesic. The triangles may be grouped together into maximal collections of triangles sharing a common vertex (a "pivot"). Let $p_i$ be the number of triangles in the $i$th group. Associated to this sequence of grouped triangles is a canonical sequence $[p_1,p_2, \ldots, p_k]$, where $p_1>1, p_k>1$. Define $l([p_1,p_2,\ldots,p_k])=d(p/q,r/s)$.

alt text http://dl.dropbox.com/u/8592391/pivotseq2.jpg

Note that the sequence of triangles $[1,p_2, \ldots, p_k]$ is the same as the sequence $[1+p_2, \ldots, p_k]$, since the lone triangle shares a vertex with the pivot of the adjacent group, which is why we may assume that $p_1>1$, and similarly $p_k>1$.

The formula for the the Farey distance is computed inductively by $l([p_1,p_2,\ldots,p_k]) = 1+ l([p_2,\ldots,p_k])$, and for $k=1$, $l([p_1])= 2$ (we are assuming that $p_1>1$ when $k=1$, since otherwise $d(p/q,r/s)=1$). Here, if $p_2=1$, then $l([p_2,\ldots,p_k])=l([1+p_3,\ldots,p_k])$. To prove this formula, one can see that a shortest path from $p/q$ to $r/s$ must go through the adjacent pivot to $p/q$. If not, a case-by-case analysis shows that one can find a shorter path, unless $p_1=2$ and the path goes through the lower two edges of the first group of triangles. But then one can take an equal length path going through the first pivot.

To relate this to the continued fraction expansion, use an element of $A\in PGL_2(\mathbb{Z})$ such that $A(p/q)=\infty$, and $0\leq A(r/s) \leq 1/2$. Then $d(p/q,r/s)=d(A(p/q),A(r/s))=d(\infty,A(r/s))$. To compute the triangle sequence in this case, we may use the continued fraction expansion for $A(r/s)$ to get $[p_1,\ldots,p_k]$ via $A(r/s)=1/(p_1+1/(p_2+1/(\cdots +1/p_k)\cdots )))$:

alt text http://dl.dropbox.com/u/8592391/convex.jpg

In this example, $p/q=\infty=1/0$, $r/s=2/5$, and the continued fraction is $[2,2]$, since $2/5=1/(2+1/2)$.