# Cops and Robber on Hyperbolic Manifolds

Vesna Iršič  University of Ljubljana<EMAIL_ADDRESS>,  Bojan Mohar
Simon Fraser University<EMAIL_ADDRESS>and  Alexandra Wesolek  Technische
Universität Berlin<EMAIL_ADDRESS>
###### Abstract.

The Cops and Robber game on geodesic spaces is a pursuit-evasion game with
discrete steps which captures the behavior of the game played on graphs, as
well as that of continuous pursuit-evasion games. One of the outstanding open
problems about the game on graphs is to determine which graphs embeddable in a
surface of genus $g$ have largest cop number. It is known that the cop number
of genus $g$ graphs is $O(g)$ and that there are examples whose cop number is
$\tilde{\Omega}(\sqrt{g}\,)$. The same phenomenon occurs when the game is
played on geodesic surfaces.

In this paper we obtain a surprising result about the game on a surface with
constant curvature. It is shown that two cops have a strategy to come
arbitrarily close to the robber, independently of the genus. We also discuss
upper bounds on the number of cops needed to catch the robber.

Our results generalize to higher-dimensional hyperbolic manifolds.

###### Key words and phrases:

game of cops and robber; hyperbolic plane; covering space method

###### 2020 Mathematics Subject Classification:

91A05, 91A50, 32Q45

V.I. was supported by the Slovenian Research and Innovation Agency (ARIS)
under the grant Z1-50003, and by the European Union (ERC, KARST, 101071836).

B.M. was supported in part by an NSERC Discovery Grant R611450 (Canada), by
the ERC Synergy grant (European Union, ERC, KARST, project number 101071836),
and by the Research Project N1-0218 of ARIS (Slovenia). On leave from: FMF,
Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.

A.W. was supported by the Vanier Canada Scholarship program and by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under
Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+
(EXC-2046/1, project ID: 390685689).

##  1\. Introduction

The Cops and Robber game is a pursuit-evasion game. The game is commonly
played on graphs [2, 4, 6, 7, 9, 12, 18, 22], and as a new variant on geodesic
spaces [17, 25, 26]. The players in the Cops and Robber game are the robber
$r$ and $k$ cops $c_{1},\dots,c_{k}$. On graphs the players occupy vertices
while on geodesic spaces the players occupy points in space. The game is
played in rounds. The robber chooses initial positions for the players
$r^{0},c_{1}^{0},\dots,c_{k}^{0}$ and in each round of the game the players
can move to a new position111The rules of the Cops and Robber game on graphs
we define here are slightly different to standard rules, but they do not
affect the outcome of the game on connected graphs.. Each round of the game
has two turns, the first one for the robber and the second one for the cops.
In particular, each of the cops can make a step at the cops’ turn. When the
game is played on a graph, the players are allowed to move to an adjacent
vertex at their turn. When the game is played on a geodesic space $X$, the
robber chooses an agility function $\tau:\mathbb{N}\to\mathbb{R_{+}}$ at the
beginning of the game such that $\sum_{n\geq 1}\tau(n)=\infty$. In the $n$-th
round, each player makes a step of length at most $\tau(n)$ (at their turn).
The position of a player $x$ after round $n$ is denoted as $x^{n}$. In the
following we give the robber the pronoun he, him, while the cops have the
pronoun she, her. We say the cops _catch_ the robber if at some point in the
game the cop $c_{i}$ occupies the same position as the robber $r$. If the
robber is not caught, we say the robber _escapes_.

The _cop number $c(G)$_ of a graph $G$ is the minimum number of cops that can
catch the robber (regardless of the robber’s strategy and initial positions).
For a geodesic space $X$ we denote by $c_{0}(X)$ the _cop catch number_ ,
which is the minimum number of cops that can catch the robber. Further, if the
game is played on a geodesic space, we say that the _cops win the game_ if

(1.1) $\displaystyle\inf_{n,i}d(c_{i}^{n},r^{n})=0.$

The minimum number of cops that win the game on a geodesic space $X$ is the
_cop win number_ $c(X)$ of $X$. Note that in [25, 26, 17] the cop win number
is referred as the cop number, and the cop catch number is called the strong
cop number. Informally speaking, the cop win number is the minimum number of
cops needed to capture the robber when the players are represented by
infinitesimally small disks in the metric space.

The Cops and Robber game on geodesic spaces is tightly related to continuous
and discrete pursuit-evasion games on metric spaces. In continuous pursuit-
evasion games the players make decisions at every point in the time interval
$[0,\infty)$. For example, the Lion and Man game as introduced by Rado (see
Littlewood’s Miscellany [20]) is a two-player game where each player is
represented by a point in a metric space, and they can both move with the same
maximal speed in any direction. More precisely, the players’ paths are
1-Lipschitz maps and a strategy of a player consists of choosing a path $f(g)$
for each of the possible opponents paths $g$ such that if $g$ and $g^{\prime}$
agree on a time interval $[0,t]$, then $f(g)$ and $f(g^{\prime})$ agree on
$[0,t]$. The man is trying to evade the capture by the lion, while the lion is
aiming to occupy the same point as the man. Besicovitch showed that the man
can escape the lion when the game is played on a disk [20]. Croft studied a
variation of this game with multiple pursuers on higher dimensional balls [10]
and Satimov and Kushkarov studied the game on the sphere [27]. However,
Bollobás, Leader and Walters [5] showed that in some geodesic spaces, the lion
and man game is not well-defined, in the sense that both the lion and the man
have a winning strategy.

The Discrete Lion and Man game is the Cops and Robber game where the agility
function is constant, i.e. $\tau\equiv K$ for some constant $K$. It was shown
that in the Discrete Lion and Man game the lion can catch the man on a disk,
more generally, the lion can catch the man on any compact
$\operatorname{cat}(0)$-space [3, 31]. While the Cops and Robber game is a
discrete pursuit-evasion game, it captures the properties of the continuous
game, in the sense that in the Cops and Robber game one cop cannot catch the
robber when the game is played on a disk [17]. Further, the Cops and Robber
game is well defined, as Mohar showed that either the cops or the robber have
a winning strategy [25].

One of the first results about cop numbers given by Aigner and Fromme states
that planar graphs have cop number at most $3$ [2].

######  Theorem 1.1 ([2]).

The cop number of every planar graph is at most three.

An important tool for determining upper bounds for cop numbers is the
Isometric Path Lemma, which we use to prove our main theorem and to show that
the cop catch number for special surfaces of genus $g\geq 2$ is at most $6$
(see Theorem 4.5).

######  Lemma 1.2 ([2, 26]).

Let $I$ be an isometric path starting at $A$ and ending at $B$. Then one cop
$c$ can guard $I$ after spending time equal to the length of $I$ on the path
to adjust himself.

The idea of the lemma is that the cop $c$ stays at the same distance to $A$ as
the robber, unless the robber is too far away, in which case $c$ waits at $B$.

For graphs embeddable in a surface of genus $g$ it is known that the cop
number is at most linear in $g$ and recent progress was made on improving the
linear factor, see [8, 11, 28]. It is an outstanding open problem to determine
which graphs embeddable in a surface of genus $g$ have largest cop number.
There are graphs of genus $g$ with cop number at least $g^{\frac{1}{2}-o(1)}$;
one such example are binomial random graphs ${\mathcal{G}}(n,p)$ with
$p=\frac{2\log n}{n}$ [4, 24]. The gap between the upper and lower bound is
large and it is conjectured that the lower bound gives the right order of the
cop number.

######  Conjecture 1.3 ([24, 26]).

Let $S$ be a a graph of genus $g$. Then $c(S)=O(\sqrt{g})$.

Conjecture 1.3 resembles the famous Meyniel’s conjecture.

######  Conjecture 1.4 ([12]).

Let $G$ be a a graph of order $n$. Then $c(G)=O(\sqrt{n})$.

This is a long-standing conjecture and the best upper bound is that the cop
number of an $n$-vertex graph is at most
$O\left(\frac{n}{2^{(1-o(1))\sqrt{\log^{2}(n)}}}\right)$, see [13, 21, 29].
Hence even a weaker version of the conjecture, called the Weak Meyniel’s
conjecture, which states that there exists some $\varepsilon>0$ such that
$c(G)\leq O(n^{1-\varepsilon})$, is still open. Conjecture 1.3 for graphs of
genus $g$ implies that Meyniel’s conjecture holds for graphs with $O(n)$ edges
as their genus is $O(n)$, which includes for example subcubic graphs.
Hosseini, Mohar and Gonzalez Hermosillo de la Maza [16] showed that Meyniel’s
conjecture for subcubic graphs implies the Weak Meyniel’s conjecture (with
exponent $\frac{3}{4}$), thus Conjecture 1.3 implies the Weak Meyniel’s
conjecture.

As for graphs, the cop win number for a surface of genus $g$ is at most linear
in $g$ [25]. It was shown that for graphs of cop number at least $3$ there
exists a surface $S$ of genus $g$ with $c(S)\geq c(G)$ [25]. Therefore there
are compact surfaces of genus $g$ with cop win number at least
$g^{\frac{1}{2}-o(1)}$. The following conjecture is a tough conjecture since
it implies Conjecture 1.3.

######  Conjecture 1.5 ([26]).

Let $S$ be a geodesic surface of genus $g$. Then $c(S)=O(\sqrt{g})$.

The main result of this paper shows that the upper bound from Conjecture 1.5
can be significantly improved for surfaces of constant curvature. The bound is
independent of the genus, which we find surprising. Surfaces of constant
curvature are either spherical, Euclidean or hyperbolic. It follows from [17]
that spherical and Euclidean surfaces, which are surfaces of genus $0$ and
$1$, have cop win number $2$ and cop catch number $3$. Here we settle the case
of hyperbolic surfaces which can have arbitrarily large genus, and extend it
to higher-dimensional hyperbolic manifolds. The main result of the paper thus
reads as follows.

######  Theorem 1.6.

If $M$ is a compact hyperbolic manifold, then $c(M)=2$.

Definitions and technical lemmas needed in the proofs are presented in Section
2. The proof of the 2-dimensional version of Theorem 1.6 is given in Section
3. In the proof we describe a novel strategy based on the covering space
technique. One cop follows the robber while the other one assures that the
robber needs to diverge from its route, enabling the first cop to take
shortcuts. The higher-dimensional version of Theorem 1.6 is presented in
Section 5. Finally, the cop catch number is discussed in Section 4.

##  2\. Preliminaries

In this section we present definitions and preliminary lemmas that we need to
prove our results. We start with basic definitions which are needed for the
Cops and Robber game.

Let $(X,d)$ be a metric space. For $x,y\in X$, an _$(x,y)$ -path_ is a
continuous map $\gamma:I\to X$ where $I=[0,1]$ is the unit interval on
$\mathbb{R}$, $\gamma(0)=x$ and $\gamma(1)=y$. One can define the _length_
$\ell(\gamma)$ of the path $\gamma$ by taking the supremum over all finite
sequences $0=t_{0}<t_{1}<t_{2}<\cdots<t_{n}=1$ of the values
$\sum_{i=1}^{n}d(\gamma(t_{i-1}),\gamma(t_{i}))$. Clearly, the length of every
$(x,y)$-path is at least $d(x,y)$. The metric space $X$ is a _geodesic space_
if for every $x,y\in X$ there is an $(x,y)$-path whose length is equal to
$d(x,y)$. An $(x,y)$-path $\gamma$ is _isometric_ if $\ell(\gamma)=d(x,y)$.
Observe that for $0\leq t<t^{\prime}\leq 1$ the subpath
$\gamma|_{[t,t^{\prime}]}$ is also isometric. Therefore the set
$\gamma(I)=\\{\gamma(t)\mid t\in I\\}$ is an isometric subset of $X$. With a
slight abuse of terminology, we say that the image $\gamma(I)\subset X$ is an
_isometric path_ in $X$. If there exists a unique isometric path between $x,y$
then we will denote it by $\overline{xy}\subset X$. A continuous map
$\gamma:\mathbb{R}\to X$ is a _geodesic_ if it is locally isometric, i.e., for
every $t\in\mathbb{R}$ there is an $\varepsilon>0$ such that the subpath
$\gamma|_{J}$ on the interval $J=[t-\varepsilon,t+\varepsilon]$ is isometric.

###  2.1. Hyperbolic plane and hyperbolic surfaces

Since we consider the Cops and Robber game played on hyperbolic spaces, we
properly define those and give examples for particular hyperbolic surfaces.

The $n$-dimensional hyperbolic space $\mathbb{H}^{n}$ is the unique
$n$-dimensional simply connected complete Riemannian manifold with a constant
negative sectional curvature equal to $-1$. Standard examples for hyperbolic
space is the half space model and the Poincaré disk model. The $n$-dimensional
_Poincaré disk_ $\mathcal{D}^{n}$ is the disk $\\{(x_{1},\ldots,x_{n})\mid
x_{1}^{2}+\cdots+x_{n}^{2}<1\\}$ equipped with the hyperbolic metric
$4\frac{dx_{1}^{2}+\cdots+dx_{n}^{2}}{(1-x_{1}^{2}-\cdots-x_{n}^{2})}$. For
brevity, we write $\mathcal{D}=\mathcal{D}^{2}$.

Well-known examples for surfaces which are not hyperbolic are the sphere and
the flat torus. The flat torus arises from a tessellation of the Euclidean
plane by translations of a parallelogram. Here, the Euclidean plane is the
universal covering space of the standard torus. For a topological space $X$, a
_covering space_ of $X$ is a topological space $C$ together with a continuous
surjective map $p\colon C\to X$ such that for every $x\in X$, there exists an
open neighbourhood $U$ of $x$, such that $p^{-1}(U)$ is a union of disjoint
open sets in $C$, each of which is mapped homeomorphically onto $U$ by $p$
(i.e. it is a local homeomorphism).

Similarly as for the flat torus, hyperbolic surfaces arise from a tessellation
of the hyperbolic plane into copies of some polygon (see Figure 1), which is
formalized by the following theorem.

######  Theorem 2.1 (Killing-Hopf [15, 19]).

Any compact Riemannian manifold of constant curvature $-1$ is isometric to
$\mathbb{H}^{n}/\Gamma$ where $\Gamma$ is a group of isometries on
$\mathbb{H}^{n}$ acting freely and properly discontinuously.

Here, the curvature is the sectional curvature. For more information about
curvatures, we refer the reader to [1].

A _fundamental polygon_ of a Riemannian surface $\mathbb{H}^{2}/\Gamma$ is a
polygon in $\mathbb{H}^{2}$ which contains a representative of each
$\Gamma$-orbit and at most one representative of each $\Gamma$-orbit in its
interior. We define by _$P(k,\theta)$_ the regular $k$-gon in the Poincaré
disk $\mathcal{D}$ centred at $O=(0,0)$ with angle $\theta$ at the vertices.
We denote its vertices by $v_{1},\dots,v_{k}$ in counter-clockwise direction
and let $a_{i}$ be the (oriented) edge from $v_{i}$ to $v_{i+1}$ and
$a_{i}^{-1}$ be the reversed edge from $v_{i+1}$ to $v_{i}$ (we consider the
indices modulo $k$). We are going to consider three standard hyperbolic
surfaces for $g\geq 2$, where one of them is non-orientable.

  * •

Let $S(g)$ be the orientable surface obtained from
$P\left(4g,\frac{2\pi}{4g}\right)$ by identifying the (oriented) edges
$a_{4i-3}$ with $a_{4i-1}^{-1}$ and $a_{4i-2}$ with $a_{4i}^{-1}$ for
$i=1,\dots,g$. The surface $S(2)$ is depicted in Figure 1.

  * •

Let $S^{\prime}(g)$ be the orientable surface obtained from
$P\left(4g+2,\frac{2\pi}{2g+1}\right)$ by identifying opposite (oriented)
edges $a_{i},a_{i+2g+1}^{-1}$ for $i=1,\dots,2g$.

  * •

Let $N(g)$ be the non-orientable surface obtained from
$P\left(2g,\frac{2\pi}{2g}\right)$ by identifying the (oriented) edge $a_{2i}$
with $a_{2i+1}$ for $i=1,\dots g$.

$a_{1}$$a_{2}$$a_{5}$$a_{6}$$(a)$
$a_{1}$$a_{1}^{-1}$$a_{2}$$a_{2}^{-1}$$a_{5}$$a_{5}^{-1}$$a_{6}$$a_{6}^{-1}$$v_{1}$$v_{3}$$v_{2}$$v_{4}$$v_{8}$$v_{6}$$v_{7}$$v_{5}$$(b)$

Figure 1. Figure (a) depicts the surface $S(g)$ and Figure (b) its fundamental
domain $P\left(4g,\frac{2\pi}{4g}\right)$ inside a partial tessellation of the
Poincaré disk.

The _diameter_ of a compact surface $S$ is the maximum distance between points
in $S$, that is $\operatorname{diam}(S)=\max\\{d(x,y)\mid x,y\in S\\}$. The
_systolic girth_ , denoted as $\operatorname{sys}(S)$, is the length of a
shortest noncontractible curve on the surface. A hyperbolic surface is locally
isometric to the hyperbolic plane, which we will use frequently in our proofs.

######  Lemma 2.2.

If $S$ is a hyperbolic surface, $a\in S$ and
$r<\frac{\operatorname{sys}(S)}{4}$, then the disk $B(a,r)$ is isometric to a
hyperbolic disk.

###  2.2. Trigonometric lemmas for the hyperbolic plane

In the rest of this section, we present lemmas that will be used in the proof
of Theorem 3.1. Their proofs are omitted and are given in Appendix A. For
properties of the hyperbolic plane needed in the proofs of these lemmas we
refer the reader to [23, 30].

First, consider Figure 2 and let the robber’s position be $X_{1}$ and the
cop’s position be $A$. The robber moves to $B$, while the cop moves as close
to $B$ as possible in the same time. Our first lemma shows that if their
starting positions would be closer together (at positions $X_{2}$ and $X_{3}$,
say), then their end positions would be closer together.

######  Lemma 2.3.

Let $ABC$ be a hyperbolic triangle with a right angle at $C$. If
$X_{1}\in\overline{AC}$, then

$\displaystyle
d(A,B)-d(X_{1},B)=\max_{X_{2},X_{3}\in\overline{AX_{1}}}d(X_{2},B)-d(X_{3},B).$

Moreover, $d(A,B)-d(X_{1},B)=d(X_{2},B)-d(X_{3},B)$ if and only if $X_{2}=A$
and $X_{3}=X_{1}$.

$A$$X_{3}$$B$$C$$X_{2}$$X_{1}$ Figure 2. A hyperbolic right-angled triangle
$ABC$ with the right angle at $C$.

The second lemma shows that $d(A,B)-d(X_{3},B)$ would decrease if the length
of the side $\overline{AC}$ would decrease, while $d(A,X_{3})$ would remain
the same.

######  Lemma 2.4.

Let $ABC$ be a hyperbolic triangle with a right angle at $C$. If
$X_{3}\in\overline{AC}$, then

$\displaystyle
d(A,B)-d(X_{3},B)=\max_{\begin{subarray}{c}X_{1},X_{2}\in\overline{AC}\\\
d(X_{1},X_{2})=d(A,X_{3})\end{subarray}}d(X_{2},B)-d(X_{1},B).$

The next lemma helps to compare triangles where two sides have the same
length.

######  Lemma 2.5.

Suppose $ABC$, $A^{\prime}B^{\prime}C^{\prime}$ are hyperbolic triangles,
$d(A,B)=d(A^{\prime},B^{\prime})$, $d(B,C)=d(B^{\prime},C^{\prime})$, $\angle
BCA>\angle B^{\prime}C^{\prime}A^{\prime}$ and $\angle CAB<\frac{\pi}{2}$.
Then it holds that $d(A,C)<d(A^{\prime},C^{\prime})$.

The Pythagorean theorem for the hyperbolic plane for a triangle $ABC$ with
right angle at $C$ says that
$\cosh(\overline{AB})=\cosh(\overline{AC})\cdot\cosh(\overline{BC}).$ In the
following we observe that the increase of $\overline{BC}$ increases
$\overline{AB}$ ”uniformly”.

######  Lemma 2.6.

Suppose $t_{2}>t_{1}>0$ and $w>1$, then there exists $\eta>0$ such that for
$x,y\in[t_{1},t_{2}]$ with $x<y$ it holds that,

$\displaystyle\operatorname{acosh}(w\cosh(x))-\operatorname{acosh}(w\cosh(y))\geq\eta\cdot(y-x).$

##  3\. Hyperbolic surfaces

In this section we prove that two cops can win the game on any compact
hyperbolic surface. In fact, this is the most difficult step towards proving
Theorem 1.6.

######  Theorem 3.1.

If $S$ is a compact hyperbolic surface, then $c(S)=2$.

###  3.1. The lower bound

Let $s=\operatorname{sys}(S)$. To show that $c(S)>1$ we play the game with one
cop $c$ and the robber $r$ and show that the robber has a strategy to stay at
distance at least $\frac{s}{16}$ to the cop. The robber chooses the agility
function $\tau\equiv\frac{s}{16}$ and initial positions such that
$d(c^{0},r^{0})>\frac{s}{16}$. Informally, the robber’s strategy is to move in
the direction opposite to the cop’s position.

If $d(c^{k},r^{k})\geq\frac{3s}{16}$, then the robber’s strategy is to stay at
the same place, which means $r^{k+1}=r^{k}$. Then $d(c^{k+1},r^{k+1})\geq
d(c^{k},r^{k+1})-\frac{s}{16}\geq\frac{s}{8}$. From Lemma 2.2 it follows that
if $d(c^{k},r^{k})<\frac{3s}{16}$, then there exists a position $r^{k+1}$ such
that $d(r^{k},r^{k+1})=\frac{s}{16}$ and an isometric path between $r^{k+1}$
and $c^{k}$ contains $r^{k}$. This means that
$d(c^{k},r^{k+1})=d(c^{k},r^{k})+\frac{s}{8}>\frac{s}{4}$ and hence
$d(c^{k+1},r^{k+1})>\frac{s}{8}$.

###  3.2. The upper bound

Instead of playing the Cops and Robber game on the hyperbolic surface $S$, we
will consider the game on its universal cover, viewed as the Poincaré disk
$\mathcal{D}$. For each time step $k$ we choose a representation
$C_{i}^{k},R^{k}$ of $c_{i}^{k},r^{k}$ in $\mathcal{D}$ ($i=1,2$).

If the robber was only escaping from cop $c_{1}$, then by the above argument
his strategy could be to stay roughly on the geodesic $g$ defined in
$\mathcal{D}$ by the current positions of the robber $r$ and cop $c_{1}$.
Since we have two cops available, we can force the robber to take a different
strategy. The idea of the cops’ strategy is that cop $c_{1}$ will chase the
robber, while cop $c_{2}$ will force the robber to move away from $g$,
allowing cop $c_{1}$ to move closer to $r$.

Let $D=\operatorname{diam}(S)$. The robber chooses an agility function $\tau$
and starting positions, $c_{1}^{0},c_{2}^{0},r^{0}$. Let
$0=t_{0}<t_{1}<t_{2}<t_{3}<\cdots$ be a sequence of integers representing time
steps such that

$\sum_{k=t_{i}}^{t_{i+1}-1}\tau(k)\geq 32D.$

Our goal is to show that for every $\varepsilon>0$ the cops $c_{1},c_{2}$ have
a strategy in which the cop $c_{1}$ can come $\varepsilon$-close to the robber
$r$. This suffices to show that the cop win number is at most $2$ by the
definition of infimum, see [26, Corollary 6]. We will attain our goal by
showing that in between time step $t_{i}$ and $t_{i+1}$, the cop $c_{1}$ can
decrease her distance to the robber by some small constant $\delta$.

######  Lemma 3.2.

For every $\varepsilon>0$, there exists $\delta>0$ and strategies for the cops
$c_{1},c_{2}$, such that if $d(c_{1}^{t_{i}},r^{t_{i}})\geq\varepsilon$ and
the cops follow their strategy then either $c_{2}$ captures the robber, or we
have

$\displaystyle d(c_{1}^{t_{i+1}},r^{t_{i+1}})\leq
d(c_{1}^{t_{i}},r^{t_{i}})-\delta.$

The rest of the section is devoted to the proof of Lemma 3.2. Let
$R^{0},C_{1}^{0}$ be such that $d(R^{0},C_{1}^{0})=d(r^{0},c_{1}^{0})$.

####  3.2.1. The strategy of cop $c_{2}$

We explain the strategy of the cop $c_{2}$ first. Since we play the game in
the covering space $\mathcal{D}$, we have arbitrarily many copies of the
position of $c_{2}$ that we can choose from (see Figure 3). At each time step
$t_{i}$, the cop $c_{2}$ chooses a new representation $C_{2}^{t_{i}}$, and
therefore $d(C_{2}^{t_{i}-1},C_{2}^{t_{i}})$ in $\mathcal{D}$ is possibly
greater than $\tau(t_{i})$ but for the projection onto $S$ we maintain the
condition that $d(c_{2}^{t_{i}-1},c_{2}^{t_{i}})\leq\tau(t_{i})$. In between
the time steps $t_{i},t_{i+1}$ we choose the representation of $c_{2}$ such
that it is coherent with the agility function, which means
$d(C_{2}^{k-1},C_{2}^{k})\leq\tau(k)$ for $t_{i}<k<t_{i+1}$. We consider the
geodesic $g_{0}=g_{0}(t_{i})$ through $R^{t_{i}},C_{1}^{t_{i}}$. We choose
$C_{2}^{t_{i}}$ for cop $c_{2}$ such that it is close to the geodesic $g_{0}$
but sufficiently far from $R^{t_{i}}$, which we make more precise in the
following.

Figure 3. Copies of the fundamental polygon $P(4g,\frac{2\pi}{4g})$ in
$\mathcal{D}$. Depicted is a point and one copy of this point in each of the
depicted copies of the fundamental polygon.

Let $P$ be the point on $g_{0}$ at distance $10D$ from $R^{t_{i}}$ that is
further away from $C_{1}^{t_{i}}$. Note that there is a copy $C_{2}^{t_{i}}$
in the universal covering space which is at distance at most $D$ from $P$,
this will be the starting position of $c_{2}$. We consider
$h=o_{g_{0}}(C_{2}^{t_{i}})$, the orthogonal geodesic to $g_{0}$ through
$C_{2}^{t_{i}}$. The strategy of $c_{2}$ between time steps $t_{i}$ and
$t_{i+1}$ is to chase the orthogonal projection of the robber on $h$. Let
$B,B^{\prime}$ be points on $h$ at distance $8D$ from $g_{0}\cap h$.

######  Lemma 3.3.

The cop $c_{2}$ can guard the path from $B$ to $B^{\prime}$ on $h$.

###### Proof.

First we show that the cop $c_{2}$ can reach $h\cap g_{0}$ much faster than
the robber.

######  Claim 3.4.

The point $h\cap g_{0}$ is at distance between $9D$ and $11D$ from $R^{t_{i}}$
and at distance at most $D$ from $C_{2}^{t_{i}}$.

###### Proof.

Note that the closest point from $C_{2}^{t_{i}}$ to $g_{0}$ is $h\cap g_{0}$
since $h$ and $g_{0}$ are orthogonal. Hence $d(h\cap g_{0},C_{2}^{t_{i}})\leq
d(P,C_{2}^{t_{i}})\leq D$.

The closest point from $P$ to $h$ is also $h\cap g_{0}$ since $P\in g_{0}$. In
particular it holds that $d(h\cap g_{0},P)\leq d(h\cap
g_{0},C_{2}^{t_{i}})\leq D$. The distance from $R^{t_{i}}$ to $P$ is $10D$, so
by the triangle inequality, robber’s distance to $h\cap g_{0}$ is between $9D$
and $11D$. This proves the claim. ∎

Note that by Claim 3.4 the distance from $R^{t_{i}}$ to $h$ is at least $9D$.
The cop $c_{2}$ can guard the path from $B$ to $B^{\prime}$ on $h$, since her
distance to $g_{0}\cap h$ is at most $D$, and hence her distance to any point
on $\overline{BB^{\prime}}$ is at most $9D$, which is less than the distance
from $R^{t_{i}}$ to that point. This means that $c_{2}$ can use the strategy
from the proof of Lemma 1.2 to guard the isometric path
$\overline{BB^{\prime}}$. This completes the proof of Lemma 3.3. ∎

####  3.2.2. The strategy of cop $c_{1}$

For $k\geq t_{i}$, let $g^{k}=o_{h}(C_{1}^{k})$ (the orthogonal geodesic to
$h$ through $C_{1}^{k}$) and let $B^{k}=g^{k}\cap h$, see Figure 4.

$C_{1}^{k}$$B$$B^{k}$$h$$g^{k}$$R^{k}$ Figure 4. A schematic picture of cop’s
position $c_{1}$ and robber’s position $r$ at time step $k$.

We will assign a strategy to cop $c_{1}$ that will force the robber $r$ to
cross the isometric path $\overline{C_{1}^{k}B}$ (or the symmetric case
$\overline{C_{1}^{k}B^{\prime}}$) for some $k$. Note that the robber cannot
cross $\overline{BB^{\prime}}$ since it is guarded by cop $c_{2}$. Since in
round $k$ the robber makes his turn before the cop, the robber crosses
$\overline{C_{1}^{k}B}$ (or $\overline{C_{1}^{k}B^{\prime}}$) in step $k+1$.

In the following the strategy of the cop $c_{1}$ will be such that the best
strategy for the robber $r$ is to cross $\overline{C_{1}^{k}B}$ (or
$\overline{C_{1}^{k}B^{\prime}}$) somewhere close to $B$ (or $B^{\prime}$). We
say two points $X,Y$ _are on opposite sides_ of the geodesic $g$ if $X,Y$ are
in distinct connected components of the Poincaré disk $\mathcal{D}\setminus
g$. If two points $X,Y$ are not on opposite sides, we say they _are on the
same side_.

Suppose $R^{k},R^{k+1}$ are on the same side as $B$ with respect to $g^{k}$.
We denote $x=o_{h}(R^{k+1})\cap\overline{C_{1}^{k}B}$. Then the position
$C_{1}^{k+1}$ can be chosen to be

  * (a)

on $\overline{C_{1}^{k}B}$ with $d(C_{1}^{k+1},C_{1}^{k})=\tau(k+1)$ if
$d(x,C_{1}^{k})\geq\tau(k+1)$, or

  * (b)

on $o_{h}(R^{k+1})$, as close to the point $R^{k+1}$ as possible, otherwise.

This strategy ensures the following condition:

(3.1) The robber’s position $R^{k+1}$ and $B$ are on the same side of
$g^{k+1}$.

######  Observation 3.5.

There is a strategy for the cop $c_{1}$, such that for every time step
$t_{i}\leq k\leq t_{i+1}-1$, while the robber is contained in the triangle
$BB^{k}C_{1}^{k}$ we can assume the robber’s position $R^{k+1}$ is on the same
side of the geodesic $g^{k}$ as $R^{k}$ by subdividing each step at most once.

###### Proof.

By symmetry we can assume that the first step of the robber away from the
geodesic $g_{0}$ is towards $B$. Now, suppose that the robber crosses $g^{k}$
by going from step $R^{k}$ to step $R^{k+1}$, see Figure 5. By splitting each
such step into two substeps we may consider the first substep as above,
initial and ending position on the same side as $B$, and the second substep
with initial and ending position on the same side as $B^{\prime}$. In the
first substep the cop $c_{1}$ moves along $g^{k}$ towards the robber. In the
second substep the cop imagines the robber to move to $\phi(R^{k+1})$, which
is the reflection of the position $R^{k+1}$ along $g^{k}$, and determines his
position $\phi(C_{1}^{k+1})$ by using strategy $(a)$ or $(b)$. She then
reflects the position $\phi(C_{1}^{k+1})$ along $g^{k}$ to obtain
$C_{1}^{k+1}$. After subdividing each of the robber’s steps at most once, by
symmetry we can assume the robber does not cross $g^{k}$, which means the
position $R^{k+1}$ is on the same side of the geodesic $g^{k}$ as $B$.

Figure 5. The point $\phi(R^{k+1})$ is the reflection point of $R^{k+1}$ over
$g^{k}$.

∎

Recall that in round $k$ the robber makes a step before the cops make their
step. We let $t$ be the first round at which the robber crosses
$\overline{C_{1}^{t-1}B}$ (or $\overline{C_{1}^{t-1}B^{\prime}}$). We will
assume without loss of generality that $R^{t}=x\in\overline{C_{1}^{t-1}B}$ (or
$\overline{C_{1}^{t-1}B^{\prime}}$) by subdividing the step and letting the
agility at time step $t$ be $d(x,R^{t-1})$. From step $t$ until step
$t_{i+1}$, the strategy of cop $c_{1}$ is to simply follow the robber, while
the strategy of cop $c_{2}$ is to stay at the same position. In particular,
$R^{t}\in\overline{C_{1}^{t}B}=\overline{C_{1}^{t-1}B}$ (or
$R^{t}\in\overline{C_{1}^{t}B^{\prime}}$).

####  3.2.3. Proof of Lemma 3.2

We start by showing that the robber crosses $\overline{C_{1}^{t}B}$.

######  Lemma 3.6.

If the robber does not get caught by the cops, then
$R^{t}\in\overline{C_{1}^{t}B}$ (or $R^{t}\in\overline{C_{1}^{t}B^{\prime}}$)
for some $t$ with $t_{i}<t<t_{i+1}$. In particular,
$\sum_{k=t_{i}}^{t}\tau(k)<32D$.

###### Proof.

By Observation 3.5 we can assume that at step $k$, the cop $c_{1}$ is moving
closer to $B$ and $h$, and by the triangle inequality on the triangle defined
by $C_{1}^{k-1},C_{1}^{k}$ and $g^{k}\cap\overline{C_{1}^{k-1}B}$, she
decreases the total distance to $B$ and to $h$ by at least $\tau(k)$, i.e.,

$d(C_{1}^{k},B)+d(C_{1}^{k},h)\leq d(C_{1}^{k-1},B)+d(C_{1}^{k-1},h)-\tau(k).$

By Claim 3.4, $d(C_{1}^{t_{i}},g_{0}\cap h)\leq 12D$ and by the triangle
inequality it holds that $d(C_{1}^{t_{i}},B)\leq d(C_{1}^{t_{i}},g_{0}\cap
h)+d(g_{0}\cap h,B)\leq 12D+8D=20D$. Hence the cop either meets $B$ or $h$
after moving for time $32D$, thus catching the robber. ∎

Lemma 3.2 follows directly from the following result.

######  Lemma 3.7.

For each $\varepsilon>0$ there exists some $\delta>0$, such that if
$d(R^{t_{i}},C_{1}^{t_{i}})\geq\varepsilon$, and at step $t$
$(t_{i}<t<t_{i+1})$ $R^{t}\in\overline{C_{1}^{t}B}$, then

$\displaystyle d(R^{t},C_{1}^{t})\leq d(R^{t_{i}},C_{1}^{t_{i}})-\delta.$

The rest of this section is concerned with proving Lemma 3.7. The proof is
technical and uses Lemmas 2.3–2.5.

###### Proof of Lemma 3.7.

Assume that the robber does not get caught by step $t_{i+1}$. Let us consider
the right triangle on vertices $C_{1}^{t-1}$, $B^{t-1}$ and $B$; recall that
$B^{k}=g^{k}\cap h$, see Figure 4. We define a function
$f\colon\overline{C_{1}^{t-1}B}\to\mathbb{R}$ with

$f(x)=d(C_{1}^{t-1},x)-d(R^{t-1},x).$

If $R^{t}=x$, then $d(C_{1}^{t},R^{t})\leq f(x)$. Note that by the triangle
inequality it holds that $f(x)<d(C_{1}^{t-1},R^{t-1})$ since $x$,
$C_{1}^{t-1}$ and $R^{t-1}$ are not on a common geodesic. In order to maximise
his distance to cop $c_{1}$, we show that the best choice for the robber would
be to move to $B$ in his last step (we ignore that the robber would be caught
by $c_{2}$).

######  Claim 3.8.

Given fixed positions $C_{1}^{t-1}$ and $R^{t-1}$ such that $R^{t-1}$ is in
the triangle defined by $C_{1}^{t-1},B,B^{t-1}$, it holds that

$f(B)=\max_{x\in\overline{C_{1}^{t-1}B}}f(x).$

###### Proof.

Suppose $x\in\overline{C_{1}^{t-1}B}$ and $x\neq B$. We consider the triangle
defined by $x,B,R^{t-1}$. Since $x$ is on a common geodesic with $C_{1}^{t-1}$
and $B$,

$\displaystyle f(B)$ $\displaystyle=d(C_{1}^{t-1},B)-d(R^{t-1},B)$
$\displaystyle=(d(C_{1}^{t-1},x)+d(x,B))-(d(R^{t-1},B)-d(R^{t-1},x))-d(R^{t-1},x).$

By the triangle inequality, $d(x,B)\geq d(R^{t-1},B)-d(R^{t-1},x)$, hence
$f(B)$ is at least $f(x)=d(C_{1}^{t-1},x)-d(R^{t-1},x)$. ∎

Let $R^{t_{i}},\dots,R^{t}$ be a sequence of $t-t_{i}$ steps such that
$R^{t}\in\overline{C_{1}^{t-1}B}$ and $R^{k}$ is in the interior of the
triangle $C_{1}^{k-1}BB^{k}$ for $k=t_{i},\dots,t-1$ (given the prescribed
strategy of cop $c_{1}$). We define

$\displaystyle g(t):=\max_{R^{t_{i}},\dots,R^{t},\tau}d(C_{1}^{t},R^{t}).$

Note that the maximum is well-defined since $S$ is compact and we can assume
$\tau(k)\leq D$. Hence let $R^{t_{i}},\dots,R^{t}$ be a sequence such that
$d(C_{1}^{t},R^{t})=g(t)$.

We show that $g(t)\leq g(t-1)$ for every $t\in\\{t_{i},\ldots,t_{i+1}\\}$. If
the last step of $c_{1}$ is of type $(b)$, the robber is caught, and
$0=g(t)\leq g(t-1)$. Thus the following holds.

######  Observation 3.9.

The last step of the cop $c_{1}$ is of type $(a)$.

######  Claim 3.10.

If the second to last step is of type $(a)$, then $g(t)\leq g(t-1)$.

###### Proof.

We can assume $R^{t}=B$ by Claim 3.8. Suppose the second last step from
$C_{1}^{t-2}$ to $C_{1}^{t-1}$ is of type $(a)$. Note that the cop moves
distance exactly $d(R^{t-2},R^{t-1})+d(R^{t-1},B)$ along
$\overline{C_{1}^{t-2}B}$ and for the robber’s steps it holds that
$d(R^{t-2},R^{t-1})+d(R^{t-1},B)\geq d(R^{t-1},B)$. Hence by maximality of
$R^{t_{i}},\dots,R^{t}$, we can assume $R^{t-1}\in\overline{R^{t-2}B}$. But
then $R^{t}_{i},\dots,R^{t-2},R^{t}$ is a sequence with the same value
assuming $\tau^{\prime}(t-1)=\tau(t-1)+\tau(t)$, $\tau^{\prime}(k)=\tau(k)$ if
$k\leq t-2$ and $\tau^{\prime}(k)=\tau(k-1)$ if $k\geq t$. This shows that
$g(t)\leq g(t-1)$.

∎

######  Claim 3.11.

The second to last step is of type $(a)$.

###### Proof.

Now assume the step from $C_{1}^{t-2}$ to $C_{1}^{t-1}$ is of type $(b)$. Let
$z_{c}$ be the intersection point of $g^{t-1}$ and $\overline{C_{1}^{t-2}B}$,
see Figure 6. By Lemma 2.3 we can assume for the step size at time $t-1$ that
$\tau(t-1)=d(R^{t-1},R^{t-2})$, otherwise changing $\tau(t-1)$ to
$\tau^{\prime}(t-1)=\max\\{d(C_{1}^{t-2},z_{c}),d(R^{t-1},R^{t-2})\\}$ gives a
larger value of $g$.

Let $z_{r}^{1},z_{r}^{2}$ be the points on $g^{t-1}$ such that they are at the
same distance from the robber’s position $R^{t-2}$ as $z_{c}$ is from the
cop’s position $C_{1}^{t-2}$. Let $z_{r}^{1}$ be closer to $B^{t-1}$. Note
that $R^{t-1}$ is either in $\overline{z_{r}^{1}B^{t-1}}$ or in
$\overline{z_{r}^{2}z_{c}}$. The second case cannot happen since by Lemma 2.3,
$R^{t-1}=z_{r}^{2}$ would give $C_{1}^{t-1}=z_{c}$ and that would be a better
choice for the robber, contradicting maximality of $R^{t_{i}},\dots,R^{t}$. We
denote $z_{r}=z_{r}^{1}$ and then $R^{t-1}\in\overline{z_{r}B^{t-1}}$, see
Figure 6.

$p_{c}$$B^{t-1}$$C_{1}^{t-2}$$p_{r}$$R^{t-2}$$z_{r}$$B$$z_{c}$$C_{1}^{t-1}$$R^{t-1}$$h$$g^{t-1}$
Figure 6. The case when the second last move of the robber is of type $(b)$.

In the following we argue that it is of advantage to the robber to move to
$z_{r}$ instead of $R^{t-1}$, which also means that the second to last step is
of type $(a)$ as desired.

Let $p_{c},p_{r}$ be the closest points on $g^{t-1}$ from
$C_{1}^{t-2},R^{t-2}$, respectively. This means the angles $\angle
C_{1}^{t-2}p_{c}B^{t-1}$, $\angle R^{t-2}p_{r}B^{t-1}$ are right angles. There
are two Lambert quadrilaterals222A quadrilateral in which three of its angles
are right angles. formed by $C_{1}^{t-2},p_{c},B^{t-1},B^{t-2}$ and
$R^{t-2},p_{r},B^{t-1},o_{h}(R^{t-2})\cap h$, respectively. Any two sides of a
Lambert quadrilateral determine the length of the other sides, see [30]. In
particular, since $d(B^{t-1},o_{h}(R^{t-2})\cap h)\leq d(B^{t-1},B^{t-2})$ and
$d(p_{r},B^{t-1})<d(p_{c},B^{t-1})$, it holds that

$\displaystyle d(p_{r},R^{t-2})<d(p_{c},C_{1}^{t-2}).$

Therefore by the sine formula for hyperbolic right triangles it holds for the
angles that $\angle p_{c}z_{c}C_{1}^{t-2}>\angle p_{r}z_{r}R^{t-2}$ and thus

$\displaystyle\angle C_{1}^{t-2}z_{c}C_{1}^{t-1}<\angle R^{t-2}z_{r}R^{t-1}.$

Since $d(C_{1}^{t-2},z_{c})=d(R^{t-2},z_{r})$ and
$d(C_{1}^{t-2},C_{1}^{t-1})=d(R^{t-2},R^{t-1})$, it holds by Lemma 2.5 that
$d(z_{r},R^{t-1})<d(z_{c},C_{1}^{t-1})$. By Lemmas 2.4 and 2.3 we have

$\displaystyle d(B,z_{c})-d(B,z_{r})>d(B,C_{1}^{t-1})-d(B,R^{t-1}).$

Hence it is of advantage for the robber to move to $z_{r}$ instead of
$R^{t-1}$, a contradiction to the maximality of $R^{t_{i}},\dots,R^{t}$. ∎

We will establish now a positive lower bound on
$d(R^{t_{i}},C_{1}^{t_{i}})-d(R^{t},C_{1}^{t})$. By Claims 3.10 and 3.11, we
can assume that $t=t_{i}+1$. To compute $d(R^{t},C_{1}^{t})$ we only need to
compute the difference between $d(C_{1}^{t_{1}},B)$ and $d(R^{t_{1}},B)$. By
the Pythagorean Theorem for hyperbolic triangles and $H:=g_{0}\cap h$, we have

$\displaystyle d(R^{t},C_{1}^{t})=d(C_{1}^{t_{i}},B)-d(R^{t_{i}},B)$
$\displaystyle=$
$\displaystyle\operatorname{acosh}(\cosh(d(B,H))\cosh(d(C_{1}^{t_{i}},H))-\operatorname{acosh}(\cosh(d(B,H))\cosh(d(R^{t_{i}},H))$
$\displaystyle=$
$\displaystyle\operatorname{acosh}(b\cosh(d(C_{1}^{t_{i}},R^{t_{i}})+d(R^{t_{i}},H))-\operatorname{acosh}(b\cosh(d(R^{t_{i}},H))$

where $b=\cosh(d(B,H))=\cosh(8D)>1$. For $x=d(R^{t_{i}},H)$ and
$y=d(C_{1}^{t_{i}},H)$, and using that
$y-x=d(R^{t_{i}},C_{1}^{t_{i}})\geq\varepsilon$, Lemma 2.6 gives $\eta>0$ such
that

$\displaystyle
d(R^{t},C_{1}^{t})-d(R^{t_{i}},C_{1}^{t_{i}})\geq\eta\varepsilon.$

By taking $\delta=\eta\varepsilon$, we obtain the conclusion of Lemma 3.7. ∎

##  4\. Catching the Robber

We will now turn to the cop catch number. First, we show that on a hyperbolic
surface at least three cops are needed to catch the robber. The upper bound is
considered in Section 4.2.

###  4.1. Lower bound for cop catch number

######  Theorem 4.1.

If $S$ is a hyperbolic surface, then $c_{0}(S)\geq 3$.

###### Proof.

Let $s=\operatorname{sys}(S)$ be the systolic girth of the surface $S$. The
robber chooses the agility function $\tau\equiv\frac{s}{10}$ and starting
positions $r^{0},c_{1}^{0},c_{2}^{0}$ where $r^{0}$ is at distance more than
$\frac{s}{10}$ to $c_{1}^{0},c_{2}^{0}$. In fact, it suffices to assume that
$r^{0}\neq c_{1}^{0},c_{2}^{0}$. We show that if $r^{k}\neq
c_{1}^{k},c_{2}^{k}$ then there exists a position $r^{k+1}$ at distance at
most $\frac{s}{10}$ from $r^{k}$ with $d(r^{k+1},c_{j}^{k})>\frac{s}{10}$
($j=1,2$), and hence the robber can escape from the cops.

If $d(r^{k},c_{j}^{k})>\frac{s}{5}$ for $j=1,2$, then the robber’s strategy is
to stay in the same place, and $d(r^{k+1},c_{j}^{k})>\frac{s}{5}$. If
$d(r^{k},c_{1}^{k})\leq\frac{s}{5}$ and $d(r^{k},c_{2}^{k})>\frac{s}{5}$, then
the robber moves away from cop $c_{1}$; $r^{k+1}$ is the point at distance
$\frac{s}{10}$ on the geodesic through $r^{k},c_{1}^{k}$ which is further away
from $c_{1}^{k}$. We consider $B(r^{k},\frac{s}{5})$, the disk of radius at
most $\frac{s}{5}$ from $r^{k}$ on $S$ and this is isometric to a hyperbolic
disk by Lemma 2.2. It follows that
$d(r^{k+1},c_{1}^{k})=d(r^{k},c_{1}^{k})+\frac{s}{10}$. By the triangle
inequality $d(r^{k+1},c_{2}^{k})>\frac{s}{10}$. If
$d(r^{k},c_{1}^{k})\leq\frac{s}{5}$ and $d(r^{k},c_{2}^{k})>\frac{s}{5}$ we
use the same strategy by interchanging the roles of $c_{1},c_{2}$. Hence we
can assume $d(r^{k},c_{1}^{k}),d(r^{k},c_{2}^{k})\leq\frac{s}{5}$. Note that
$c_{1}^{k},c_{2}^{k}$ are now in the hyperbolic disk $B(r^{k},\frac{s}{5})$ of
radius $\frac{s}{5}$ centred at $r^{k}$. We consider the disk
$B(r^{k},\frac{s}{5})$ being embedded in the Poincaré disk, and consider the
geodesic $h$ through $c_{1}^{k},c_{2}^{k}$ in this disk and let $o_{h}(r^{k})$
be the orthogonal geodesic to $h$ passing through $r^{k}$. Now let $r^{k+1}$
be the point at distance $\frac{s}{10}$ on the geodesic $o_{h}(r^{k})$ which
is further away from $g$. If $c_{j}^{k}$ is on $o_{h}(r^{k})$ then
$d(r^{k+1},c_{j}^{k})=d(r^{k},c_{j}^{k})+\frac{s}{10}>\frac{s}{10}$. If
$c_{j}^{k}$ is not on $o_{h}(r^{k})$, then $\angle c_{j}^{k},o_{h}(r^{k})\cap
h,r^{k+1}$ form a right angle and by the hyperbolic Pythagorean theorem
$d(c_{j}^{k},r^{k+1})>\frac{s}{10}$. ∎

###  4.2. Upper bound for cop catch number

The following lemma shows how to capture the robber on the universal covering
space $\mathcal{D}$, if the robber is contained in a polygon which is guarded
by the cops.

######  Lemma 4.2.

Suppose the robber is contained in a bounded convex polygon in the Poincaré
disk $\mathcal{D}$ where $n$ cops guard the boundary of the polygon. Then
these $n$ cops can catch the robber.

###### Proof.

Suppose the robber is contained in a bounded convex polygon at the beginning
of the game. For all $k\geq 0$ we consider the bisectors $b_{j}^{k}$ between
the robber’s position $r^{k}$ and each of the cops’ positions $c_{j}^{k}$
($j\in[n]$), and let $B_{j}^{k}$ be the midpoint between $r^{k}$ and
$c_{j}^{k}$, see Figure 7 and Figure 8.

The bisectors $b_{j}^{0}$ bound a polygon $P_{0}$ containing the robber,
otherwise there is a point on the boundary of the Poincaré disk towards which
the robber can walk and escape from the cops. Without loss of generality let
$b_{1}^{0},\dots,b_{n}^{0}$ appear consecutively on the convex hull of
$P_{0}$, see Figure 7 for an example with $n=4$. Let $\alpha_{j,{j+1}}^{k}$ be
the angle between the bisector $b_{j}^{k}$ and $b_{j+1}^{k}$ (we consider the
indices modulo $n$) and let $P_{j,j+1}^{k}$ be their intersection point.

$r$$c_{1}$$b_{1}$$P_{1,2}$$b_{2}$$c_{2}$$c_{4}$$b_{4}$$c_{3}$$b_{3}$$P_{4,1}$$P_{3,4}$$P_{2,3}$$\alpha_{2,3}$$\alpha_{1,2}$$\alpha_{4,1}$$\alpha_{3,4}$$\beta_{1,2}$$\beta_{2,3}$$\beta_{3,4}$$\beta_{4,1}$
Figure 7. A schematic figure when the number of cops is $n=4$. A label $x$ in
the figure denotes the value $x^{k}$. That is, the figure depicts the
positions of the cops $c_{i}^{k}$ ($i=1,2,3,4$), the intersection points
$P_{i,i+1}^{k}$ of the bisectors $b_{i}^{k},b_{i+1}^{k}$, and the angles
$\beta_{i,i+1}^{k},\alpha_{i,i+1}^{k}$.

Every cop has the same strategy, which is as follows. Cop $c_{j}$ copies the
move of the robber by reflecting it along the bisector $b_{j}$ and
subsequently if there is any agility left she moves as close to the robber as
possible (see Figure 8).

$r^{k-1}$$c_{1}^{k-1}$$b_{1}^{k-1}=b_{1}^{k}$$Q^{k}$$r^{k}$$c_{1}^{k}$$B_{1}^{k}$$B_{1}^{k-1}$

$r^{k-1}$$c_{1}^{k-1}$$b_{1}^{k-1}$$Q^{k}$$c_{1}^{k}$$B_{1}^{k}$$B_{1}^{k-1}$$r^{k}$$b_{1}^{k}$

Figure 8. A step $K_{1}^{+}$ in comparison to a step $K_{1}^{-}$. In both
cases the distance of $r^{k}$ to $r^{k-1}$ is the same and hence the move of
cop $c_{1}$ is the same.

More precisely, in the $k$-th round the cop $c_{j}^{k-1}$ will move to
$o_{b_{j}^{k-1}}(r^{k})$, as close to the robber as possible. In particular,
$b_{j}^{k-1}$ and $b_{j}^{k}$ are parallel and the voronoi cell of the robber
with respect to $b_{j}^{k}$ is contained in the voronoi cell with respect to
$b_{j}^{k-1}$. Therefore throughout the whole game, the robber is restricted
to $P_{0}$. We have to show that with this strategy the robber is eventually
caught. If

$\displaystyle\sum_{k=1}^{\infty}\tau(k)-d(r^{k},r^{k-1})=\infty,$

then the cops catch the robber. Note that while the robber is not caught, the
distance between $b_{j}^{k-1}$ and $b_{j}^{k}$ is at least
$\tau(k)-d(r^{k},r^{k-1})$. The part of the Poincaré disk
$\mathcal{D}\setminus b_{j}^{k}$ containing the cop $c_{j}$ eventually
includes $P_{0}$, in which $r^{k}$ is contained, which is a contradiction
since $b_{j}^{k}$ is a bisector.

Hence we assume that the robber moves an infinite distance, that is

$\displaystyle\sum_{k=1}^{\infty}d(r^{k},r^{k-1})=\infty.$

We want to show that also in this case one of the bisectors surpasses the
polygon. Note that for some $j$, $\alpha_{j,j+1}^{0}<(n-2)\pi/n$ since the
angle sum in a hyperbolic $n$-gon is upper bounded by the angle sum in an
Euclidean $n$-gon. We suppose $j=1$ in the following and will show, that
either $b_{1}^{k}$ or $b_{2}^{k}$ eventually surpasses the polygon. By the
following claim we can assume that also $\alpha_{1,2}^{k}<(n-2)\pi/n$ for all
positive integers $k$, as all the angles are non-decreasing and one of them
has to stay below $(n-2)\pi/n$.

######  Claim 4.3.

The angles in the guarded polygon are increasing, which means

$\displaystyle\alpha_{j,j+1}^{k}\geq\alpha_{j,j+1}^{k-1}.$

###### Proof.

We consider the step of the cop $c_{j}$ and the cop $c_{j+1}$ separately,
imagining the cop $c_{j}$ takes her turn first. Let $P^{\prime}$ be the
intersection point between $b_{j}^{k},b_{j+1}^{k-1}$ and let $\alpha^{\prime}$
be the angle between $b_{j}^{k},b_{j+1}^{k-1}$. If $b_{j}^{k}=b_{j}^{k-1}$,
then $\alpha^{\prime}=\alpha_{j,j+1}^{k-1}$. Otherwise $b_{j}^{k}\neq
b_{j}^{k-1}$ and note that $b_{j}^{k}$ is orthogonal to
$o_{b_{j}^{k-1}}(r^{k})$. In particular, $b_{j}^{k-1}$ and $b_{j}^{k}$ are
parallel, see Figure 8. Since the quadrilateral
$B_{j}^{k},B_{j}^{k-1},P_{j,j+1}^{k-1},P^{\prime}$ has angle sum smaller than
$2\pi$ and has a right angle at $B_{j}^{k-1}$ and $B_{j}^{k}$, it holds that
the angle at $P^{\prime}$ in the quadrilateral is smaller than
$\pi-\alpha_{j,j+1}^{k-1}$ but then $\alpha^{\prime}>\alpha_{j,j+1}^{k-1}$.
Now we consider the quadrilateral formed by
$B_{j+1}^{k},B_{j+1}^{k-1},P^{\prime},P_{j,j+1}^{k}$. By the same argument,
$\alpha_{j,j+1}^{k}>\alpha^{\prime}$. ∎

We want in the following that the angle between $\overline{r^{k-1}r^{k}}$ and
$\overline{r^{k}c_{j}^{k}}$ for $j=1$ or $j=2$ is bounded away from $\pi/2$,
as this will help the cop $c_{1}$ or $c_{2}$ to get closer to the robber. We
show that if the angle between $\overline{r^{k-1}r^{k}}$ and
$\overline{r^{k}c_{1}^{k}}$ is close to $\pi/2$, then the angle between
$\overline{r^{k-1}r^{k}}$ and $\overline{r^{k}c_{2}^{k}}$ is bounded away from
$\pi/2$ by bounding the angle $\beta_{1,2}^{k}$, see Figure 7. We define the
angle $\beta_{1,2}^{k}$ for every $k\in\mathbb{N}$ as the angle between
$\overline{r^{k}c_{1}^{k}}$ and $\overline{r^{k}c_{2}^{k}}$.

######  Claim 4.4.

It holds that

$\displaystyle\operatorname{acot}\left(\frac{\cosh(d\left(P_{1,2}^{k},r^{k}\right))}{\cot((n-2)\pi/n)}\right)\leq\beta_{1,2}^{k}\leq\pi-\alpha_{1,2}^{k}.$

###### Proof.

Since $\alpha_{1,2}^{k}\leq(n-2)\pi/2$, there is a quadrilateral formed by
$r^{k}B_{1}^{k}P_{1,2}^{k}B_{2}^{k}$ with right angles at $B_{1}^{k}$ and
$B_{2}^{k}$. Since a quadrilateral has angle sum at most $2\pi$ it holds that
$\beta_{1,2}^{k}\leq\pi-\alpha_{1,2}^{k}$. On the other hand ([23, Corollary
32.13]),

$\cot\left(\angle
P_{1,2}^{k}r^{k}B_{1}^{k}\right)=\frac{\cosh\left(d\left(P_{1,2}^{k},r^{k}\right)\right)}{\cot\left(\angle
r^{k}P_{1,2}^{k}B_{1}^{k}\right)}\leq\frac{\cosh\left(d\left(P_{1,2}^{k},r^{k}\right)\right)}{\cot\left(\left(n-2\right)\pi/n\right)}.$

Since $\beta_{1,2}^{k}\geq\angle P_{1,2}^{k}r^{k}B_{1}^{k}$ the claim follows.
∎

Note that $\alpha_{1,2}^{k}\geq\alpha_{1,2}^{0}$ by Claim 4.3 and
$d\left(P_{1,2}^{k},r^{k}\right)$ is upper bounded by the diameter $D$ of
$P_{0}$. Let

$\beta=\min\left\\{\operatorname{acot}\left(\frac{\cosh(D)}{\cot((n-2)\pi/n)}\right),\alpha_{1,2}^{0}\right\\}.$

If the angle at $r^{k}$ between $\overline{r^{k-1}r^{k}}$ and
$\overline{r^{k}c_{1}^{k}}$ is in
$[\frac{\pi}{2}-\frac{\beta}{2},\frac{\pi}{2}+\frac{\beta}{2}]$, then the
angle between $\overline{r^{k-1}r^{k}}$ and $\overline{r^{k}c_{2}^{k}}$ is in
$[0,\frac{\pi}{2}-\frac{\beta}{2}]\cup[\frac{\pi}{2}+\frac{\beta}{2},\pi]$ by
Claim 4.4 and the definition of $\beta$. Let $K_{j}$ for $j=1,2$ be the set of
rounds at which the angle between $\overline{r^{k-1}r^{k}}$ and
$\overline{r^{k}c_{j}^{k}}$ is not in
$[\frac{\pi}{2}-\frac{\beta}{2},\frac{\pi}{2}+\frac{\beta}{2}]$. Without loss
of generality,

$\displaystyle\sum_{k\in K_{1}}d(r^{k},r^{k-1})=\infty.$

We will show that if the cop $c_{1}$ does not catch the robber, then
$b_{1}^{k}$ eventually surpasses $P_{0}$, which is a contradiction. Let
$Q^{k}$ be the closest point to $r^{k-1}$ on the geodesic $r^{k}c_{1}^{k}$.
Let $K_{1}^{+}$ be the time steps in $K_{1}$ in which the robber’s position
$r^{k}$ is closer to $c_{1}^{k}$ than $Q^{k}$ to $c_{1}^{k}$ and let
$K_{1}^{-}$ be the remaining steps, see Figure 8. If $k$ is a step of type
$K_{1}^{-}$, then the distance between $b_{1}^{k-1}$ and $b_{1}^{k}$ is at
least $d(r^{k},Q^{k})$. Suppose $k$ is a step of type $K_{1}^{+}$. Since
$r^{k-1}Q^{k}B_{1}^{k}B_{1}^{k-1}$ is a Lambert quadrilateral with acute angle
at $r^{k-1}$, it holds that $d(r^{k-1},B_{1}^{k-1})\leq d(Q^{k},B_{1}^{k})$.
Hence $d(r^{k},Q^{k})$ is the distance that the cop $c_{1}$ is getting closer
to $r$ in step $k$. We will show that

$\displaystyle\sum_{k\in K_{1}}d(r^{k},Q^{k})=\infty,$

which then proves that the robber is eventually caught. Note that the triangle
$r^{k-1}Q^{k}r^{k}$ has a right angle at $Q^{k}$ and an angle at $r^{k}$ not
in $[\frac{\pi}{2}-\frac{\beta}{2},\frac{\pi}{2}+\frac{\beta}{2}]$. In fact,
this angle is at most $\frac{\pi}{2}-\frac{\beta}{2}$, since it is in a right-
angled triangle. By the cosine formula for right hyperbolic triangles (see
[30]), it follows that

$\displaystyle
d\left(r^{k},Q^{k}\right)\geq\operatorname{atanh}\left(\cos\left(\frac{\pi}{2}-\frac{\beta}{2}\right)\tanh\left(d\left(r^{k},r^{k-1}\right)\right)\right).$

Using that $\tanh(x)$ is monotonly increasing and for small $x$, $\tanh(x)\geq
x\left(1-x^{2}/3\right)$, we get that

$\displaystyle\sum_{k\in
K_{1}}\tanh\left(d\left(r^{k},r^{k-1}\right)\right)=\infty.$

But then, since $\operatorname{atanh}(x)\geq x$, we also have

$\displaystyle\sum_{k\in K_{1}}d(r^{k},Q^{k})\geq\sum_{k\in
K_{1}}\operatorname{atanh}\left(\cos\left(\frac{\pi}{2}-\frac{\beta}{2}\right)\tanh\left(d\left(r^{k},r^{k-1}\right)\right)\right)=\infty,$

thus the bisector $b_{1}^{k}$ eventually surpasses $P_{0}$, a contradiction,
or the distance between the cop $c_{1}$ and robber decreases to $0$. ∎

We now use Lemma 4.2 to bound $c_{0}$ from above for the special surfaces
$S(g),S^{\prime}(g)$ and $N(g)$.

######  Theorem 4.5.

If $g\geq 2$, then $c_{0}(S(g))\leq 5$, $c_{0}(S^{\prime}(g))\leq 6$ and
$c_{0}(N(g))\leq 4$.

###### Proof.

We will give the proof only for $S(g)$, the proof for the other surfaces is
similar. Let $O$ be the midpoint of the fundamental polygon
$P\left(4g,\frac{2\pi}{4g}\right)$. We will play the game in the covering
space and choose the player’s positions such that they are in
$P\left(4g,\frac{2\pi}{4g}\right)$. We will first use the cops
$c_{1},c_{2},c_{3}$ to guard isometric paths. We start by moving cop $c_{1}$
to the isometric path $\overline{Ov_{1}}$, cop $c_{2}$ to the isometric path
$\overline{Ov_{5}}$ and cop $c_{3}$ to the isometric path $\overline{Ov_{9}}$.
By Lemma 1.2 we can assume that after a finite amount of time the cops guard
the respective isometric paths. Now if the robber is in one of the triangles
$Ov_{j}v_{j+1}$ for some $1\leq j\leq 4$, then the robber’s moves are
restricted to the specified triangles since $a_{1}=a_{3}^{-1}$ and
$a_{2}=a_{4}^{-1}$. Similarly if the robber is contained in one of the
triangles $Ov_{j}v_{j+1}$ for some $5\leq j\leq 8$ his moves are restricted to
these triangles. If the robber is outside $Ov_{j}v_{j+1}$ for some $1\leq
j\leq 8$, we move cop $c_{2}$ to the isometric path $\overline{Ov_{13}}$ and
wait until she is guarding it. If the robber is in one of the triangles
$Ov_{j}v_{j+1}$ for $9\leq j\leq 12$, his moves are restricted to these
triangles. If the robber is not contained in one of these triangles we keep
going for $i=3,4,\dots$ in the same way, moving the cop currently guarding
$\overline{Ov_{1+4i}}$ to guard $\overline{Ov_{1+4(i+2)}}$ unless $i+2=g$, in
which case the robber is contained in one of
$Ov_{4g-3}v_{4g-2},Ov_{4g-2}v_{4g-1},Ov_{4g-1}v_{4g}$ or $Ov_{4g}v_{1}$, cop
$c_{1}$ guards $Ov_{1}$ and one of $c_{2}$ or $c_{3}$ guards $Ov_{4g-3}$.

Hence we can assume without loss of generality that cop $c_{1}$ guards
$\overline{Ov_{1}}$, cop $c_{2}$ guards $\overline{Ov_{5}}$ and the robber is
in one of the triangles $Ov_{j}v_{j+1}$ for some $1\leq j\leq 8$. Cop
$c_{3},c_{4},c_{5}$ will guard
$\overline{Ov_{2}},\overline{Ov_{3}},\overline{Ov_{4}}$, respectively. Now the
robber is captured in either $R_{1}=Ov_{1}v_{2}\cup Ov_{3}v_{4}$ or
$R_{2}=Ov_{2}v_{3}\cup Ov_{4}v_{5}$. The regions $R_{1}$ and $R_{2}$ can be
embedded in the covering space $\mathcal{D}$ such that they form a
quadrilateral which is guarded by four of the cops. By Lemma 4.2 we can now
catch the robber. ∎

##  5\. Generalizations

The proof of Theorem 3.1 can be generalized to higher dimensional hyperbolic
manifolds. We first prove the following lemma, which will replace the
isometric path lemma in the proof of Theorem 3.1.

######  Lemma 5.1.

Let the Cops and Robber game be played on an Euclidean disk, a disk on the
unit sphere of radius at most $\frac{\pi}{2}$ or a hyperbolic disk $B^{2}$. If
the cops position $c^{k_{0}}$ is on the line between the center $O$ of $B^{2}$
and the position of the robber $r^{k_{0}}$, then the cop can guard the disk of
radius $\frac{1}{2}(d(O,c^{k_{0}})+d(O,r^{k_{0}}))$ and center $O$.

###### Proof.

Let $d_{k}=\frac{1}{2}(d(O,c^{k})+d(O,r^{k}))$ and $D_{k}$ be the disk of
radius $d_{k}$ and center $O$. We explain the cop’s strategy for the time
steps $k\geq k_{0}$. First suppose that the geodesic segment from $r^{k}$ to
$r^{k+1}$ passes through $D_{k}$, we show that the cop can catch the robber.
We are allowed to subdivide the robber’s step since this is only to the
advantage of the robber, so we assume without loss of generality
$d(O,r^{k+1})=d_{k}$. We can assume $r^{k+1}\neq c^{k}$ and we consider the
closest point $p$ from $r^{k+1}$ on the geodesic through $O$ and $r^{k}$.

$O$$r^{k}$$r^{k+1}$$p$$c^{k}$$d_{k}$ Figure 9. Depicted is the point $p$ which
is the closest point on $Or^{k}$ from the robber’s position $r^{k+1}$.

By the Pythagorean theorem (in the Euclidean or hyperbolic plane or for a
right angled triangle on a spherical hemisphere),

$\displaystyle d(O,p)<d_{k},$

hence $d(r^{k},p)>d(c^{k},p)$. But then using the Pythagorean theorem again on
the triangles $c^{k}pr^{k+1}$ and $r^{k+1}pr^{k}$ which both have a right
angle at $p$, it follows that $d(r^{k+1},c^{k})<d(r^{k+1},r^{k})$, so the cop
can catch the robber.

We show now that if $d(O,r^{k+1})>d_{k}$ and the cop does not pass through
$D$, there exists a position of the robber on $\overline{Or^{k+1}}$ such that

(5.1) $\displaystyle d(O,c^{k+1})-d(O,c^{k})\geq d(O,r^{k})-d(O,r^{k+1}).$

By subdividing the robber’s step, we can assume that the triangle
$Or^{k}r^{k+1}$ has angle at most $\frac{\pi}{2}$ at $O$. Suppose first the
angle at $r^{k}$ in the triangle $Or^{k}r^{k+1}$ is smaller than $\pi$. The
cop moves to the point $c^{k+1}$ on $\overline{Or^{k+1}}$ such that

$\displaystyle d(O,c^{k+1})-d(O,c^{k})=d(O,r^{k})-d(O,r^{k+1}).$

We show now that this is a valid move, which means $d(c^{k},c^{k+1})\leq
d(r^{k},r^{k+1})$.

$O$$r^{k}$$r^{k+1}$$p_{r}$$c^{k}$$c^{k+1}$$p_{c}$ Figure 10. The case where
the angle at $r^{k}$ in the triangle $Or^{k}r^{k+1}$ is smaller than $\pi$.

If $r^{k+1}$ is on the geodesic $Or^{k}$, then the cop moves as far as the
robber, hence this is a valid move for the cop. Otherwise consider the closest
points $p_{c},p_{r}$ on the geodesic $Or^{k}$ of $c^{k+1},r^{k+1}$,
respectively. Then using the Pythagorean theorem again,
$d(O,c^{k+1})>d(O,p_{c})$ and $d(O,r^{k+1})>d(O,p_{r})$. Therefore it holds
that $d(p_{c},c^{k})<d(O,c^{k+1})-d(O,c^{k})$ and
$d(p_{r},r^{k})>d(O,r^{k})-d(O,r^{k+1})$. Using the Pythagorean theorem again,
$d(c^{k},c^{k+1})<d(r^{k},r^{k+1})$, hence 5.1 is a valid move.

Suppose now the angle at $r^{k}$ in the triangle $Or^{k}r^{k+1}$ is larger
than $\pi$. Then this is of advantage to the cop since the robber moves
further away from $O$, i.e.

$d(O,r^{k})-d(O,r^{k+1})<0.$

The cop can simply move at a right angle to $Oc^{k}$ and

$\displaystyle d(O,c^{k+1})-d(O,c^{k})\geq 0,$

which establishes (5.1). As long as the cop has not caught the robber, the
value $d_{k}$ is increasing, and as soon as the robber passes through the disk
$D_{k}$, he is caught. This proves the lemma. ∎

###### Proof of Theorem 1.6..

Suppose $M=\mathbb{H}^{n}/\Gamma$ where $\Gamma$ is a torsion-free, discrete
group of isometries on $\mathbb{H}^{n}$. Let $D$ be the diameter of $M$. We
position the cop $c_{2}$ in the covering space such that she is of distance at
most $D$ to a point $O$ on the isometric path $\overline{C_{1}^{k}R^{k}}$ at
distance between $9D$ and $11D$ from the robber’s position (and further from
cops $c_{1}$). By Lemma 5.1, the cop $c_{2}$ can guard the $n$-dimensional
ball $B$ of radius $4D$ with center $O$ after moving to $O$. We consider the
$(n-1)$-dimensional hyperplane $H$ through $O$ which is perpendicular to the
geodesic $C_{1}^{k}R^{k}$. Note that cop $c_{2}$ guards all points on $H$ of
distance at most $4D$ to $O$. We denote by $o_{H}(C_{1}^{k})$ the orthogonal
geodesic to $H$ which contains $C_{1}^{k}$. Now at the cops’ turn, we consider
the positions $C_{1}^{k},R^{k+1}$ and $o_{H}(C_{1}^{k})\cap H$. These points
lie on a common $2$-dimensional subspace of $\mathcal{D}^{n}$ which is
isometric to $\mathcal{D}^{2}$ and is also isometric as a subset of
$\mathcal{D}^{n}$. Now the cop can use the strategies (a) and (b) outlined in
Theorem 3.1 on this subspace. The proof idea for the lower bound is the same
as in the case $n=2$. ∎

We are ready to summarise our results about manifolds of constant curvature,
i.e.  _space forms_.

######  Theorem 5.2.

If $M$ is a compact manifold of constant curvature, then $c(M)=2$.

###### Proof.

If $M_{g^{p}}$ is a Riemannian manifold equipped with a Riemannian metric
$g^{p}$ and constant curvature $C\neq 0$, we can equip the same space with the
Riemannian metric ${g^{p}}^{*}=|C|\cdot g^{p}$ instead. This gives a
Riemannian manifold $M_{{g^{p}}^{*}}$ of constant curvature $1$ or $-1$. Given
the step function $\tau$ for $M_{g^{p}}$, we can play the game with step
function $\sqrt{|C|}\cdot\tau$ on $M_{{g^{p}}^{*}}$ instead. By rescaling the
lengths of the steps appropriately, $k$ cops can win the game on $M_{g}$ if
and only if they can win the game on $M_{{g^{p}}^{*}}$. The result follows for
negative curvature by Theorem 1.6, for constant curvature $0$ by generalizing
[17, Lemma 8] and positive constant curvature by generalizing the results for
the sphere in [17, Theorem 4].333The upper bound follows from the Killing-Hopf
theorem and the covering-space method and the lower bound by considering a
small enough agility function that allows the robber to move in the opposite
direction to the cop without being caught. ∎

We also would like to point out that for the cop catching number one can
obtain a lower bound of one larger than the dimension of the manifold by a
similar argument as in Theorem 4.1. Further, Lemma 4.2 can be extended to
higher dimensional hyperbolic spaces, if $n$ cops guard the boundary of a
convex polytope which contains the robber, then they can catch the robber in
finite time.

##  6\. Concluding remarks

One of the main open question is Conjecture 1.5 on the cop win number of
surfaces. A first step towards it would be to lower the multiplicative
constant for upper bounds that are linear in $g$, as was done for graphs of
genus $g$. Note that in general the cop number of a compact metric space can
be infinite [14]. It would be nice to find more properties of spaces that
guarantee a finite (or constant) cop win number.

When considering compact surfaces of constant curvature, it is still open
whether (and how) the cop catch number grows with the genus of the surface. It
is easy to show that a linear number (depending on the genus) of cops is
sufficient using Lemma 4.2, by cutting the surface into smaller parts using
isometric paths (similarly as was done in [26]). We obtained that on natural
constant curvature surfaces the cop number is bounded by a constant
(irrespectively of the genus). A first step towards understanding the cop
catch number on constant curvature surfaces would be to find the exact cop
catch number for the surfaces $S(g),S^{\prime}(g)$ and $N(g)$. More
importantly, is the cop catch number bounded by a constant on hyperbolic
surfaces?

## References

  * [1] Marco Abate and Francesca Tovena, _Curves and surfaces_ , Unitext, vol. 55, Springer, Milan, 2012.
  * [2] M. Aigner and M. Fromme, _A game of cops and robbers_ , Discrete Appl. Math. 8 (1984), no. 1, 1–11.
  * [3] Andrew Beveridge and Yiqing Cai, _Two-dimensional pursuit-evasion in a compact domain with piecewise analytic boundary_ , ArXiv e-prints arXiv:1505.00297 (2015).
  * [4] Béla Bollobás, Gábor Kun, and Imre Leader, _Cops and robbers in a random graph_ , Journal of Combinatorial Theory, Series B 103 (2013), no. 2, 226–236.
  * [5] Béla Bollobás, Imre Leader, and Mark Walters, _Lion and man—can both win?_ , Israel J. Math. 189 (2012), 267–286. MR 2931397
  * [6] Anthony Bonato, _An invitation to pursuit-evasion games and graph theory_ , Student Mathematical Library, vol. 97, American Mathematical Society, Providence, RI, 2022.
  * [7] Anthony Bonato and Richard J. Nowakowski, _The game of cops and robbers on graphs_ , Student Mathematical Library, vol. 61, American Mathematical Society, Providence, RI, 2011. MR 2830217
  * [8] Nathan Bowler, Joshua Erde, Florian Lehner, and Max Pitz, _Bounding the cop number of a graph by its genus_ , SIAM J. Discrete Math. 35 (2021), no. 4, 2459–2489. MR 4327323
  * [9] Peter Bradshaw, _A proof of the meyniel conjecture for abelian cayley graphs_ , Discrete Mathematics 343 (2020), no. 1, 111546.
  * [10] H. T. Croft, _’Lion and man’: A postscript_ , J. Lond. Math. Soc. 39 (1964), 385–390 (English).
  * [11] Joshua Erde and Florian Lehner, _Improved bounds on the cop number of a graph drawn on a surface_ , Extended Abstracts EuroComb 2021, Springer, 2021, pp. 111–116.
  * [12] Peter Frankl, _Cops and robbers in graphs with large girth and Cayley graphs_ , Discrete Appl. Math. 17 (1987), no. 3, 301–305.
  * [13] Alan Frieze, Michael Krivelevich, and Po-Shen Loh, _Variations on cops and robbers_ , J. Graph Theory 69 (2012), no. 4, 383–402. MR 2979296
  * [14] Agelos Georgakopoulos, _Compact metric spaces with infinite cop number_ , ArXiv e-prints arXiv:2309.03757 (2023).
  * [15] Heinz Hopf, _Zum Clifford-Kleinschen Raumproblem_ , Math. Ann. 95 (1926), no. 1, 313–339.
  * [16] Seyyed Aliasghar Hosseini, Bojan Mohar, and Sebastian Gonzalez Hermosillo de la Maza, _Meyniel’s conjecture on graphs of bounded degree_ , J. Graph Theory 97 (2021), no. 3, 401–407. MR 4313187
  * [17] Vesna Iršič, Bojan Mohar, and Alexandra Wesolek, _Cops and robber game in higher-dimensional manifolds with spherical and Euclidean metric_ , C. R. Math. Acad. Sci. Soc. R. Can. 44 (2022), no. 3, 50–68.
  * [18] Gwenaël Joret, Marcin Kamiński, and Dirk Oliver Theis, _The cops and robber game on graphs with forbidden (induced) subgraphs_ , Contrib. Discrete Math. 5 (2010), no. 2, 40–51. MR 2791289
  * [19] Wilhelm Killing, _Ueber die Clifford-Klein’schen Raumformen_ , Math. Ann. 39 (1891), no. 2, 257–278.
  * [20] J. E. Littlewood, _Littlewood’s miscellany_ , Cambridge University Press, Cambridge, 1986, Edited and with a foreword by Béla Bollobás. MR 872858
  * [21] Linyuan Lu and Xing Peng, _On Meyniel’s conjecture of the cop number_ , J. Graph Theory 71 (2012), no. 2, 192–205. MR 2965383
  * [22] Tomasz Łuczak and Paweł Prałat, _Chasing robbers on random graphs: zigzag theorem_ , Random Structures & Algorithms 37 (2010), no. 4, 516–524.
  * [23] George E. Martin, _The foundations of geometry and the non-Euclidean plane_ , Undergraduate Texts in Mathematics, Springer-Verlag, New York-Berlin, 1982, Reprint.
  * [24] Bojan Mohar, _Notes on cops and robber game on graphs_ , ArXiv e-prints arXiv:1710.11281 (2017).
  * [25] by same author, _Min-max theorem for the game of cops and robber on geodesic spaces_ , ArXiv e-prints arXiv:2112.0301 (2021).
  * [26] by same author, _The game of cops and robber on geodesic spaces_ , ArXiv e-prints arXiv:2205.11633 (2022).
  * [27] N. Yu. Satimov and A. Sh. Kuchkarov, _On the solution of a model differential pursuit-evasion game on a sphere_ , Uzb. Mat. Zh. 2000 (2000), no. 1, 45–50 (Russian).
  * [28] Bernd SW Schröder, _The copnumber of a graph is bounded by [3/2 genus (g)]+ 3_ , Categorical perspectives, Springer, 2001, pp. 243–263.
  * [29] Alex Scott and Benny Sudakov, _A bound for the cops and robbers problem_ , SIAM J. Discrete Math. 25 (2011), no. 3, 1438–1442. MR 2837608
  * [30] Stothers, Wilson, _Hyperbolic geometry_ , http://www.maths.gla.ac.uk/wws/cabripages/hyperbolic/hyperbolic0.html, [Online; accessed 16-January-2023].
  * [31] Olga Yufereva, _Lion and man game in compact spaces_ , Dyn. Games Appl. 9 (2019), no. 1, 281–292.

##  Appendix A Proofs of technical lemmas

###### Proof of Lemma 2.2.

Consider $B(a,r)$ as a disk in the universal covering space $\mathcal{D}$. Let
$x,y\in B(a,r)$, then the isometric path $g$ between $x$ and $y$ in the copy
of $B(a,r)$ in the universal covering space $\mathcal{D}$ is a locally
isometric path from $x$ to $y$ in $S$. Suppose $\overline{xy}\neq g$. Then the
closed path $P$ going from $x$ to $y$ along $\overline{xy}$ and from $y$ to
$x$ along $g$ is of length less than $\operatorname{sys}(S)$ and consists of
two paths which are locally isometric and bounds a region which is non-empty.

The Gauss-Bonnet Theorem states that for a region $R\subset S$ with sectional
curvature $K$, piecewise smooth boundary $\partial(R)$,

$\displaystyle\int_{R}K\,dA+\int_{\partial(R)}k_{g}\,ds=2\pi\chi(R),$

where $dA$ is the element of area of the surface, and $ds$ is the line element
along the boundary, and $\int_{\partial(R)}k_{g}ds$ is the sum of the
corresponding integrals of the geodesic curvature $k_{g}$ along the smooth
portions of the boundary, plus the sum of the angles by which the smooth
portions turn at the corners of the boundary.

Consider the curve $P$ which is piecewise geodesic. Since the curve $P$ has
length strictly smaller than $\operatorname{sys}(S)$, it has to be
contractible. The curve $P$ bounds a region $R$. Since the curvature of
locally isometric curves is $0$, by Gauss-Bonnet

$\displaystyle\int_{R}-1dA+\theta_{1}-\pi+\theta_{2}-\pi=2\pi\chi(R),$

where $\theta_{1},\theta_{2}$ are the exterior angles between the locally
isometric paths at $x$ and $y$. Since $P$ is contractible, the Euler
characteristic of $R$ is $1$, hence $\theta_{1}=\theta_{2}=2\pi$ and
$\int_{R}1dA=0$, which means that the isometric path between $x$ and $y$ goes
along the geodesic $g$. ∎

In the following proofs, denote $d(B,C)=a$, $d(A,C)=b$ and $d(A,B)=c$,
$\alpha$ is the angle at $A$, $\beta$ is the angle at $B$ and $\gamma$ is the
angle at $C$.

###### Proof of Lemma 2.3.

This is a simple application of the Pythagorean Theorem for hyperbolic
triangles. Suppose $X,Y\in\overline{AC}$ with $X\in\overline{YC}$. Since
$\cosh$ is strictly increasing on the positive real axis and
$\operatorname{acosh}$ is strictly increasing

$\displaystyle d(Y,B)$
$\displaystyle=\operatorname{acosh}(\cosh(a)\cosh(d(Y,C)))$
$\displaystyle\geq\operatorname{acosh}(\cosh(a)\cosh(d(X,C)))=d(X,B)$

with equality if and only if $X=Y$. The lemma follows by using this inequality
twice,

$\displaystyle d(X_{2},B)-d(X_{3},B)\leq c-d(X_{3},B)\leq c-d(X_{1},B).$

Clearly, $d(X_{2},B)-d(X_{3},B)=c-d(X_{1},B)$ if and only if $X_{2}=A$ and
$X_{3}=X_{1}$. ∎

###### Proof of Lemma 2.4.

For a vertex $X\in\overline{AC}$, by the Pythagorean Theorem for hyperbolic
triangles

$\displaystyle d(X,B)=\operatorname{acosh}(\cosh(a)\cosh(d(X,C))).$

The second derivative with respect to $d(X,C)$ is

$\displaystyle\frac{\partial^{2}d(X,B)}{\partial
d(X,C)^{2}}=\frac{(\cosh(d(X,C))\cosh(a)\sinh^{2}(a))}{(-1+\cosh^{2}(a)\cosh^{2}(d(X,C)))^{3/2}}.$

Therefore, $\frac{\partial^{2}d(X,B)}{\partial d(X,C)^{2}}>0$ for positive
values of $a$ and $d(X,C)$, hence $d(X,B)$ is convex for $d(X,C)>0$. This
means that the secant

$\displaystyle\frac{d(X,B)-d(Y,B)}{d(X,C)-d(Y,C)}$

is monotonely increasing (in both $d(X,C)$ and $d(Y,C)$). Consequently,

$\displaystyle\frac{c-d(X_{1},B)}{d(A,X_{1})}$
$\displaystyle=\frac{c-d(X_{1},B)}{b-d(X_{1},C)}$
$\displaystyle\geq\frac{d(X_{2},B)-d(X_{3},B)}{d(X_{2},C)-d(X_{3},C)}=\frac{d(X_{2},B)-d(X_{3},B)}{d(X_{2},X_{3})},$

and since $d(A,X_{1})=d(X_{2},X_{3})$, this proves the lemma. ∎

###### Proof of Lemma 2.5.

By the law of cosines

$\displaystyle\gamma=\arccos\left(\frac{\cosh(c)-\cosh(b)\cosh(a)}{-\sinh(a)\sinh(b)}\right).$

Since $\arccos$ is monotonely decreasing, we only need to show that $f$ as
defined by below equation is monotonely increasing. We define

$\displaystyle f(b):=\frac{\cosh(c)-\cosh(b)\cosh(a)}{-\sinh(a)\sinh(b)}.$

The derivative of $f$ is

$\displaystyle f^{\prime}(b)$
$\displaystyle=\frac{\cosh(a)\sinh(a)\sinh(b)^{2}+\sinh(a)\cosh(b)(\cosh(c)-\cosh(b)\cosh(a))}{(-\sinh(a)\sinh(b))^{2}}$
$\displaystyle=\frac{-\cosh(a)\sinh(a)+\sinh(a)\cosh(b)\cosh(c)}{\sinh(a)^{2}\cosh(b)^{2}},$

where we use that $\sinh(b)^{2}-\cosh(b)^{2}=-1$. Now since
$\alpha<\frac{\pi}{2}$ it follows that $\cosh(b)\cosh(c)\geq\cosh(a)$ and
hence the derivative is non-negative. This proves the lemma.

∎

###### Proof of Lemma 2.6.

Note that by the mean value theorem for $x<y$

$\operatorname{acosh}(w\cosh(x))-\operatorname{acosh}(w\cosh(y))\geq
c\cdot(y-x)$

where
$c=\min_{\xi\in[x,y]}\partial/\partial\xi(\operatorname{acosh}(w\cosh(\xi)))$.
Since $w>1$, the partial derivative is

$\displaystyle\frac{\partial}{\partial\xi}\operatorname{acosh}(w\cosh(\xi))=\frac{w\sinh(\xi)}{\sqrt{w^{2}-1+w^{2}\sinh^{2}(\xi)}}.$

Taking $x,y\in[t_{1},t_{2}]$ with $t_{1}>0$ and noting that $\sinh(x)$ is
monotonely increasing we get that

$\displaystyle
c\geq\frac{w\sinh(t_{1})}{\sqrt{w^{2}-1+w^{2}\sinh^{2}(t_{2})}}\geq\eta$

for some $\eta>0$. ∎