ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 187-206
Pursuit-evasion in a two-dimensional domain
Andrew Beveridge
Department of Mathematics, Statistics and Computer Science, Macalester College,
Saint Paul, MN 55105
Yiqing Cai
The Institute for Mathematics and Its Applications, University ofMinnesota, Minneapolis, MN 55455
Received 16 March 2016, accepted 3 September 2016, published online 3 March 2017
In a pursuit-evasion game, a team of pursuers attempt to capture an evader. The players alternate turns, move with equal speed, and have full information about the state of the game. We consider the most restrictive capture condition: a pursuer must become colocated with the evader to win the game. We prove two general results about this adversarial motion planning problem in geometric spaces. First, we show that one pursuer has a winning strategy in any compact cat(0) space. This complements a result of Alexander, Bishop and Ghrist, who provide a winning strategy for a game with positive capture radius. Second, we consider the game played in a compact domain in Euclidean two-space with piecewise analytic boundary and arbitrary Euler characteristic. We show that three pursuers always have a winning strategy by extending recent work of Bhadauria, Klein, Isler and Suri from polygonal environments to our more general setting.
Keywords: Pursuit-evasion, lion and man, CAT(0) space, motion planning. Math. Subj. Class.: 91A24, 49N75, 53A04
1 Introduction
A pursuit-evasion game in a domain D is played between a team of pursuers pi, p2,..., pk and an evader e. The pursuers win if some pi becomes colocated with the evader after a finite number of turns, meaning that the distance d(pi, e) = 0. When this occurs, we say that pi captures e. We consider the discrete time version of the game, which proceeds in turns. Initially, the pursuers choose their positions pi,p2,... ,p0k, and then the evader chooses his initial position e0. In turn t > 1, each pursuer pi moves from her current
E-mail addresses: abeverid@macalester.edu (Andrew Beveridge), yiqingcai@ima.umn.edu (Yiqing Cai)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
188
Ars Math. Contemp. 13 (2017) 107-123
position pt-1 to a point pti e B(ptr1, 1) = {x G D | d(pt-1,x) < 1}. If the evader has been captured, then the game ends with the pursuers victorious. Otherwise, the evader moves from et-1 to a point et e B(et-1,1). The evader wins if he remains uncaptured forever. We consider the full-information (full-visibility) game in which each player knows the environment and the locations of all the other players. Furthermore, the pursuers may coordinate their movements.
Turn-based pursuit games in simply connected domains have been well-characterized: one pursuer is sufficient to capture the evader. Winning pursuer strategies have been found for environments in En [21, 16], and in simply connected polygons [14]. Taking a geometric viewpoint and using the weaker capture criterion d(p, e) < e for some constant e > 0, Alexander, Bishop and Ghrist [3] proved that a single pursuer can capture an evader in any compact cat(0) by heading directly towards the evader at maximum speed. We provide an alternate strategy for a compact cat(0) space that achieves d(p, e) = 0 in a finite number of turns. Our winning pursuer strategy is a generalization of lion's strategy, which has been used successfully in En [21] and in simple polygons [14]. We defer the description of this strategy to Section 2.
Theorem 1.1. A pursuer p using lion's strategy in a compact cat(0) space D, captures the evader e by achieving d(p, e) = 0 after at most diam(D)2 turns.
Theorem 1.1 implies that a single pursuer can become colocated with an evader in a simply connected, compact domain D c E2. In particular, this result holds for the polygonal setting in [14]. Notably, the general cat(0) viewpoint leads to an improved capture time bound for polygons, compared to the O(n ■ diam(D)) result in [14], where n is the number of vertices of polygon D.
It is easy to construct compact domains that are evader win: removing one large open set from the middle of a simply connected domain tips the game in the evader's favor. Indeed, the evader can keep this large obstruction between himself and the pursuer, indefinitely. Such an open set is called an obstacle or hole in the environment. It is not hard to show that adding a second pursuer to this two-dimensional domain gives the game back to the pursuers. Adding multiple obstacles creates a distinct topology, and it is natural to wonder how many pursuers are needed to capture an evader in such an environment. The analogous question has been resolved for pursuit-evasion games in certain two-dimensional environments. Aigner and Fromme [1] proved that three pursuers are sufficient for pursuit-evasion on a planar graph. Bhadauria, Klein, Isler and Suri [8] showed that the analogous result holds in a two-dimensional polygonal environment with polygonal holes. We generalize the latter three-pursuer result to a broader class of geometric spaces.
Our pursuit game takes place in a compact and path-connected domain D c E2. The set D contains a finite set of disjoint open obstacles O = {O1,O2,..., Ok}. The domain boundary is dD = {dO0, dO1, dO2,..., 3Ok} where we define dO0 to be the outer boundary of D, for convenience. We place two conditions on the boundary. First, dD can be decomposed into a finite number of analytic curves y(t) = (x(t), y(t)) for 0 < t < 1, where each of x(t),y(t) can locally be expanded as convergent power series. Second, we require that dD is a 1-manifold: for any x e dD, there exists an e > 0, such that B(x, e) n dD is homeomorphic to E1. In other words, we forbid self-intersections. For brevity, we say that a domain D satisfying these properties is piecewise analytic. We list three consequences of these conditions. First, the number of singular points on the boundary is finite. Second, the absolute value of the curvature at the nonsingular points of dD
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
189
is bounded above by some constant Kmax > 0. Third, there is a minimum separation dmin > 0 between boundary components: d(Oi,Oj) > dmin for all 0 < i < j < k. During the game, the pursuers will guard a sequence of geodesics; crucially, we will see in Section 4 that each of these geodesics is also piecewise analytic. This brings us to our main result.
Theorem 1.2. Three pursuers can capture an evader in a compact domain in E2 with piecewise analytic boundary. The number of turns required to capture the evader for a domain with k obstacles is O(2k ■ diam(D) + diam(D)2).
At a high level, our winning three-pursuer strategy builds on those found in [1, 8], and we are indebted to those previous papers. However, our geometric and topological approach is entirely new. In particular, our arguments are grounded in a careful investigation of the convexity, curvature and homotopy classes of geodesic curves in our domain. Furthermore, Theorem 1.2 significantly extends the class of known three-pursuer-win domains.
Finally, we recently became aware of an unpublished technical report of Zhou et. al [22] that proves a similar result. Like our proof, their strategy adapts that of [8] to a more general setting. However, our underlying methodology is quite distinct: we use a homotopy based argument, while they use a geometric one. Furthermore, we devote more attention to the boundary of our region. In particular, we use analytic curves (rather than smooth curves) to avoid potential pathologies of geodesics. We provide more detail on finding guardable paths: we explain how to restrict ourselves to finding geodesics in closed sets, rather than in sets that are neither open nor closed (see Lemma 3.6 below). Finally, they use an endgame that requires two aggressive pursuers. We stick with lion's strategy due to its broad applicability to cat(0) spaces.
1.1 Related Work
Pursuit-evasion games are a class of adversarial motion planning problems. Chung, Hollinger and Isler [11] provide an informative survey of pursuit games in mobile robotics. The interdisciplinary literature on pursuit-evasion games spans a range of settings and variations. Pursuit games have been studied in many environments, including graphs, in polygonal environments and in geometric spaces. Researchers have considered motion constraints such as speed differentials between the players, constraints on acceleration, and energy budgets. As for sensing models, the players may have full information about the positions of other players, or they may have incomplete or imperfect information. Typically, the capture condition requires achieving colocation, a proximity threshold, or sensory visibility (such as a non-obstructed view of the evader).
Pursuit games enjoy a wide range of applications, including intruder neutralization, search-and-rescue, and environmental monitoring of tagged wildlife. In these settings, modeling an adversarial evader gives worst-case feasibility and time bounds. For an overview of pursuit-evasion on graphs, see the monograph by Bonato and Nowakowski [9]. Kopparty and Ravishankar [16] give a nice an introduction to pursuit in the polygonal setting.
Research on pursuit-evasion spans nearly a century. In the 1930s, Rado posed the Lion and Man game in which a lion hunts the man in a circular arena. The players move with equal speeds, and the lion wins if it achieves colocation. At first blush, it seems that lion should be able to capture man, regardless of the man's evasive strategy. However,
190
Ars Math. Contemp. 13 (2017) 107-123
Besicovitch showed that when the game is played in continuous time, the man can follow a spiraling path so that lion can get arbitrarily close, but cannot achieve colocation [17]. However, when lion and man move in discrete time steps, our intuition prevails: lion does have a winning strategy [21].
The past decade has witnessed a renaissance of pursuit-evasion results in multiple disciplines. Prominent research efforts come from the robotics community, where pursuitevasion in polygonal environments is a productive setting for exploring autonomous agents. Pursuit-evasion has also thrived in the graph theory community, where it is known as the game of Cops and Robbers. More recently, researchers have started exploring pursuitevasion games in topological spaces. This is a natural evolution for the study of pursuitevasion games. Indeed, determining the number of pursuers required to capture an evader in a given environment becomes a question about its topology since the various loops and holes of the environment provide escape routes for the evader.
The classic paper of Aigner and Fromme [1] initiated the study of multiple pursuers versus a single evader on a graph. In this turn-based game, agents can move to adjacent vertices, and the cops win if one of them becomes colocated with the robber. This paper introduced the cop number of a graph, which is the minimum number of pursuers (cops) needed to catch the evader (robber). Aigner and Fromme proved that the cop number of any planar graph is at most 3. This bound is tight, as the dodecahedron graph requires three cops. At a high level, their winning pursuer strategy proceeds as follows. Two cops guard distinct (u, v)-paths where u, v are vertices of the graph G. This restricts the robber movement to a subgraph of G. The third pursuer then guards another (u, v)-path, chosen so that (1) the robber's movement is further restricted, and (2) one of the other cops no longer needs to guard its path. This frees up that cop to continue the pursuit. This process repeats until the evader is caught.
More recently, an analogous result was proven by Bhadauria, Klein, Isler and Suri [8] for pursuit-evasion games in a two-dimensional polygonal environment with polygonal holes. In this turn-based game, an agent can move to any point within unit distance of its current location. Like Aigner and Fromme, they use colocation as their capture criterion. Bhadauria et al. prove that three pursuers are sufficient for pursuit-evasion in this setting, and that this bound is tight. The pursuer strategy is inspired by the Aigner and Fromme strategy for planar graphs: two pursuers guard paths that confine the evader while the third pursuer takes control of another path that further restricts the evader's movement. Of course, the details of the pursuit and the technical proofs are quite different from the graph case. Their proofs make heavy use of the polygonal nature of the environment, both to find the paths to guard and to guarantee that their pursuit finishes in finite time.
Just as the proofs of Bhadauria et al. were inspired by Aigner and Fromme, our proof of Theorem 1.2 is inspired by those for the polygonal environment. Bhadauria et al. actually give two different winning strategies for three pursuers. At a high level, these strategies progress in the same way, but the tactics for choosing paths and how to guard them are different. Herein, we adapt their shortest path strategy to our setting. Our more general geometric environment introduces a distinctive set of challenges to overcome. In particular, we do not have a finite set of polygonal vertices to use as a backbone for our guarded paths. Instead, we rely on homotopy classes to differentiate between paths to guard. Looking beyond the high-level structure of our pursuer strategy, the arguments (and their technical details) in this paper are wholly distinct from those found in [8], and our result applies to a much broader class of environments.
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
191
Finally, we note that our result follows in the footsteps of other recent explorations of pursuit-evasion games in general geometric and topological domains. Pursuit-evasion games in such spaces have further applications in robotics, where agents must navigate and coordinate in high dimensional configuration spaces. Alexander, Bishop and Ghrist helped to pioneer this subject, studying pursuit-evasion games with the capture condition e) < e for some constant e > 0 (rather that colocation). In [3], Alexander, Bishop and Ghrist prove that a single pursuer can capture an evader in any compact cat(0) space: the simple pursuit strategy of heading directly towards the evader is a winning strategy. In [5], these authors explore the simple pursuit strategy in unbounded cat(K) spaces with positive curvature K > 0, developing connections between evader-win environments and the total curvature of the pursuer's trajectory. Finally, in [4], they consider pursuit games in unbounded Euclidean domains using multiple pursuers. They provide conditions on the initial configuration of the players that guarantee capture, generalizing (and amending) results of Sgall [21] and Kopparty and Ravishankar [16].
1.2 Preliminaries
We introduce some notation and review some concepts and results from algebraic topology [13]. We then prove three lemmas about convex paths in two-dimensional compact regions with piecewise analytic boundary.
A topological space is a set X along with a collection of subsets of X, called open sets that satisfy a sequence of axioms [7]. A map f : X ^ Y between two spaces is continuous when the inverse image of every open set in Y is open in X. A path n : [0,1] ^ D is a continuous map from the interval [0,1] to D, with initial point n(0) and terminal point n(1). The length l(n) of this path is its arc length in Euclidean space E2. A path n is a loop when n(0) = n(1). A simple path has no self-intersections, meaning that n is injective. By abusing notation, we write x e n when x = n(t) for some t e [0,1]. For x, y G n, we use n(x, y) to denote the subpath connecting these points. The space X is path-connected if there exists a path between any pair of points x, y e X.
A homotopy of paths is a family of maps ft : [0,1] ^ X, t e [0,1], such that the associated map F : [0,1] x [0,1] ^ X given by F(s, t) = ft(s) is continuous, and the endpoints ft(0) = x0 and ft(1) = xi are independent of t. The paths f0 and f are called homotopic. The relation of homotopy on paths with fixed endpoints is an equivalence relation and we use [f ] to denote the homotopy class of the curve f under this relation. The set [f] of loops in X at the basepoint x0 forms a group under path composition, called the fundamental group of X at the basepoint x0. The space X is simply connected when it is path-connected and its fundamental group is trivial. For example, a subspace X of E2 is simply connected if and only if it has the same homotopy type as a 2-disc.
We now turn to some geometric properties of paths in E2. The distance d(x, y) between points x, y e X is the length of a shortest (x, y)-path in X. When restricting ourselves to R C X, we use dR (x, y) to denote the distance between these points in the subdomain. We will frequently consider a subdomain R enclosed by two simple (u, v)-paths n1, n2. We denote such a set as R[n1, n2] C X.
Fora C2 path 7 : [0,T] ^ E2, its curvature at Y(t) is defined as «(t) = ± IIy'^^'Wl^11, with the sign positive if the tangent turns counterclockwise, and negative if the tangent turns clockwise. The smoothness of a piecewise analytic curve 7 : [0,1] ^ E2 ensures that its absolute curvature is bounded at its nonsingular points. If 7 is piecewise C2 and
192
Ars Math. Contemp. 13 (2017) 107-123
u
u
(a)
(b)
Figure 1: (a) A piecewise convex (u, v)-path n. (b) Shortcutting a non-convex (u, v)-path
ni.
continuous, with t0 < t1 < • • • < tn as the preimages of the singular points, then its total curvature is
where Qi is the exterior angle at 7^), and Qn = 0 when 7(t0) = 7(tn). This brings us to the celebrated Gauss-Bonnet Theorem which relates the total curvature of a closed curve with the Euler characteristic of its enclosed region. In our setting, the Euler characteristic equals 1 - k, where k is the number of obstacles in the region R.
Theorem 1.3. [Gauss-Bonnet Theorem, cf. [12]] Given a compact region R C E2 with boundary dR, we have
«total (dR) =2nx(R), where x(R) is the Euler characteristic of R.
We use the Gauss-Bonnet Theorem to understand the effect of obstacles on shortest paths. In particular, we will consider pairs of paths n1, n2 with shared endpoints u, v. These paths will be piecewise analytic (so that they have a finite number of singular points). Our goal is to prove that if the shortest (u, v)-path is not unique, then each shortest path must touch an obstacle in the given region. We begin with a definition of convexity, which we define for the broader family of piecewise C2 smooth curves; an example is shown in Figure 1(a).
Definition 1.4. Let n : [0,1] ^ E2 be a piecewise C2 smooth curve in E2. Then n is convex when the following holds for any point x e n\{u, v}:
(a)	If n is C2 smooth at x, then the curvature at x is nonpositive;
(b)	If n is not C2 smooth at x, then the tangent line at x turns clockwise by an angle
0 < Q < n.
The definition for a concave curve is similar, but the curvature must be nonnegative and the tangent line must turn counterclockwise. Note that if the (u, v)-curve n is convex, then the (v, u)-curve r given by r(t) = n(1 -1) is concave.
Lemma 1.5. Let n1 and n2 be two piecewise analytic (u, v)-paths with n1 n n2 = {u, v} and such that R[n1, n2] lies to the left of n1. If the curve n1 is a shortest (u, v)-path in R[n1, n2] and touches no obstacle inside R[n1, n2], then n1 is convex in R[n1, n2].
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
193
Note that the curve ni does not to need to be a straight line: see Figure 1(a) for an example. Similar convex bounding curves will arise as the pursuers remove obstacles from the evader's reach.
Proof. We prove the lemma by contradiction. Suppose that there exists an x G n\{u, v} where the convexity of n1 in R[n1, n2] is violated. Either (a) n1 is C2 smooth at x, but the curvature at x is positive, or (b) n1 is not C2 smooth at x, and the tangent line turns counterclockwise by an angle 0 < 0 < n at x, creating a non-convex corner. Let d0 denote the minimum distance between n1 and any obstacle O G R[n1, n2] with n1 n dO = 0.
Suppose that the curvature at x is positive, see Figure 1(b). There must be a C2 subpath nx between y 1 and y2 of n1 around x with positive curvature. Using the lower bound d0 on the separation between n1 and any obstacles inside R[n1, n2] and n2, we may take y1, y2 to be close enough so that the line segment A connecting y1 and y2 lies inside R[n1, n2] and does not encounter any obstacles. Replacing nx with A creates a path that is strictly shorter than n1, contradicting the minimality of n1.
Next suppose there is a non-convex corner at x. By an analogous argument to the previous case, we can create a short-cut A around x to make a shorter path than n1, a contradiction.	□
Lemma 1.6. Let n1, n2 be two (u, v)-paths with n1 n n2 = {u, v}. Suppose that n1 is a convex and piecewise analytic (u, v)-path in R[n1, n2], and let n2 be a convex and piece-wise analytic (v, u)-path in R[n1, n2]. Then n1 and n2 are both straight lines connecting
u, v.
Proof. Let Q = Q[n1, n2] be the simply connected, closed region between n1 and n2 (so we ignore all obstacles in D). The concatenation of n1(u, v) and n2(v, u) is a loop dQ bounding the simply connected region Q. By the Gauss-Bonnet Theorem 1.3, the total curvature along dQ equals 2nx(Q) = 2n. We decompose the total curvature of dQ as the sum of total curvature of n1 and n2 respectively, and the exterior angles at u and v. Because of convexity, both n1 and n2 have total curvature no greater than 0. As for the two angles at u, v, neither can exceed n. Therefore the total curvature of the loop does not exceed 2n, and could only achieve 2n when «total(n1) = Ktotal(n2) = 0. Therefore, n1 and n2 are both straight lines connecting u and v.	□
Lemma 1.7. Suppose n1, n2 are two shortest (u, v)-paths in the region R = R[n1, n2], with n1 n n2 = {u, v}. Then each of n1, n2 touches at least one obstacle in R.
Proof. Suppose that the conclusion is false. Without loss of generality, n1 does not touch any obstacles in R. By Lemma 1.5, the (u, v)-path n1 is convex in R. Let Q be the simply connected region obtained by removing the obstacles in R. We have 1(n1) = 1(n2), so they are both shortest (u, v)-paths in the simply connected environment Q. Therefore n2 is also convex by Lemma 1.5, if parameterized as a path from v to u. By Lemma 1.6, n1 and n2 are both straight lines connecting u, v, which contradicts n1 n n2 = {u, v}. This proves that when there is more than one shortest (u, v)-path, each of these paths must touch an obstacle inside R.	□
This concludes our topological and geometric preliminaries.
194	Ars Math. Contemp. 13 (2017) 107-123
c
•'
P
e
1
Figure 2: Lion's strategy in E2. On each move, the pursuer moves on the line segment connecting the center c to the evader, and increases her distance from c.
2 Lion's Strategy in a cat(0) space
In this section, we describe a winning strategy for a single pursuer in a compact cat(0) domain, and prove Theorem 1.1. Our strategy generalizes lion's strategy for pursuit in E2, introduced by Sgall [21]. This strategy was adapted for pursuit in polygonal regions by Isler, Kannan and Khanna [14]. Their adaptation relies heavily on the vertices of the polygon P and gives a capture time of n • diam(P)2, where n is the number of vertices of P. We give a version of lion's strategy that succeeds in any compact CAT(0) domain D (including polygons) with capture time bounded by diam(D)2.
Sgall's version of lion's strategy proceeds as follows. Fix a point c as the center of our pursuit, see Figure 2. The pursuer starts at p = c and the evader starts at some point e. On her first move, the pursuer moves directly towards e along the line ce. Considering a general round, the pursuer will be on the line segment between c and e prior to the evader move. After the evader moves to e' G B(e, 1), the pursuer looks at the circle centered at p with radius e. If e is inside this circle, then the pursuer can capture the evader. Otherwise, this circle intersects the line segment ce' at two points. The pursuer moves to the point p' that is closer to e.
Lemma 2.1 (Sgall [21]). A pursuer using lion's strategy in E2 re-establishes her location on the line segment between c and the evader. Furthermore, if the evader moves from e to e' andthe pursuer moves from p to p' then d(c,p')2 > d(c,p)2 + 1.
Before generalizing lion's strategy, we introduce of the basics of a cat(0) geometry; see [10] for a thorough treatment. A complete metric space (X, d) is a geodesic space when there is a unique path n(x, y) whose length is the metric distance d(x,y). This path n(x, y) is called a geodesic (or shortest path). A triangle Axyz between three points x, y, z G X is the triple of geodesics n(x, y), n(y, z), n(z, x). To each Axyz G X, we associate a comparison triangle Axyz c E2 whose side lengths in E2 are the same as the lengths of the corresponding geodesics in X. The complete geodesic metric space (X, d) is cat(0) when no triangle in X has a geodesic chord that is longer than the corresponding chord in the comparison triangle. In other words, pick any triangle Axyz and any points u G n(x, y) and v G n(y, z). Let U G xy and V G yz be the corresponding points, chosen distancewise on the edges xy and yz. If the space X is cat(0) then dx (u, v) < dg2 (U, V). Colloquially, this is called the "no fat triangles" property, since it also implies that the sum of the angles of the triangle is not greater than n.
Our cat(0) lion's strategy generalizes the extended lion's strategy for polygons of Isler et al. [14]. The pursuer starts at a fixed center point c and her goal is to stay on the shortest path n(c, e) at all times. In particular, assume that pt is on the shortest path n(c, et) and
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
195
that the evader moves from et to et+i. If d(pt, et+i) < 1 then the purser responds by capturing the evader. Otherwise, the pursuer draws the unit circle C centered at pt and moves to the point in C n n(c, et+1) that is closest to et+1.
Lemma 2.2 (Lion's Strategy). A pursuer using lion's strategy in a cat(0) space (X, d) reestablishes her location on the line segment between c and the evader. Furthermore, if the evader moves from e to e' and the pursuer moves from p to p' then d(c,p')2 > d(c,p)2 + 1.
Proof. Suppose that p G n(c, e) and then the evader moves to e'. Consider the cat(0) triangle Acee' and its comparison triangle Acee' in E2. Look at the corresponding E2 pursuit-evasion game with the pursuer at p G ce. By Lemma 2.1, the pursuer can move to apointp' G ce' such that dE2(c,pC')2 > dE2(c,pe)2 + 1. Since there are no fat triangles in X, we have dX(p, p') < dE2 (p,p') where p' G n(c, e') is the point corresponding to p'. Therefore, in our original game, the pursuer can move to the point p' G n(c, e'), which satisfies dX(c,p')2 > dX(c,p)2 + 1.	□
Finally, we prove Theorem 1.1: lion's strategy succeeds in a cat(0) domain.
Proof of Theorem 1.1. Consider a pursuit-evasion game in the compact cat(0) domain D. Pick any c G dD as our center point. Using lion's strategy, the pursuer increases her distance from c with every step by Lemma 2.2, so she captures the evader after at most diam(D)2 rounds.	□
3 Minimal Paths and Guarding
The key to our pursuit strategy is the ability of one pursuer to guard a shortest path, meaning that the evader cannot cross this path without being caught by a pursuer. When this shortest path splits the domain into two subdomains, the evader will be trapped in a smaller region. We refer to this region as the evader territory. In fact, we will be able to also guard a "second shortest path" when the shortest path is already guarded. The definitions and lemmas in this section are adaptations of the minimal path formulations introduced in [8] and further developed in [6]. Recall that we use d(x, y) to denote the length of a shortest (x, y)-path in D. In addition, we will use X and X to denote the interior and the closure of a set X, respectively.
Definition 3.1. Let X c D be a path-connected region. The simple path n c X is
minimal in X when for any y 1, y2 G n and any z G X, we have dn (y1, y2) < dX (y1, z) + dx (z,y2).
Definition 3.2. Let Z c X and let n be a minimal (u, v)-path in Z where u, v G dZ. Then the path projection with anchor u is the function n : Z ^ n defined as follows. If
dZ(u, z) < dZ(u, v) = dn(u, v), then n(z) is the unique point x G n with dn(u,x) = dZ(u, z). For the remaining z G Z\n, we set n(z) = v.
We make a few observations. If X = D, then a shortest (x, y)-path is always a minimal path in D. In this case, we can define the path projection n : D ^ n. When X C D, we might have dX (x1, x2) > d(x1, x2). In this case, a shortest path in X will be minimal in X, but it will not be minimal in D. Next, we show that a path projection is non-expansive, meaning that distances cannot increase.
196
Ars Math. Contemp. 13 (2017) 107-123
Lemma 3.3. Let n : Z ^ n be a path projection onto a minimal path in Z. Then
dn(n(zi),n(z2)) < dz(zi, z2) for all z\,z2 G Z.
Proof. The proof is a straight-forward argument using the triangle inequality. We consider the case zi, z2 G Z with d(u, zi) < d(u, z2) < d(u, v). We have
dz(z2,zi) > dz(z2,u) — dz(zi,u) = dn(n(z2),u) — dn(n(zi),u) = dn(n(z2 ),n(zi)).
The other non-trivial cases are argued similarly.	□
A single pursuer can turn a minimal path n into an impassable boundary: once the pursuer has attained the position p = n(e), the evader cannot cross n without being captured in response. The proof of the following lemma is similar to the analogous result in [6], but we include this brief argument for completeness.
Lemma 3.4 (Guarding Lemma). Let n : X ^ n be a path projection onto the minimal (u, v)-path n c X. Consider a pursuit-evasion game between pursuer p and evader e in the environment X.
(a)	After O(diam(X)) turns, the pursuer can attain pt = n(et-i).
(b)	Thereafter, the pursuer can re-establish ps+i = n(es) for all s > t.
(c)	If the evader moves so that a shortest path from es-i to es intersects n, then the pursuer can capture the evader at time s + 1.
Proof. To achieve (a), the pursuer moves as follows. First, p travels to u, reaching this point in O(diam(X)) turns. Next, p traverses along n until first achieving d(u,pl) < d(u,n(ei-i)) < d(u,pl) + 1. If pl = n(ei-i) then we are done. Otherwise, when the evader moves, we either have d(u,p%) — 1 < d(u,n(ei)) < d(u,pi) + 1 or d(u,pi) + 1 < d(u, n(ei)) < d(u,pl) + 2 by Lemma 3.3. In the former case, p can move to n(el) in response, achieving her goal. In the latter case, p will increase her distance from u by one unit, re-establishing d(u,pi+i) < d(u,n(ei)) < d(u,pi+i) + 1. This latter evader move can only be made O(diam(X)) times, after which the pursuer acheives p = n(e).
Next, suppose thatps = n(es-i) and that es-i G X\n. The pursuer can stay on the evader projection by induction since
dn(ps,n(es)) = dn(n(es-i),n(es)) < d(es-i,es) < 1,
so (b) holds. As for (c), suppose that a shortest path from es-i to es includes the point y G n. Then
d(ps, es) < dn(n(es-i), y) + d(y, es) < d(es-i,y) + d(y, es) = d(es-i,es) = 1. Therefore the pursuer can capture the evader on her next move.	□
The Guarding Lemma is the cornerstone of our pursuer strategy. When the pursuer moves as specified in the lemma, we say that she guards the path n. In Section 4, our pursuers will repeatedly guard paths chosen to reduce the number of obstacles in the evader territory. Once the evader is trapped in a region that is obstacle-free, we have reached the endgame of the pursuit.
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
197
Lemma 3.5. Suppose that the evader is located in a simply connected region R whose boundary consists of subcurves of the original boundary dD and two guarded paths ni and n2. If the evader remains in R, then the third pursuer can capture him infinite time. If the evader tries to leave the region through ni or n2, then he will be captured by the guarding pursuer.
Proof. By Lemma 3.4, if the evader tries to leave this region, he will be caught by either pi or p2. If the evader remains in this component, then Theorem 1.1 guarantees that pursuer p3 captures the evader in a finite number of moves.	□
The remainder of this section is devoted to identifying guardable paths that touch obstacles. Guarding such a path will neutralize the threat posed by the obstacle. First, we consider the case when pi guards the unique shortest (u, v)-path ni that touches an obstacle O in the evader region. The objective of p2 is to guard another (u, v)-path n2 of a different homotopy type. This path can be guarded even when n2 is longer than ni, provided that any path shorter than n2 also intersects ni.
Lemma 3.6. Suppose that the evader territory R = R[ni, A] is bounded by the unique (u,v)-shortest path ni and another boundary curve A. Furthermore, suppose that ni touches an obstacle O and that ni is guarded by pi. Then we can find a (u, v)-path n2 c R with the following properties: (a) O c R[ni, n2], so that the homotopy type of n2 is different than that of ni; and (b) n2 is guardable by p2, provided that ni remains guarded by pi .
A naive attempt to find such a path is to pick some x e ni n O and find a shortest path that does not include the point x. However, R\{x} is not a closed set, which would complicate our argument. Furthermore, it could be that the next shortest path includes x without using this point as a shortcut around the obstacle O, as shown in Figure 3(b).1 We handle both problems by removing a small and well-chosen open region A near x, rather than removing the point x. The delicate choice of A relies on two consequences of our piecewise analytic boundary: the finite upper bound Kmax > 0 on the curvature and the minimum distance dmin > 0 between boundary components.
Proof. First, suppose that ni n dO includes a continuous subcurve C c ni. Pick x e C7 and e > 0 so that B(x, e) n R c O. Let R' — R\B(x, e), which effectively absorbs the obstacle into the boundary, see Figure 3 (a). The region R' is closed, so there is a well-defined shortest (u, v)-path n2 c R'. The path n2 is guardable in R', and therefore it is guardable by p2 in R, provided that pi guards ni. Indeed, any shorter path in R must go through the point x, so Lemma 3.4 guarantees that an evader using such a path will be caught by pi. Finally, we note that ni, n2 have distinct homotopy types because
o c R[ni, n2].
Next, we consider the case where ni n O contains no continuous curves: we just focus on the first point x e ni n O encountered as we move from u to v. Locally around x, the path ni and the boundary dO separate R into two external regions (outside of n and inside dO) and two internal regions, see Figure 3 (b). The shortest path ni does not self-intersect, so locally near x, this path consists of two curves meeting at x, creating an
1We note that this unusual circumstance is overlooked in [8], where it can occur during their minimal path strategy. This case can be easily handled in a manner analogous to our approach, but based on the visibility graph of their environment.
198
Ars Math. Contemp. 13 (2017) 187-206
O
ni
v
(a)
A
A
n^ ¿p (b)
(c)
A
vA
(d)
Figure 3: Finding the second shortest path. (a) When n1 n dO contains a curve, we can remove a small open ball. (b) The shortest path n1 touches obstacle O at x. The second shortest path n2 goes around O, but includes the point x. (c) Finding n2 requires removing a small, open, triangular set A between n1 and O, and then finding the shortest (u, v)-path in the closed set R\A. (d) Any path that crosses the line segment yz can be short-cut.
x
u
u
v
interior angle smaller than 2n. Therefore, at least one of the two interior angles made by n1 and the obstacle tangent line(s) at x is strictly less than n. This local region is where we will remove our triangular open set.
Without loss of generality, suppose that the subpath n1(x, v) helps to bound this local region. Take points y G n1(x, v) and z G dO (traveling counterclockwise from x) such that 0 < dni (x, y) = ddO (x, z) < dmin/2, and the angle Zyxz < n. Let A c B(x, dmin) be the closed region with endpoints (x, y, z), where the third curve is the unique shortest (y, z)-path r, see Figure 3 (c). The bound on the absolute curvature Kmax allows us to choose our y, z so that the region A is essentially triangular. Since dmin is the minimum distance between obstacles, A is obstacle-free, so r is a straight line segment.
We remove the relatively open set A' = A\r from our domain. We then find the shortest (u, v)-path n2 in the closed set R = R\A'. We claim that p2 can guard n2 in R, provided that p1 guards n1. As in the previous case, the shorter paths that go through x are not available to the evader. Therefore, we must show that any path in R that visits A' is longer than n2. Such a path A must enter and leave A' through r, say at points a, b, see Figure 3 (d). However, the subpath A(a, b) can be replaced with the unique shortest path r(a, b) without changing the homotopy type, a contradiction. Once again, n1, n2 have distinct homotopy types because O c R[n1, n2].	□
We refer to the paths n1, n2 from Lemma 3.6 as a guardable pair. Provided that the shortest (u, v)-path n1 is guarded, the "second shortest (u, v)-path" n2 can also be guarded. The following corollary is a variation of the lemma.
Corollary 3.7. Let n1, n2 be (u, v)-paths that are guarded by p1,p2, respectively. Suppose that for i = 1, 2, the path n touches an obstacle Oit where O1 = O2. Then we can find a path n3 with the following properties: (a) the homotopy type of n3 is different than the homotopy types of n1 and n2, and in particular, Oj G Rpj, n3] for i = 1,2; and (b) n3 is guardable by p3, provided that n1, n2 remain guarded by p1, p2.
Proof. The proof is similar to the proof of Lemma 3.6. This time, we must remove an open set A near x g n1 n O1 and an open set B' near y G n2 n O2. We then find n3 in
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
199
R\(A' U B').	□
This concludes our search for guardable paths that touch obstacles. The next section lays out the three-pursuer strategy for capturing the evader in a two-dimensional domain.
4 Shortest Path Strategy
In this section, we prove Theorem 1.2: three pursuers can capture an evader in a two-dimensional compact domain with piecewise analytic boundary. We adapt the the shortest path strategy of Bhaudaria et al. [8] to our more general setting. In particular, our guard-able path lemmas from Section 3 supplant their use of polygon vertices to find successive paths. Their algorithm guarantees success by reducing the number of polygon vertices in the evader territory. Instead, we keep track of the threat level of obstacles to argue that the evader becomes trapped in a simply connected region.
Our pursuit proceeds in rounds. At the start of a round, at most two pursuers guard paths. The third pursuer moves to guard another path with the goal of eliminating obstacles from the evader territory. This third path will either be a shortest path, or it will create a guardable pair with the currently guarded path(s). Once this third path is guarded, the evader is trapped in a smaller region, which releases one of the other pursuers to continue the process. This continues until the evader is trapped in a simply connected region, where the free pursuer can capture the evader by Lemma 3.5.
We start by showing that the boundary of the evader territory is always piecewise analytic, after recalling two definitions. First, the endpoints of a line segment touching the boundary dV are called switch points. Second, a point x is an accumulation point (or limit point) of a set S when any open set containing x contains an infinite number of elements in S. We make use of the following result about the interaction of a geodesic with the boundary of the domain.
Theorem 4.1 (Albrecht and Berg [2]). If M is a 2-dimensional analytic manifold with boundary embedded in E2, and y is a geodesic in M, then the switch points on y have no accumulation points.
We restrict ourselves to analytic boundary, instead of smooth (C2, or even Cbound-ary, to avoid some potentially pathological behavior of geodesics. For example, Albrecht and Berg [2] construct a geodesic in Cenvironment, that achieves a Cantor set of positive measure as the accumulation of switch points. This unusual geometry hampers our ability to confine the evader in a well-defined connected component. Theorem 4.1 ensures that our new evader territory will be bounded by piecewise analytic curves.
Lemma 4.2. Let V be a compact domain with piecewise analytic boundary. If n is a shortest path in V, then n is piecewise analytic. Furthermore, if V\n is disconnected, then it contains finitely many connected components, and the boundary of each connected component is piecewise analytic.
Proof. Let B c d(n\dV) be the set of switch points. We claim that B is finite. Otherwise, there must be an accumulation point of B since l(n) is finite, contradicting Theorem 4.1. Now we can use the finite set B as endpoints to partition n so that each subcurve is either in the boundary dV, or in the interior V. Since any shortest path in the interior V must be a line segment, the path n is piecewise analytic. For each connected component of V\n, its boundary is a subset of n U dV, hence is piecewise analytic.	□
200
Ars Math. Contemp. 13 (2017) 107-123
In order to prove Theorem 1.2, we will show that our pursuit succeeds in finite time. To aid in this effort, we assign a threat level to each of the k obstacles in the original domain. These threat levels will reliably decrease during pursuit. An obstacle is in one of three states: dangerous, safe, or removed. A removed obstacle lies outside the evader territory. A safe obstacle lies in the evader territory and touches a currently guarded path. This obstacle is not a threat because the evader cannot circle around the object without being captured. The remaining obstacles are dangerous. Finally, we say that the evader territory is dangerous if it contains at least one dangerous obstacle.
At the start of pursuit, all obstacles are dangerous. So long as there are still dangerous obstacles, a round consists of taking control of a guardable path. This effort succeeds in a finite number of moves by Lemma 3.4. We will show that after at most two rounds, either a dangerous obstacle transitions to safe/removed, or a safe obstacle transitions to removed. This is our notion of progress: after at most 2k rounds, the evader territory is not dangerous. From here forward, we focus on the transition of the threat levels of obstacles.
In general, our evader territory will be bounded by part of the domain boundary dD and by at most two guarded paths ni, n2. At the end of a round, the evader territory will be updated, bounded in part by updated paths ni, n2. If these guarded paths intersect or share subpaths, then the evader is actually trapped in a smaller region by Lemma 3.4. When this is the case, we advance the endpoint(s) of our paths so that these are the only point(s) shared by our paths. This obviates the need to discuss degenerate cases.
The first round is an initialization round, so all obstacles might still be dangerous when this round completes. However, we will be able to neutralize at least one obstacle in the subsequent round. To kick off the first round, we pick points u, v e dD, chosen so that they divide the outer boundary into two curves A1, A2 of equal length, see Figure 4(a). Let n1 be a shortest (u, v)-path; if there are multiple shortest paths (in which case each touches an obstacle), then we pick one arbitrarily. Using Lemma 3.4, p1 moves to guard n1. The round ends when p1 has attained guarding position, trapping the evader in a subdomain that is bounded by n1 and one of A1, A2. The evader could be trapped in a smaller pocket region between n1 and a subcurve A3 of an obstacle O C D, see Figure 4(b). In the latter case, the obstacle O is marked as removed and we treat A3 as the new outer boundary. After updating the evader territory R, any obstacle O C R is marked as removed. Any obstacle O C R that touches n1 or n2 is marked as safe.
For the remainder of the game, the evader territory is one of the following types.
•	Type 0 region: A region containing no dangerous obstacles.
•	Type 1 region: A dangerous three-sided region bounded by a (u, v)-shortest path n1, a (u, w)-shortest path n2 and a (v, w)-path A C dD. No obstacle touches both
ni, n2.
•	Type 1' region: A dangerous two-sided region bounded by a (u, v)-shortest path n1 and a (u, v)-path A C dD. We treat this as a special case of the previous type, where n2 consists of the single point w = u. This point is on n1, so it is guarded by p1.
•	Type 2 region: A dangerous two-sided region bounded by (u, v)-paths n1, n2, each of which touches an obstacle in the evader territory. The path n1 is a shortest (u, v)-path in this region. The path n2 might also be a shortest (u, v)-path, or it could be a "second shortest path," meaning that it is a shortest (u, v)-path among the set of (u, v)-paths that are not homotopic to n1. No obstacle touches both n1, n2.
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
201
Ai
Ai
A2 (a)
nr-
I Q A3
A2 (b)
Figure 4: The shortest (u, v)-path n i guarded in round one. (a) The path n i partitions the outer boundary to subcurves A i, A2 of equal length. (b) The evader may be trapped in a pocket between the path n i and the boundary subcurve A3 of obstacle O.
u
u
v
• Type 3 region: a dangerous 4-sided region bounded by a (u, v)-shortest path n i, a (w, x)-shortest path n2, a (v, w)-path A i from the boundary and a (u, x)-path A2 from the boundary. These vertices are arranged so that they are ordered clockwise as u, v, w, x. No obstacle touches both n i, n2.
For example, after the initialization round, the evader territory is a type 1' region, bounded by a guarded path and part of the boundary dD. Finally, we emphasize that Lemma 4.2 ensures that the boundary of the evader region is always piecewise analytic, since it consists of sub-curves of the piecewise analytic boundary along with one or more shortest paths.
We now describe the different types of rounds. In regions of type 1, 1' and 2, we will always transition at least one obstacle. At the end of such a round, the evader could now be trapped in a region of any type. Type 3 rounds are slightly different. Our primary goal is to trap the evader in a type 1 region, where we will surely make progress in the subsequent round. However, it is possible to transition an object via a type 3 move (just as in the initialization round). In this case, we make immediate progress, and the evader could then be trapped in a region of any type.
First we consider type 1 regions. This also handles type 1' regions as a special case. We use the following lemma to identify a point x G A and a shortest (u, x)-path to guard during this round.
Lemma 4.3. Let shortest paths n0(u, v), n i(u, w) and boundary path A(v, w) bound a type 1 environment R. If R contains obstacles, then there exists a point x G A such that there are multiple shortest (u, x)-paths in R each of which touches at least one obstacle.
Proof. Parameterize the boundary path as A : [0,1] ^ R. We prove the lemma by contradiction.
Suppose that for every t G [0,1], the shortest (u, A(t))-path nt is unique. Denote its length by 1(nt) = d(u, A(t)). Define the function n(t) to be the number of obstacles in the region Rt bounded by n0, nt and A. The function n(t) is well-defined by the uniqueness of each nt. Furthermore, n(0) = 0, and n(1) > 0, so there must be a jump discontinuity somewhere in [0,1]. Let s = inf{t G [0,1] : n(t) > 0}.
Case 1: n(s) > 0 where 0 < s < 1. (Recall that n(0) = 0, so s > 0.) Let r be a shortest (u, A(s))-path that is of the same homotopy class as n0. The choice of s and
202
Ars Math. Contemp. 13 (2017) 107-123
u A v	u \ / 1K
T-r V \ o n2 / \ / \	y & t {
x w	v x
(a)	(b)
u K
u
A
/ »
no
ni
nil*
^2
u
,1 ^ Al'
n^ \n2

w v x
(c)
w v = x w v x	w
(d)	(e)
3
v
Figure 5: Representative examples of a type 1 move, where we transition to (a) a type 1 region, (b) a type 1 or type 1' region, (c) a type 1 or a type 3 region, (d) a type 1 or type 2 region, (e) a type 1 or type 3 region.
the uniqueness of ns guarantee that l(T) > /(ns). Also no obstacles are contained in the region bounded by n0, r and A(0, s). By the definition of r, for all t G [0, s), we have ¿(r) < ¿(rt) + ¿(A(t, s)). By the continuity of 1(nt) = d(u, A(t)) with respect to t G [0, s), we have /(r) < /(nt) + /(A(t, s)), so
/(r) < lim (z(no + i(A(t, s))) = i(ns) + o = i(ns).
t—s-
This contradicts /(r) > /(ns), so ns is not the unique shortest (u, A(s))-path.
Case 2: n(s) = 0, where 0 < s < 1. Let {s^} be an infinite sequence si ^ s+, such that n(sj) > 0 for all i. There are finite number of obstacles, so by taking a subsequence if necessary, we can assume that the shortest paths {ns.} are of the same homotopy class. Let r be the shortest (u, A(s))-path of this homotopy class. We have /(r) < /(nsi) + /(A(s, sj)) for all i, and therefore
/(r) < lim (i(nsi) + i(A(s,sj))) = /(ns),
i—^^o
where the limit holds by the continuity of distances in the region. However, this contradicts the uniqueness of ns which would require /(ns) < /(r).
Thus we can conclude that are multiple shortest (u, x)-paths. By Lemma 1.7, each of these paths touches at least one obstacle.	□
Having found the next path to guard, we now prove that we transition an object during a type 1 move.
Lemma 4.4. Suppose that the evader is trapped in a type 1 (or type 1') region. Then the third pursuer can guard a path that transitions an obstacle state.
Proof. By Lemma 4.3, there is some point x G A with multiple shortest (u, x)-paths, each of which touches an obstacle. Let n3 be one of these shortest (u, x)-paths. If x = v then we take a path n3 = ni. Similarly if x = w we choose n3 = n2. When x G {v, w}, we can choose n3 arbitrarily from the collection of (u, x)-shortest paths. Pursuer p3 moves to guard n3, which traps the evader in either R[n;, n3] or R[n3, n2]. Any obstacles in the other region are marked as removed.
Without loss of generality, let O c R[n;, n3] be an obstacle touched by n3, see Figure 5(a). Suppose that prior to p3 guarding n3, the object O was dangerous. If e G R[n3, n2]
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
203
then O transitions to removed. If e G Rpi, n3] then O transitions to safe. However, we may be in a more advantageous position, shown in Figure 5(b): the evader could be trapped in a pocket between obstacle O and path n3. In this case, the new evader territory is type 1' and the obstacle O is marked as removed, since it is now part of the outer boundary of the evader territory.
Next, suppose that O was already safe, touched by n1. If e G R[n2, n3] after p3 guards n3, then O transitions from safe to removed. If the evader is trapped in a pocket region between O and n3, we proceed as in the previous case. Otherwise, we have e G R[n1, n3] and the obstacle O separates R[n1, n3] into disjoint regions, as shown in Figure 5(c). The evader is trapped in one of these two subregions because both n1, n3 are guarded. Let A' be the subcurve of dO that bounds the effective evader territory. We update the evader territory appropriately, bounded by A' and subpaths of n1, n3, and perhaps part of A. The result is a region of type 1 or 3. The obstacle O is marked as removed: it is now part of the boundary. This reduces the number of safe obstacles.
When n3 touches multiple obstacles, each of them transitions to a lower threat level. Figures 5(d) and (e) show that we can also end up in a type 2 or 3 region, depending on the configuration of these obstacles and the location of the evader at the end of the round. □
Next, we consider a type 2 region. Such a region is bounded by (u, v)-paths n1, n2 that form a guardable pair, where n1, n2 touch safe obstacles O1, O2, respectively. Without loss of generality, n1 is a shortest (u, v)-path in the region, and n2 is either another shortest path, or a "second shortest path" as found in Lemma 3.6. (A type 1 move can lead to the first case. A type 2 move can lead to the second case, as we are about to see.)
Lemma 4.5. Suppose that the evader is trapped in a type 2 region. Then the third pursuer can guard a path that transitions an obstacle state.
Proof. Use Corollary 3.7 to find a guardable (u, v)-path n3 in R[n1, n2] whose homotopy type is distinct from that of both n1, n2. Pursuer p3 establishes a guarding position on n3. The evader is now trapped in either Rp1, n3] or Rp3, n2], so one of O1, O2 transitions from safe to removed. Furthermore, n3 must touch at least one obstacle in each of R[n1, n3] or R[n3, n2]. Otherwise, n3 would be shorter than one of n1, n2, which contradicts the minimality of that path in R[n1, n2]. Depending on the configuration of the obstacles, we may be able to restrict the evader territory further. After doing so, the evader territory may be of any possible type, as shown in Figure 6 (a).	□
This brings our discussion to a type 3 region, with p1 guarding a shortest (u, v)-path n1 and p2 guarding a shortest (w, x)-path n2. Our primary goal is to trap the evader in a type 1 region, but we might end up transitioning an obstacle instead. In the latter case, the new evader territory can be of any type, as explained below.
Lemma 4.6. Suppose that the evader is trapped in a type 3 region. Then the third pursuer can guard a path so that either (a) the evader is trapped in a type 1 region, or (b) an obstacle transitions to a lower threat level.
Proof. Let n3 be a (u, w)-minimal path. Pursuerp3 moves to guard this path using Lemma 3.4. This traps the evader in a smaller region: without loss of generality, this region is bounded by n1, A1, n3. If n3 does not touch any obstacles in this region, then the evader is now in a type 1 region. If n3 touches an obstacle O, then this obstacle transitions to
204
Ars Math. Contemp. 13 (2017) 107-123
Figure 6: Examples of moves where the new guarded path n3 divides the region into five subregions, each identified by its type. (a) A type 2 move. (b) A type 3 move.
either safe or removed. The evader could be trapped in a region of any type, as shown in Figure 6 (b).	□
We can now prove our main theorem: three pursuers can capture the evader in a two-dimensional compact domain with piecewise analytic boundary.
Proof of Theorem 1.2. The first round traps the evader in a type 1' region, or transitions an obstacle state. If we are in a region of type 1, 1' or 2 then we transition an obstacle state in the current round by Lemma 4.4 and Lemma 4.5. When we are in a type 3 region, Lemma 4.6 ensures that we either trap the evader in a type 1 region, or we transition an obstacle. With each path that we guard, the boundary of the updated evader territory is still piecewise analytic by Lemma 4.2. At the end of the round, we update the evader territory and our value for minimum obstacle separation since our new guarded path might be closer to an obstacle than the current value dmin. (Note that the maximum boundary curvature Kmax never increases since all additions to the boundary are line segments.)
After at most 2k rounds, we have transitioned all k obstacles to either safe or removed. Once all obstacles have been transitioned, the evader is trapped in a simply connected type 0 region. Lemma 3.5 shows that the evader will then be caught. Each round completes in finite time, so the three pursuers win the game. The capture time upper bound of O(2k • diam(D) + diam(D)2) follows easily. The time required to guard any shortest path is
diam(D) by Lemma 3.4 and lion's strategy completes in time diam(D)2 by Theorem 1.1.
□
5 Conclusion
In this paper, we described a winning pursuer strategy for a single pursuer in a cat(0) space for turn-based pursuit with capture criterion d(p, e) = 0. We then restricted our attention to compact domains in E2 with piecewise analytic boundary. We showed that three pursuers are sufficient to catch an evader in such environments. By adding a fourth pursuer for use in the final endgame, our strategy could be quickly adapted to a winning strategy in the continuous time version. However, a clever use of the two guarding pursuers during the endgame shows that three pursuers are actually sufficient: see [22] for details.
There are plenty of avenues for reseach in geometric pursuit-evasion. Pursuit-evasion results on polyhedral surfaces are an active area of current research [15, 18, 19]. For example, Klein and Suri [15] have proven that 4g + 4 pursuers have a winning strategy on a
A. Beveridge and Y Cai: Pursuit-evasion in a two-dimensional domain
205
polyhedral surface of genus g. Meanwhile, Schroder [20] has proven that at most |_3g/2j + 2 pursuers are needed for a graph of genus g (meaning that such a graph can be drawn on a surface of genus g without edge crossings). It would be natural to consider this question for topological surfaces, or to start by trying to improve the bound for polyhedral surfaces. Likewise, there are a wealth of motion and sensory constraints to consider. Most of these variations of pursuit-evasion have a natural analog in a more general geometric setting.
Acknowledgments. This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation. We thank the anonymous referee for helping us to improve the exposition.
References
[1]	M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8 (1983), 1-12.
[2]	F. Albrecht and I. D. Berg, Geodesics in euclidean space with analytic obstacles, Proceedings of the American Mathematical Society 113 (1991), 201-207.
[3]	S. Alexander, R. Bishop and R. Ghrist, Pursuit and evasion in non-convex domains of arbitrary dimensions, in: Proceedings of Robotics: Science and Systems, 2006 .
[4]	S. Alexander, R. Bishop and R. Ghrist, Capture Pursuit Games on Unbounded Domains, L'Enseignment Mathematique 55 (2009), 103-125.
[5]	S. Alexander, R. Bishop and R. Ghrist, Total Curvature and Simple Pursuit on Domains of Curvature Bounded Above, Geometriae Dedicata 149 (2010), 275-290.
[6]	B. Ames, A. Beveridge, R. Carlson, C. Djang, V. Isler, S. Ragain and M. Savage, A leapfrog strategy for pursuit-evasion in polygonal environments, International Journal of Computational Geometry and Applications (to appear).
[7]	M. Armstrong, Basic Topology, Springer, 1983.
[8]	D. Bhadauria, K. Klein, V. Isler and S. Suri, Capturing an evader in polygonal environments with obstacles: The full visibility case, International Journal of Robotics Research 31 (2012), 1176-1189.
[9]	A. Bonato and R. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.
[10]	M. Bridson and A. Haefliger, Metric Spaces of Non-positive Curvature, Springer-Verlag, 1999.
[11]	T. H. Chung, G. A. Hollinger and V. Isler, Search and pursuit-evasion in mobile robotics: a survey, Autonomous Robots 31 (2011), 299-316.
[12]	M. do Carmo, Differential Geometry of Curves and Surfaces, Prentice-Hall, 1976.
[13]	A. Hatcher, Algebraic Topology, Cambridge Univeristy Press, 2002.
[14]	V. Isler, S. Kannan and S. Khanna, Randomized pursuit-evasion in a polygonal environment, IEEE Transactions on Robotics 5 (2005), 864-875.
[15]	K. Klein and S. Suri, Pursuit-evasion on polyhedral surfaces, Algorithmica 73 (2015), 730-747.
[16]	S. Kopparty and C. V. Ravishankar, A framework for pursuit evasion games in Rn, Inf. Process. Lett. 96 (2005), 114-122.
[17]	J. E. Littlewood, Littlewood's Miscellany, Cambridge Univeristy Press, 1986.
[18]	N. Noori and V. Isler, Lion and man game on convex terrains, in: Workshop on the Algorithmic Foundations of Robotics (WAFR), 2014 .
[19]	N. Noori and V. Isler, Lion and man game on polyhedral surfaces with boundary, in: IEEE Conference on Intelligent Robots and Systems (IROS), 2014 .
206
Ars Math. Contemp. 13 (2017) 107-123
[20]	B. S. Schroder, The copnumber of a graph is bounded by §genus(G)J + 3, in: J. Koslowski and A. Melton (eds.), Categorical Perspectives: Proceedings of the Conference in Honor of George Strecker's 60th Bitrthday, 2001 pp. 243-263.
[21]	J. Sgall, A solution to David Gale's lion and man problem, Theoretical Comp. Sci. 259 (2001), 663-670.
[22]	Z. Zhou, J. R. Shewchuk, H. Huang and C. T. Tomlin, Smarter lions: Efficient full-knowledge pursuit in general arenas, unpublished technical report, University of California, Berkeley, 2012, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1. 381.2253.