11institutetext:  Department of Mathematics, Toronto Metropolitan University,
Toronto, ON, M5B 2K3, Canada 11email<EMAIL_ADDRESS>
# Triangle Evacuation of 2 Agents in the Wireless Model ††thanks:  This is the
full version of the paper with the same title [20] which will appear in the
proceedings of the 18th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks (ALGOSENSORS 2022), 8-9 September 2022 in
Potsdam, Germany.

Konstantinos Georgiou Research supported in part by NSERC. Woojin Jang

###### Abstract

The input to the _Triangle Evacuation_ problem is a triangle $ABC$. Given a
starting point $S$ on the perimeter of the triangle, a feasible solution to
the problem consists of two unit-speed trajectories of mobile agents that
eventually visit every point on the perimeter of $ABC$. The cost of a feasible
solution (evacuation cost) is defined as the supremum over all points $T$ of
the time it takes that $T$ is visited for the first time by an agent plus the
distance of $T$ to the other agent at that time.

Similar evacuation type problems are well studied in the literature covering
the unit circle, the $\ell_{p}$ unit circle for $p\geq 1$, the square, and the
equilateral triangle. We extend this line of research to arbitrary non-obtuse
triangles. Motivated by the lack of symmetry of our search domain, we
introduce 4 different algorithmic problems arising by letting the starting
edge and/or the starting point $S$ on that edge to be chosen either by the
algorithm or the adversary. To that end, we provide a tight analysis for the
algorithm that has been proved to be optimal for the previously studied search
domains, as well as we provide lower bounds for each of the problems. Both our
upper and lower bounds match and extend naturally the previously known results
that were established only for equilateral triangles.

###### Keywords:

Search Evacuation Triangle Mobile Agents

##  1 Introduction

Search Theory is concerned with the general problem of retrieving information
in some search domain. Seemingly simple but mathematically rich problems
pertaining to basic geometric domains where studied as early as the 1960's,
see for example [6] and [7], then popularized in the Theoretical Computer
Science community in the late 1980's by the seminal works of Baeza-Yates et
al. [4], and then recently re-examined under the lens of mobile agents, e.g.
in [13].

In search problems closely related to our work, a hidden item (exit) is placed
on a geometric domain and can only be detected by unit speed searchers (mobile
agents or robots) when any of them walks over it. When the exit is first
visited by an agent, its location is communicated instantaneously to the
remaining agents (wireless model) so that they all gather to the exit along
the shortest path in the underlying search domain. The time it takes for the
last agent to reach the exit, over all exit placements, is known as the
_evacuation time_ of the (evacuation) algorithm.

Optimal evacuation algorithms for 2 searchers are known for a series of
geometric domains, e.g. the circle [13], $\ell_{p}$ circles [24], and the
square and the equilateral triangle [17]. For all these problems, a plain-
vanilla algorithm is the optimal solution: the two searchers start from a
point on the perimeter of the geometric domain and search the perimeter in
opposite directions at the same unit speed until the exit is found, at which
point the non-finder goes to the exit along the shortest path.

In this work we consider the 2 searcher problem in the wireless model over
non-obtuse triangles. The consideration of general triangles comes with
unexpected challenges, since even the worst-case analysis of the plain-vanilla
algorithm becomes a technical task due to the lack of symmetry of the search
domain. But even more interestingly, the consideration of general triangles
allows for the introduction of 4 different algorithmic problems pertaining to
the initial placement of the searchers. Indeed, in all previously studied
domains, the optimal algorithm had the searchers start from the same point on
the perimeter.

Motivated by this, we consider 4 different algorithmic problems that we
believe are interesting in their own right. These problems are obtained by
specifying whether the algorithm or the adversary chooses the starting edge
and/or the starting point on that edge for the 2 searchers. In our results we
provide upper bounds for all 4 problems, by giving a technical and tight
analysis of the plain-vanilla algorithm that we call OppositeSearch. We also
provide lower bounds for arbitrary search algorithms for the same problems.
This is the full version of a published extended abstract with the same tile
[20].

It is worth noting that the results of [17] for the equilateral triangle were
presented in the form of evaluating the evacuation time of the OppositeSearch
algorithm for any starting point on the perimeter for the purpose of finding
only the best starting point. It is an immediate corollary to obtain optimal
results for all 4 new algorithmic problems, but only for the equilateral
triangle. Both our upper and lower bounds for general triangles match and
extend the aforementioned results for the equilateral triangle. To that end,
one of our surprising findings is that for some of the algorithmic problems,
the evacuation time is more than half the perimeter of the search domain, even
though the induced searchers' trajectories stay exclusively on the perimeter
of the domain and the searchers cover the entire triangle perimeter for the
worst placements of the exit (which would be the same trajectory, should the
exit was found only at the very end of the search). This is despite that two
agents can search the entire domain in time equal to half the triangle
perimeter.

##  2 Related Work

Search problems have received several decades of treatment that resulted in
some interesting books [1, 2], in a relatively recent survey [25], and in an
exposition of mobile agent-based (and hence more related to our work) results
in [19]. A primitive, and maybe the most well-cited search-type problem is the
so-called cow-path or linear-search [3] in which a mobile agent searches for
hidden item on the infinite line. Numerous variations of the problem have been
studied, ranging from different domains to different searchers specifications
to different objectives. The interested reader may consult any of the
aforementioned resources for problem variations. Below we give a
representative outline of results most relevant to our new contributions, and
pertaining primarily to wireless evacuation from geometric domains.

The problem of evacuating 2 or more mobile agents from a geometric domain was
consider by Czyzowicz et al. [13] on the circle. The authors considered the
distinction between the wireless (our communication model), where searchers
exchange information instantaneously, and the face-to-face model, where
information cannot be communicated from distance. The results pertaining to
the wireless model were optimal, while improved algorithms for the face-to-
face model followed in [16, 8, 18]. A little later, the work of [10] also
considered trade-offs to multi-objective evacuations costs. Since the first
study of [13] a number of variations emerged. Different searchers' speeds were
considered in [26], faulty robots were studied in [14, 22], evacuation from
multiple exits was introduced in [12], searching with advice was considered in
[23], and search-and-fetch type evacuation was studied in [21].

The work most relevant to our new contributions are the optimal evacuation
results in the wireless model of Czyzowicz et al. [17] pertaining to the
equilateral triangle. In particular, Czyzowicz et al. considered the problem
of placing two unit speed wireless agents on the perimeter of an equilateral
triangle. If the starting point is $x$ away from the middle point of any edge
(assumed to have unit length, hence $x\leq 1/2$), they showed that the optimal
worst-case evacuation cost equals $3/2+x$. As a corollary, the overall best
evacuation cost is 3/2 if the algorithm can choose the starting point, even if
an adversary chooses first an edge for where the starting point will be
placed. Similarly, the evacuation cost is 2 when an adversary chooses the
searchers' starting point even if the algorithm can choose the starting edge.
These are the results that we extend to general triangles by obtaining
formulas that are functions of the triangle edges. Notably, the search domains
of [17] were later re-examined in the face-to-face model [9] and with limited
searchers' communication range [5].

One of the main features of our results is that we quantify the effectiveness
of choosing the starting point of the searchers. When the search domain is the
circle [17], the starting point is irrelevant as long as both agents start
from the same point (and turns out it is optimal to have searchers initially
co-located on the perimeter). Nevertheless, strategic starting points based on
the searchers' relative distance have been considered in [15, 11]. Apart from
[17], the only other result we are aware of where the (same) starting point of
the searchers has to be chosen strategically is that of [24] that considered
evacuation from $\ell_{p}$ unit discs, with $p\geq 1$. Nevertheless, a key
difference in our own result is that the geometry of the underlying search
domain, that is a triangle, allows us to quantify how good an evacuation
solution can be when choosing the searchers' and the exit's placement. In
particular the order of decisions for the problems studied here, once one
fixes an arbitrary triangle, are obtained by fixing (i) the starting edge of
the searchers, then (ii) the starting point on that edge, then (iii) the
searchers' evacuation algorithm, and then (iv) the placement of the exit, in
that order. Item (iii) is always an algorithmic choice while (iv) is always an
adversarial choice.

##  3 Problem Definition, Motivation & Results

We begin with the problem definition and some motivation. Two unit speed
mobile agents start from the same point on the perimeter of some non-obtuse
triangle $ABC$. Somewhere on the perimeter of $ABC$ there is a hidden object,
also referred to as the exit, that an agent can see only if it is collocated
with the exit. When an agent identifies the location of the exit, the
information reaches the other agent instantaneously, or as it is described in
the literature, the mobile agents operate under the so-called wireless model.
A feasible solution to the problem consists of agents' trajectories that
ensure that regardless of the placement of the exit, both agents eventually
reach the exit. For this reason such solutions/algorithms are also known as
evacuation algorithms. The time it takes the last agent to reach the exit is
known as the _evacuation time_ of the algorithm for the specific exit
placement. As it is common for worst-case analysis, in this work we are
concerned with the calculation of the _worst-case evacuation cost_ of an
algorithm (or simply evacuation cost), that is, the supremum of the evacuation
time over all possible placements of the exit. Note that the worst-case
evacuation cost of an algorithm is a function of the agents' starting point,
and of course the size of the given triangle $ABC$.

The 2-agent evacuation problem in the wireless model has been studied on the
circle, the square and the equilateral triangle. Especially when the search
domain enjoys the symmetry of the circle, the starting point of the agents is
irrelevant. In other cases when the search domain exhibits enough symmetries,
e.g. for the square and the equilateral triangle, the exact evaluation of the
worst-case evacuation cost (as a function of the agents' starting point) for a
natural (and optimal algorithm) is an easy exercise, and due to the underlying
symmetries not all starting points need to be considered. Interestingly,
things are quite different in our problem when the search domain is a general
non-obtuse triangle; indeed, not only the worst-case evacuation cost depends
(in a strong sense) on the agents' starting point, but also its' exact
evaluation (as a function of the starting point, and the triangle's edges) is
a non-trivial task even for a plain-vanilla evacuation algorithm.

Due to the asymmetry of a general triangle, we are motivated to identify
efficient evacuation algorithms when the agents' starting point is chosen in
two steps:
_Step 1:_ Choose a starting edge (either the largest, or the second largest,
or the smallest), and
_Step 2:_ Choose the starting point on that edge.
Each of the two choices can be either _algorithmic or adversarial_ , giving
rise to 4 different interesting algorithmic questions, summarized in the next
table, that also introduces notation for the best possible evacuation time,
over all evacuation algorithms. Note that after a starting edge and a starting
point on that edge are fixed, the performance (evacuation cost) of an
evacuation algorithm is quantified as the worst-case evacuation time over all
adversarial placements of the exit. To that end, we are after algorithms that
minimize the evacuation cost in the underlying algorithmic/adversarial choice
of a starting point, as a function of the edge lengths $a\geq b\geq c$.

Choose Edge | Choose Starting Point | Optimal Evacuation Cost
---|---|---
Algorithm | Algorithm | $\underline{\mathcal{L}}(a,b,c)$
Adversary | Algorithm | $\overline{\mathcal{L}}(a,b,c)$
Algorithm | Adversary | $\underline{\mathcal{U}}(a,b,c)$
Adversary | Adversary | $\overline{\mathcal{U}}(a,b,c)$

Our contributions read as follows.

###### Theorem 3.1

For triangle $ABC$ with edges $a\geq b\geq c$, we have that

$\displaystyle\underline{\mathcal{L}}(a,b,c)$ $\displaystyle=\frac{a+b+c}{2},$
$\displaystyle\frac{a+b+c}{2}\leq\overline{\mathcal{L}}(a,b,c)$
$\displaystyle\leq\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\},$
$\displaystyle\min\left\\{\frac{1}{2}\sqrt{\frac{2b^{2}(a-c)-(a-2c)(a+c)^{2}}{a}}+b,a+c\right\\}\leq\underline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq\min\left\\{\frac{a}{2}+b+\frac{c}{2},a+c\right\\},$
$\displaystyle
a+\frac{1}{2}\sqrt{\frac{2a^{2}(b-c)-(b-2c)(b+c)^{2}}{b}}\leq\overline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq a+\frac{b+c}{2},$

where $\tau$ is the area of the triangle.

Theorem 3.1 is a generalization of some of the results in [17] about the
equilateral triangle evacuation problem. Indeed, if the searchers' starting
point is $x$ away from the middle point of an equilateral triangle with edges
$a=b=c=1$, the authors of [17] proved that the optimal evacuation cost equals
$3/2+x$, showing this way that
$\underline{\mathcal{L}}(a,a,a)=\overline{\mathcal{L}}(a,a,a)=3a/2$ and
$\underline{\mathcal{U}}(a,a,a)=\overline{\mathcal{U}}(a,a,a)=2a$. The claims
of Theorem 3.1 imply the exact same bounds by setting $a=b=c$.

##  4 Preliminaries for our Upper Bound Arguments

In this section we introduce some notation, we recall some useful past
results, as well as we make some technical observations that we use repeatedly
in our arguments. Line segments with endpoints $A,B$ are denoted as $AB$. By
abusing notation, and whenever it is clear from the context, we also use $AB$
to refer to the length of the line segment. We use $\angle BAC$ to refer to
the angle of vertex $A$ of triangle $ABC$, or simply as $\angle A$ (or even
more simply $A$), whenever it is clear from the context.

Our upper bounds for all 4 algorithmic problems we consider are obtained by
analyzing the plain-vanilla algorithm that has been proved to be optimal for
other search domains in the wireless model, e.g. the circle and the
equilateral triangle. We refer to this algorithm as OppositeSearch.

The OppositeSearch Algorithm: The algorithm is executed once the two agents
are placed at any point on the perimeter of the given geometric search domain.
The two agents search the perimeter of the domain in opposite directions at
the same unit speed until one of them reports the exit. Then the non-finder,
who is notified instantaneously, goes to the exit along the shortest line
segment. Consequently, the evacuation cost, for any exit placement, is the
time that the non-finder reaches the exit. Note also that due to the symmetry
of the communication model, it does not matter who is the exit finder, rather
only when the exit is found.

Our upper bounds rely on a tight analysis of the OppositeSearch algorithm. Our
proofs use a monotonicity criterion of [15] that we present next. The lemma
refers to arbitrary unit-speed trajectories $S(t),R(t)\in\mathbb{R}^{2}$,
$t\geq 0$, assumed to be continuous and differentiable at $t=0$. Let also
$S=S(0)$ and $R=R(0)$. We think of $S,R$ as the locations of the two robots
where one of them reports the exit. We define the _critical angle_ of robot
$S(t)$ (similarly of robot $R(t)$) as the angle that the velocity vector
$S^{\prime}(0)$ forms with segment $SR$ (and as the angle that velocity vector
$R^{\prime}(0)$ forms with segment $SR$, for robot $R(t)$). The following
lemma characterizes the monotonicity of the evacuation time, assuming that the
exit is found in one of the two points $S,R$.

######  Lemma 1 (Theorem 2.6 in [15])

Let $\phi,\theta$ denote the critical angles of robots $S(t),R(t)$ at time
$t=0$. Then, the evacuation cost, assuming that the exit is at $S$ or $R$, is
strictly increasing if $\cos\left({\phi}\right)+\cos\left({\theta}\right)<1$
strictly decreasing if $\cos\left({\phi}\right)+\cos\left({\theta}\right)>1$
and constant otherwise.

Intuitively, the proof of Lemma 1 relies on that the rate by which the two
agents approach each other is
$\cos\left({\phi}\right)+\cos\left({\theta}\right)$, while the rate by which
the time goes by is 1. Lastly, our arguments often reduce to the solutions of
Non-Linear Programs (NLPs). Whenever we do not provide a theoretical solution
to the NLPs, we solve them using computer assisted symbolic (non-numerical)
calculations on Mathematica which is guaranteed to report the global optimal
value [27].

###  4.1 Evacuation Cost for two Line Segments

In this section we analyze the performance of OppositeSearch under a special
scenario, see Figure 1(a). We consider a configuration according to which a
portion of the search domain has already been explored, and currently the two
agents reside at points $B,C$, both moving towards point $A$ at unit speed.
Conditioning that the exit is somewhere on segments $AB,AC$, we calculate the
evacuation cost, e.g. the worst-case time it takes the last agent to reach the
exit, over all placements of the exit. The section is devoted into proving the
following lemma.

###### Lemma 2

Consider two unit speed robots starting at points $B,C$ simultaneously, and
moving toward point $A$ along the corresponding line segments. Assuming that
an exit is placed anywhere on segments $AB,AC$, and $\angle A\leq\pi/2$, then
the worst case evacuation time equals $\max\\{AB,AC,BC\\}$.

Without loss of generality we assume that in triangle $ABC$ we have $\angle
B\geq\angle C$, and hence $AC\geq AB$.

(a) Two agents start from points $B,C$ and move towards $A$. The exit is
placed somewhere on line segments $AB,AC$. Their critical angles, after
searching for time $x$ are denoted as $\phi_{x},\theta_{x}$, respectively.

(b) The starting point $S$ of the two robots in the analysis of Section 5.

(c) The positions of the two robots in Configuration 1. Both $R_{1},R_{2}$
move towards $C$.

(d) The positions of the two robots in Configuration 2. Both $R_{1},R_{2}$
move towards $A$.

Figure 1: Different configurations of searchers' starting points.

We refer to robots at points $B,C$ as $S,R$, respectively. Since robots are
moving from points $B,C$ towards $A$ at unit speed, it follows that the exit
will be found either at some time $x\leq AB$, by either of the two robots, or
at time $x\geq AB$.

###### Claim

If the exit is found when $x\geq AB$, then the worst case evacuation cost is
$AC$.

###### Proof

Since the exit is found at $x\geq AB$, the exit will be on edge $AC$. At time
$AB$, robot $S$ reaches $A$, robot $R$ still moves towards $A$, and the two
robots move towards each other. This instance is covered by Lemma 1. Note that
their corresponding critical angles are both $0$ (until they meet), and since
$2\cos\left({0}\right)=2>1$, it follows that the worst placement of the exit
is any of the locations of the two robots when $S$ reaches $A$. That gives
evacuation cost $AC$.

Next we analyze the case that the exit is found at time $x\leq AB$. Our goal
is to show that also in this case, the evacuation cost equals
$\max\\{AB,AC,BC\\}$. Let $\phi_{x},\theta_{x}$ be robots' critical angles at
time $x$, see Figure 1(a). Let also $S_{x},R_{x}$ denote their locations on
$AB,AC$ respectively. In order to identify the time $x$ that induces the worst
case evacuation time, and as per Lemma 1, we need to examine expression

$f(x):=\cos\left({\theta_{x}}\right)+\cos\left({\phi_{x}}\right).$

Consider also triangle $AS_{x}R_{x}$. Clearly, $A+\phi_{x}+\theta_{x}=\pi$,
and hence
$f(x)=\cos\left({\theta_{x}}\right)+\cos\left({\pi-(A+\phi_{x})}\right)=\cos\left({\theta_{x}}\right)-\cos\left({A+\phi_{x}}\right)$.

###### Claim

If $\angle A<\pi/3$, then $f(x)\neq 1$.

###### Proof

Using trigonometric identities, we have

$f(x)=\cos\left({\theta_{x}}\right)-\cos\left({A}\right)\cos\left({\theta_{x}}\right)+\sin\left({A}\right)\sin\left({\theta_{x}}\right).$

Now consider transformation $y=\cos\left({\theta_{x}}\right)$, and therefore
$\sqrt{1-y^{2}}=\sin\left({\theta_{x}}\right)$. Under the previous
transformation, we can write that

$f(x)=\left(1-\cos\left({A}\right)\right)y+\sin\left({A}\right)\sqrt{1-y^{2}}.$

It follows that equation $f(x)=1$ can be reduced to finding the roots to a
degree 2 polynomial in $y$, with discriminant $1-2\cos\left({A}\right)$. When
$A<\pi/3$ the discriminant is negative, and hence $f(x)=1$ has no roots.

Note that Claim 4.1 implies that $f(x)-1$ preserves sign. Moreover for $x=AB$
we have that $\theta_{x}=0$ and $\phi_{x}=\pi-A$. Therefore,
$f(AB)=\cos\left({0}\right)+\cos\left({\pi-A}\right)=1-\cos\left({A}\right)<1$,
and moreover $f(x)<1$ for all $x$. By Lemma 1, it follows that the evacuation
cost remains increasing for $x\leq AB$, and hence the worst placement of the
exit is at $A$, inducing evacuation cost $AC$. At the same time, if $\angle
A<\pi/3$ (in the case we are examining) and since $\angle B\geq\angle C$, edge
$AC$ is indeed the largest edge. This concludes the lemma in case $\angle
A<\pi/3$.

We are now focusing on the case that $\angle A\geq\pi/3$, and we show that the
worst placement of the exit is either at $B$ or at $A$. Indeed, first we claim
that initially, the evacuation cost is decreasing.

###### Claim

The evacuation cost at $x=0$ is decreasing.

###### Proof

When $x=0$, we have that $\phi_{x}=B$ and $\theta_{x}=C$. But then, we have
that $f(0)=\cos\left({C}\right)+\cos\left({B}\right)$. The previous function,
subject to that $B\geq C$ and that $A+B+C=\pi$ (for non-negative variables
$A,B,C$) attains a minimum of value $1$.
$f(0)=\cos\left({C}\right)+\cos\left({B}\right)\geq 2\cos\left({C}\right)$. By
Lemma 1, this shows that at $x=0$ the evacuation cost is decreasing.

Now we show that the evacuation cost has only one extreme point with respect
to $x\leq AB$ (either maximizer or minimizer).

###### Claim

The evacuation cost attains only one critical point when $x\leq AB$.

###### Proof

As in the proof of Claim 4.1, we attempt to find critical points by solving
equation $f(x)=1$. As a reminder, the latter equation reduces to finding the
roots of a degree 2 equation (in $y=\cos\left({\theta_{x}}\right)$)

$\left(1-\left(1-\cos\left({A}\right)\right)y\right)^{2}=\sin\left({A}\right)^{2}\left(1-y^{2}\right)$

with discriminant $1-2\cos\left({A}\right)$. Now that $A\geq\pi/3$, the degree
2 polynomial has two (possibly double) roots, and these are

$y_{1,2}=\frac{1}{2}\left(1\pm\frac{\sqrt{1-2\cos\left({A}\right)}}{\tan\left(A/2\right)}\right)$

We show that only one of them corresponds to a critical point. To see why,
recall that $y=\cos\left({\theta_{x}}\right)$, and that $0\leq\theta_{x}\leq
C$, and therefore $\cos\left({C}\right)\leq y\leq 1$.

On the other hand, in triangle $ABC$, we have $A+B+C=\pi$, and since $B\geq
C$, it follows that $C\leq(\pi-A)/2$. Therefore
$\cos\left({C}\right)\geq\cos\left({(\pi-A)/2}\right)=\sin\left({A/2}\right)$.
But then, any critical point $y$ must also satisfy $\sin\left({A/2}\right)\leq
y\leq 1$. When $A\geq\pi/3$ it is easy to see that only one of the two roots
$y_{1,2}$ is not less than $\sin\left({A/2}\right)$, while since $A\leq\pi/2$,
the largest of the roots does not exceed 1.

To conclude, by Claim 4.1, the evacuation cost has only one critical point.
Since by Claim 4.1 the evacuation cost is initially decreasing, the unique
critical point must be a minimizer. As a result, the evacuation cost is
maximized either at $x=0$ or at $x=AB$. In the former case the cost equals
$BC$, while in the latter, the cost equals $AC$. In any case, the worst case
evacuation cost for $x\leq AB$ equals $\max\\{BC,AB\\}$.

Combining the latest statement with Lemma 4.1 (that holds for all angles $A$),
we conclude that also in the case that $A\geq\pi/3$, the worst case evacuation
cost equals $\max\\{AB,AC,BC\\}$, as promised by Lemma 2.

##  5 Evacuation Cost Analysis for Special Initial Starting Points

The purpose of this section is to analyze the evacuation cost of
OppositeSearch for searching triangle $ABC$ with edge lengths
$\alpha,\beta,\gamma$. In this section only, we assume that the starting point
$S$ of the agents lies on edge $BC$ (of length $\alpha$), and that it is $x$
away from the middle point $N$ of $BC$ on the side of $B$, i.e.
$BS=\alpha/2-x$ and $NS=x$, where $0\leq x\leq\alpha/2$, see also Figure 1(b).
If $T(x)$ denotes the worst-case evacuation time (over all placements of the
exit) starting from $S$, we want to calculate

$\max_{0\leq x\leq\alpha/2}T(x),~{}~{}\min_{0\leq x\leq\alpha/2}T(x),$

that is, the worst and best starting points on segment $NB$ (inducing worst
possible and best possible worst-case costs).

The best starting point can be thought of as an algorithmic choice, whereas
the worst starting point can be thought of as an adversarial choice. We note
here that $T(x)$ denotes the worst-case evacuation cost for the starting point
induced by point $S=S(x)$, which is determined by the adversarial placement of
the exit anywhere on the perimeter of the triangle. That is, for each
placement $I$ of the exit, and each $x$, $T(x)$ denotes the supremum of the
evacuation cost of the algorithm that has agents start from $S$ and given that
the exit is at $I$, where the supremum is taken over all $I$.

Even though the starting point $S$, in this section, is restricted to be in
segment $BN$, we will do the performance analysis for all cases regarding the
relative lengths of $\alpha,\beta,\gamma$. That will allow us in Section 6 to
deduce the worst possible and best possible worst-case costs starting anywhere
on the perimeter of a triangle for algorithm OppositeSearch.

###  5.1 Observations for Two Special Configurations

Starting from $S$, agents $R_{1},R_{2}$ traverse clockwise and
counterclockiwse the perimeter of $ABC$ until the exit is found. Then, the
exit's location is reported, and the non-finder is informed instantaneously
and evacuates along the shortest path. Note that $R_{1}$ reaches $B$ no later
than $R_{2}$ reaches $C$. Also, $R_{1}$ reaches point $A$ in total time
$\alpha/2-x+\gamma$, while $R_{2}$ reaches $C$ in time $\alpha/2+x$. The next
observation follows immediately from Lemma 1.

###### Observation 5.1

Until either $A$ is reached by $R_{1}$ or $C$ is reached by $R_{2}$, the
evacuation cost is increasing.

In the analysis below, we denote by $R_{1},R_{2}$ the locations (points on the
perimeter of $ABC$) of the two agents, when the first among points $B,C$ is
reached by either of the agents. We also abuse notation and we use
$R_{1},R_{2}$ to refer also to the identities of the agents. Which of the two
points $A,C$ is reached first depends on the original starting point $S$.
Therefore, all distances of $R_{1},R_{2}$ to any other point is a function of
$x$, and so we will write, for example, $R_{1}R_{2}(x)$ or $AR_{2}(x)$ for the
segments $R_{1}R_{2}$ and $AR_{2}$, respectively.

###### Definition 1

We say that we are in Configuration 1 (see Figure 1(c)) if agent $R_{1}$
reaches point $A$ no later than $R_{2}$ reaches $C$. We say that we are in
Configuration 2 if agent $R_{2}$ reaches point $C$ no later than $R_{1}$
reaches $A$ (see Figure 1(d)).

###### Lemma 3

In Configuration 1, we have that
$T(x)=\alpha/2+\gamma-x+\max\\{R_{1}R_{2}(x),\beta,2x-\gamma\\}$, where
$R_{1}R_{2}(x)=AR_{2}(x)$. In Configuration 2, we have that
$T(x)=\alpha/2+x+\max\\{R_{1}R_{2}(x),\beta,\gamma-2x\\}$, where
$R_{1}R_{2}(x)=R_{1}C(x)$.

###### Proof

For Configuration 1, we see that $R_{1}$ reaches point $A$ no later than
$R_{2}$ reaches $C$ if and only $x\geq\gamma/2$. In this case, since also
$R_{1}$ reaches point $A$ time $\alpha/2-x+\gamma$, and $R_{2}$ starts
$x+\alpha/2$ way from $C$, it follows that

$R_{2}C=SC-SR_{2}=x+\alpha/2-(\alpha/2-x+\gamma)=2x-\gamma.$

By Observation 5.1, up to that moment the evacuation cost keeps increasing.
From that moment on, $R_{1},AR_{2}$ move towards the same point $C$, and hence
Lemma 2 applies, according to which the evacuation cost becomes

$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2},AM,R_{2}C\\}=\alpha/2+\gamma-x+\max\\{AR_{2},\beta,2x-\gamma\\},$

where $AR_{2}=AR_{2}(x)$. Note that in particular in this case, we have that
$R_{1}=A$.

For Configuration 2, we see that $R_{2}$ reaches point $C$ no later than
$R_{1}$ reaches $A$ if and only $x\leq\gamma/2$. In that case, $R_{2}$ reaches
$C$ in time $\alpha/2+x$, and hence while $R_{1}$ was originally
$\alpha/2-x+\gamma$ away from $A$, its current distance is

$R_{1}A=\alpha/2-x+\gamma-(\alpha/2+x)=\gamma-2x.$

Up to that moment, and by Observation 5.1, the evacuation cost was increasing.
From that moment on, $R_{1},R_{2}$ move towards the same point $A$, and hence
Lemma 2 applies, according to which the evacuation cost becomes

$T(x)=\alpha/2+x+\max\\{CR_{1},AM,R_{1}A\\}=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\},$

where $CR_{1}=CR_{1}(x)$. Finally, note that in this case, we also have
$C=R_{2}$.

Note that in both configurations, the worst case evacuation cost $T(x)$ is a
function of $R_{1}R_{2}(x)$, where either $R_{1}=A$ or $R_{2}=C$. The
following lemma will be used repeatedly later.

###### Lemma 4

In both Configurations 1,2, function $R_{1}R_{2}(x)$ is convex in its domain.

###### Proof

Consider some function $f(x)=\sqrt{x^{2}+bx+c}$. We note that
$\frac{d}{dx^{2}}\sqrt{x^{2}+bx+c}=\frac{4c-b^{2}}{4(x^{2}+bx+c)^{3/2}}$, and
therefore $f(x)$ is convex if and only if $4c\geq b^{2}$. We use this
observation to show that $R_{1}R_{2}(x)$ is indeed convex.

In Configuration 1, we have that $R_{1}R_{2}(x)=AR_{2}(x)$. In triangle
$AR_{2}C$ we apply the Cosine Law, and we have that

$\displaystyle AR_{2}(x)$
$\displaystyle=\left(\beta^{2}+(2x-\gamma)^{2}-2\beta(2x-\gamma)\cos(C)\right)^{1/2}$
$\displaystyle=2\left(x^{2}-(\beta\cos(C)+\gamma)x+(\beta^{2}+\gamma^{2}+2\beta\gamma\cos(C))/4\right)^{1/2}$

By our first observation, we can show that $AR_{2}(x)$ is convex by verifying
that

$\beta^{2}+\gamma^{2}+2\beta\gamma\cos(C)-(\beta\cos(C)+\gamma)^{2}=\beta^{2}\sin^{2}(C)\geq
0.$

In Configuration 2, we have that $R_{2}=C$. In triangle $AR_{1}C$ and by the
Cosine Law we have that

$\displaystyle CR_{1}(x)$
$\displaystyle=\left(\beta^{2}+(\gamma-2x)^{2}-2\beta(\gamma-2x)\cos(A)\right)^{1/2}$
$\displaystyle=2\left(x^{2}+(\beta\cos(A)-\gamma)x+(\beta^{2}+\gamma^{2}-2\beta\gamma\cos(A))/4\right)^{1/2}$

Again by our first observation we verify that $CR_{1}(x)$ by checking that

$(\beta^{2}+\gamma^{2}-2\beta\gamma\cos(A))-(\beta\cos(A)-\gamma)^{2}=\beta^{2}\sin^{2}(A)\geq
0.$

Now recall that Lemma 3 gave us the evacuation cost $T(x)$ as a function of
the starting point $S=S(x)$. In particular $T(x)$ is expressed as the maximum
quantity between linear functions (in $x$) and $R_{1}R_{2}(x)$ which is convex
by Lemma 4. Therefore we immediately obtain the following.

###### Corollary 1

The evacuation cost $T(x)$ is convex in its domain in both configurations.

Combined with Lemma 4, we will also need to evaluate $R_{1}R_{2}(x)$ at the
critical points $x\in\\{0,\alpha/2,\gamma/2\\}$. Whether $R_{1}R_{2}(x)$ is
defined for these values will depend on the given triangle $ABC$. For the
purposes of the lemma, we work under the assumptions that all these values are
in the domain of $R_{1}R_{2}(x)$ and we will make the proper check when we
invoke the lemma.

###### Lemma 5

In Configuration 1, we have

$\displaystyle R_{1}R_{2}(\gamma/2)$ $\displaystyle=\beta$ $\displaystyle
R_{1}R_{2}(\alpha/2)$
$\displaystyle=\left(\frac{\gamma(\beta+\gamma-\alpha)(\alpha+\beta-\gamma)}{\alpha}\right)^{1/2}$

In Configuration 2, we have

$\displaystyle R_{1}R_{2}(0)$ $\displaystyle=\alpha$ $\displaystyle
R_{1}R_{2}(\gamma/2)$ $\displaystyle=\beta$ $\displaystyle
R_{1}R_{2}(\alpha/2)$
$\displaystyle=\left(\frac{\alpha(\beta+\gamma-\alpha)(\alpha+\beta-\gamma)}{\gamma}\right)^{1/2}$

###### Proof

In Configuration 1, when $x=\gamma/2$, then $R_{2}=C$, and therefore
$R_{1}R_{2}(\gamma/2)=AC=\beta$.

Next we study $x=\alpha/2$ of the Configuration 1. Note that $R_{1}=A$ and
that $R_{2}C=\alpha-\gamma$. Using the Cosine Law in triangle $AR_{2}C$, we
have

$\displaystyle AR_{2}(\alpha/2)$
$\displaystyle=\left(\beta^{2}+(\alpha-\gamma)^{2}-2\beta(\alpha-\gamma)\cos(C)\right)^{1/2}$
$\displaystyle=\left(\frac{\gamma(\beta+\gamma-\alpha)(\alpha+\beta-\gamma)}{\alpha}\right)^{1/2},$

where the last equality is by expressing $\cos(C)$ as a function of the
triangle edges using the Cosine Law in triangle $ABC$ according to which
$\gamma^{2}=\alpha^{2}+\beta^{2}-2\alpha\beta\cos(C)$.

We move on with Configuration 2. When $x=0$, then $R_{1}=B$, and therefore
$R_{1}R_{2}(0)=BC=\alpha$. Also, when $x=\gamma/2$, then $R_{1}=A$, and
therefore $R_{1}R_{2}(\gamma/2)=AC=\beta$.

Finally, when $x=\alpha/2$, then $AR_{1}=\gamma-\alpha$. By the Cosine Law in
$CR_{1}A$, we have that

$\displaystyle CR_{1}(\alpha/2)$
$\displaystyle=\left(\beta^{2}+(\gamma-\alpha)^{2}-2\beta(\gamma-\alpha)\cos(A)\right)^{1/2}$
$\displaystyle=\left(\frac{\alpha(\beta+\gamma-\alpha)(\alpha+\beta-\gamma)}{\gamma}\right)^{1/2},$

where the last equality is by expressing $\cos(A)$ as a function of the
triangle edges using the Cosine Law in triangle $ABC$ according to which
$\alpha^{2}=\beta^{2}+\gamma^{2}-2\beta\gamma\cos(A)$.

We also use repeatedly the polytope $\Delta\subseteq\mathbb{R}^{3}$ identified
by all possible triples of edge lengths, i.e. $(\alpha,\beta,\gamma)\in\Delta$
if and only if

$\displaystyle\alpha+\beta\geq\gamma$ $\displaystyle\alpha+\gamma\geq\beta$
$\displaystyle\beta+\gamma\geq\alpha$ $\displaystyle\alpha,\beta,\gamma\geq 0$

We are now ready to provide tight bounds of OppositeSearch for quantities
$\max_{0\leq x\leq\alpha/2}T(x)$ and $\min_{0\leq x\leq\alpha/2}T(x),$ where
$x$, and the starting point of the two robots as in Figure 5. Our analysis is
done by cases depending on the size of the edges, that is Section 5.2 analyzes
the case $\alpha\geq\beta\geq\gamma$, Section 5.3 analyzes the case
$\alpha\geq\gamma\geq\beta$, Section 5.4 analyzes the case
$\beta\geq\alpha\geq\gamma$, Section 5.5 analyzes the case
$\beta\geq\gamma\geq\alpha$, Section 5.6 analyzes the case
$\gamma\geq\alpha\geq\beta$ and Section 5.7 analyzes the case
$\gamma\geq\beta\geq\alpha$. In each case we further analyze the cost of
$T(x)$ in Configurations 1 and 2, when applicable.

###  5.2 The case $\alpha\geq\beta\geq\gamma$

In Configuration 1 we have $x\geq\gamma/2$ and therefore

$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2},\beta,2x-\gamma\\}=\alpha/2+\gamma-x+\max\\{AR_{2},\beta\\},$

because $2x-\gamma\leq\alpha-\gamma\leq\beta$, by the triangle inequality. We
need to find the extreme values of $T(x)$ in the interval
$x\in[\gamma/2,\alpha/2]$.

###### Lemma 6

Given that $\alpha\geq\beta\geq\gamma$, we have that

$\displaystyle\max_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\beta+\gamma/2~{}~{}(\textrm{attained
at}~{}x=\gamma/2)$ $\displaystyle\min_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\beta+\gamma~{}~{}(\textrm{attained at}~{}x=\alpha/2).$

###### Proof

In the current configuration we have that

$T(x)=\alpha/2+\gamma+\max\\{AR_{2}(x)-x,\beta-x\\}$

We observe that as $x$ ranges between $\gamma/2$ and $\alpha/2$, point $R_{2}$
ranges in segment $BC$. As a result, $AR_{2}(x)$ ranges between $\gamma$ and
$\beta$, and hence, for all $x\in[\gamma/2,\alpha/2]$, we have
$\max\\{AR_{2}(x),\beta\\}=\beta$. But then $T(x)=\alpha/2+\gamma+\beta-x,$
attaining its minimum value at $x=\alpha/2$, and its maximum value at
$x=\gamma/2$.

Next we move to Configuration 2, in which case $x\leq\gamma/2$ and therefore

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\}=\alpha/2+x+\max\\{CR_{1},\beta\\}$

We show the next lemma.

###### Lemma 7

Given that $\alpha\geq\beta\geq\gamma$, we have that

$\displaystyle\max_{0\leq x\leq\gamma/2}T(x)$
$\displaystyle=\alpha/2+\max\\{\alpha,\beta+\gamma/2\\}~{}~{}(\textrm{attained
at}~{}x=0~{}\textrm{or}~{}x=\gamma/2~{}resp)$ $\displaystyle\min_{0\leq
x\leq\gamma/2}T(x)$
$\displaystyle=\frac{\alpha^{2}-\beta^{2}+\alpha\gamma+2\beta\gamma}{2\gamma}~{}~{}(\textrm{attained
at}~{}x=\gamma/2-\cos(A)\beta),$

where $\cos(A)$ can be computed with the Cosine Law in triangle $ABC$.

###### Proof

In the current configuration we have that

$T(x)=\alpha/2+\max\\{x+CR_{1}(x),\beta+x\\},$

with domain $[0,\gamma/2]$. By Corollary 1, $T(x)$ is convex, and hence
attains its maximum values in one of the endpoints $\\{0,\gamma/2\\}$. Using
Lemma 5, we calculate $T(x)$ at these two values, from which we conclude that
$\max_{0\leq x\leq\gamma/2}T(x)=\alpha/2+\max\\{\alpha,\beta+\gamma/2\\}$.

The minimum of $T(x)$ in the same domain is assumed when $CR_{1}(x)=\beta$,
for $x_{0}\neq 0$. But then triangle $AR_{1}C$ is isosceles, e.g. when
$R_{1}C=AC$. In this case, $\cos(A)=(\gamma-2x_{0})/(2\beta)$, and therefore
$x_{0}=\gamma/2-\cos(A)\beta$ (which can be verified to be non-negative
independently). But then,

$T(x_{0})=\alpha/2+\beta+\gamma/2-\cos(A)\beta,$

where $\cos(A)=(\beta^{2}+\gamma^{2}-\alpha^{2})/(2\beta\gamma)$ is obtained
by the Cosine Law in triangle $ABC$.

###  5.3 The case $\alpha\geq\gamma\geq\beta$

In Configuration 1 we have $x\geq\gamma/2$ and so

$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2},\beta,2x-\gamma\\}=\alpha/2+\gamma-x+\max\\{AR_{2},\beta\\}$

since $2x-\gamma\leq\alpha-\gamma\leq\beta$, where the last inequality is due
to triangle inequality.

We show the next lemma.

###### Lemma 8

Given that $\alpha\geq\gamma\geq\beta$, we have that

$\displaystyle\max_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\beta+\gamma/2~{}~{}(\textrm{attained
at}~{}x=\gamma/2)$ $\displaystyle\min_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\beta+\gamma~{}~{}(\textrm{attained at}~{}x=\alpha/2).$

###### Proof

In the current configuration we have that

$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2}(x),\beta\\},$

with domain $[\gamma/2,\alpha/2]$. For this we show that for all
$x\in[\gamma/2,\alpha/2]$, we have that $AR_{2}(x)\leq\beta$.

Indeed, by Lemma 5, we know that $AR_{2}(\gamma/2)=\beta$, and by Lemma 4 that
$AR_{2}(x)$ is convex. Moreover, it is straightforward that $AR_{2}(x)$ is
strictly decreasing at $x=\gamma/2$. We show that there is no
$x_{0}\in(\gamma/2,\alpha/2)$ with $AR_{2}(x_{0})=\beta$, which would imply
that $AR_{2}(x)\leq\beta$.

We observe that if $AR_{2}(x_{0})=\beta$, then triangle $AR_{2}C$ is
isosceles, with base $2x_{0}-\gamma$, and angle of the base vertices equal to
$C$. Therefore, $\cos(C)=(2x_{0}-\gamma)/(2\beta)$, from which we get
$x_{0}=\gamma/2+\cos(C)\beta$. We argue that $x_{0}\geq\alpha/2$. Indeed,
algebraic calculations show that

$\gamma/2+\cos(C)\beta-\alpha/2=\frac{\gamma(\alpha-\gamma)+\beta^{2}}{2\alpha}\geq
0,$

since $\alpha\geq\gamma$. Overall, we showed that when
$\alpha\geq\gamma\geq\beta$, we have that
$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2}(x),\beta\\}=\alpha/2+\gamma-x+\beta,$
and therefore the maximum is attained at $x=\gamma/2$, and the minimum when
$x=\alpha/2$.

Next we study Configuration 2, in which $x\leq\gamma/2$ and therefore

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\}.$

We need to find the extreme values of $T(x)$ in the interval
$x\in[0,\gamma/2]$.

###### Lemma 9

Given that $\alpha\geq\gamma\geq\beta$, we have that

$\displaystyle\max_{0\leq x\leq\gamma/2}T(x)$
$\displaystyle=3\alpha/2~{}~{}(\textrm{attained at}~{}x=0)$
$\displaystyle\min_{0\leq x\leq\gamma/2}T(x)$
$\displaystyle=\frac{(\alpha+\gamma)^{2}-\beta^{2}+4\sqrt{3}\tau}{4\gamma}~{}~{}(\textrm{attained
at}~{}x=\gamma/2-\beta/2\left(\cos(A)+\sqrt{3}\sin{A}\right)),$

where $\tau$ is the area of triangle $ABC$, and $\cos(A),\sin(A)$ can be given
by the Cosine Law as functions of $\alpha,\beta,\gamma$.

###### Proof

By Corollary 1, $T(x)$ is convex, so it attains its maximum either at $x=0$ or
at $x=\gamma/2$. Using Lemma 5, we calculate

$T(0)=\alpha/2+\max\\{CR_{1}(0),\beta,\gamma\\}=\alpha/2+\max\\{\alpha,\beta,\gamma\\}3\alpha/2,$

and

$T(\gamma/2)=\alpha/2+\gamma/2+\max\\{CR_{1}(\gamma/2),\beta,0\\}=\alpha/2+\beta.$

But then,

$\max_{0\leq
x\leq\gamma/2}T(x)=\max\\{T(0),T(\gamma/2)\\}=\max\\{3\alpha/2,\alpha/2+\beta\\}=3\alpha/2.$

and the maximum is attained at $x=0$.

Next we calculate $\min_{0\leq x\leq\gamma/2}T(x)$, by writing $T(x)$ as a
piecewise function. First by comparing $\beta,\gamma-2x$ it is easy to see
that

$T(x)=\alpha/2+x+\left\\{\begin{array}[]{ll}\max\\{CR_{1}(x),\gamma-2x\\}&,~{}\textrm{if}~{}0\leq
x\leq\gamma/2-\beta/2\\\
\max\\{CR_{1}(x),\beta\\}&,~{}\textrm{if}~{}\gamma/2-\beta/2\leq
x\leq\gamma/2\end{array}\right.$

We first claim that if $x\leq\gamma/2-\beta/2$, then $CR_{1}(x)\geq\gamma-2x$.
To see why, we compute $CR_{1}(x)$ using the Cosine Law in triangle $AR_{1}C$,
according to which
$CR_{1}(x)=\left(\beta^{2}+(\gamma-2x)^{2}-2\beta(\gamma-2x)\cos(A)\right)^{1/2}.$
But then equating $CR_{1}(x)$ with $\gamma-2x$ gives
$\bar{x}=\gamma/2-\beta/(4\cos(A))$. We show that $\bar{x}\leq 0$, and that
would imply that $CR_{1}(x)\geq\gamma-2x$. For this we note that

$\cos(A)\gamma-\beta/2=\frac{\gamma^{2}-\alpha^{2}}{2\beta}\leq 0,$

since $\alpha\geq\gamma$. But then, $\cos(A)\gamma\leq\beta/2$ for all
triangles for which $\alpha\geq\gamma\geq\beta$, and so
$\bar{x}=\gamma/2-\beta/(4\cos(A))\leq 0$. Our argument shows that
$CR_{1}(x)\neq\gamma-2x$ when $0\leq x\leq\gamma/2-\beta/2$ but also by Lemma
5 we have $CR_{1}(0)=\alpha\geq\gamma$. By continuity, we conclude that
$CR_{1}(x)\geq\gamma-2x$ as promised (when $x\leq leq\gamma/2-\beta/2$).

Next we study $T(x)$ in the interval $[\gamma/2-\beta/2,\gamma/2]$, for which
we need to compare $CR_{1}(x),\beta$. Note that by Lemma 5, we have
$CR_{1}(\gamma/2),\beta$. Any $x_{0}<\gamma/2$ that would make
$CR_{1}(x_{0})=\beta$ would induce a isosceles $CAR_{1}$, with base equal to
$\gamma-2x_{0}$, and base angle $A$. But then,
$\cos(A)=(\gamma-2x_{0})/(2\beta)$, which implies that
$x_{0}:=\gamma/2-\cos(A)\beta\geq\gamma/2-\beta/2$ (since $A\geq\pi/3$ is the
largest angle in $ABC$). It is also easy to see that $CR_{1}(x)$ is increasing
at $x=\gamma/2$, and since $CR_{1}(\gamma/2)=\beta$ and the convexity of
$CR_{1}(x)$ (Lemma 4), we conclude that $T(x)=\alpha/2+x+CR_{1}(x)$ if
$\gamma/2-\beta/2\leq x\leq x_{0}$, and $T(x)=\alpha/2+x+\beta$ if $x_{0}\leq
x\leq\gamma/2$.

To conclude, we have

$T(x)=\left\\{\begin{array}[]{ll}\alpha/2+x+CR_{1}(x)&,~{}\textrm{if}~{}0\leq
x\leq x_{0}\\\ \alpha/2+x+\beta&,~{}\textrm{if}~{}x_{0}<\leq
x\gamma/2\end{array}\right.$

Now we show that $T(x)$ is minimizes in the interval $[0,x_{0}]$ and we show
how to find the minimizer.

By Corollary 1 we know that $T(x)$ is convex. We are showing that $T(x)$ is
decreasing at $x\rightarrow 0^{+}$, and increasing at $x\rightarrow x_{0}$.
For this, we calculate

$\frac{d}{dx}T(x)=\frac{2\beta\cos(A)-2\gamma+4x}{\sqrt{-2\beta\cos(A)(\gamma-2x)+\beta^{2}+(\gamma-2x)^{2}}}+1,$

where in particular $\cos(A)$ is given explicitly as a function of
$\alpha,\beta,\gamma$. We denote the last expression in $x$ by $f(x)$. Basic
calculations then derive that

$\lim_{x\rightarrow
0^{+}}T^{\prime}(x)=f(0)=\frac{-\alpha^{2}+\alpha\gamma+\beta^{2}-\gamma^{2}}{\alpha\gamma}$

and

$\lim_{x\rightarrow
x_{0}^{-}}T^{\prime}(x)=f(x_{0})=\frac{\alpha^{2}-\beta^{2}+\beta\gamma-\gamma^{2}}{\beta\gamma},$

where both $f(0),f(x_{0})$ are expressions on $\alpha,\beta,\gamma$. The
nonlinear program then,

$\displaystyle\max$ $\displaystyle~{}~{}f(0)$ $\displaystyle s.t.~{}~{}$
$\displaystyle\alpha\geq\gamma\geq\beta$
$\displaystyle(\alpha,\beta,\gamma)\in\Delta,$

with the condition that $\alpha=1$ attains the optimizer
$\alpha=\beta=\gamma=1$, and its value becomes $0$, that is over all
triangles, $f(0)\leq 0$, and hence $T(x)$ is initially decreasing.

Similarly, we consider the nonlinear program

$\displaystyle\min$ $\displaystyle~{}~{}f(x_{0})$ $\displaystyle s.t.~{}~{}$
$\displaystyle\alpha\geq\gamma\geq\beta$
$\displaystyle(\alpha,\beta,\gamma)\in\Delta.$

With the condition that $\alpha=1$, the minimizer is again
$\alpha=\beta=\gamma=1$, and its value becomes $0$. This shows that over all
triangles, $f(x_{0})\geq 0$, and hence $T(x)$ is eventually increasing in
$[0,x_{0}]$. Recall also that $T(x)=\alpha/2+x+\beta$, when $x\geq x_{0}$,
that is $T(x)$ is increasing in $x\geq x_{0}$. Overall, this shows that $T(x)$
attains a unique minimum in $[0,\gamma/2]$, and that is the unique minimum of
the convex function

$g(x):=\alpha/2+x+CR_{1}(x)=\alpha/2+x+\left(\beta^{2}+(\gamma-2x)^{2}-2\beta(\gamma-2x)\cos(A)\right)^{1/2}$

in the interval $[0,\gamma/2]$.

For this, we solve $g^{\prime}(x)=0$ for $x$, and we find that

$x_{1,2}=\left(3\gamma-3\beta\cos(A)\mp\sqrt{3}\beta\sin(A)\right)/6.$

It is easy to see that for all triangles with $\alpha\geq\gamma\geq\beta$ we
have that $x_{2}\geq\gamma/2$, and so the only root of $g^{\prime}(x)$, hence
the minimizer of $T(x)$ is
$x_{1}=\frac{1}{6}(3\gamma-3\beta\cos(A)-\sqrt{3}\beta\sin(A))$. It follows
that $\min_{0\leq x\leq\gamma}T(x)=T(x_{1})$ which simplifies to

$\frac{\sqrt{3}\sqrt{-((\alpha-\beta-\gamma)(\alpha+\beta-\gamma)(\alpha-\beta+\gamma)(\alpha+\beta+\gamma))}+(\alpha+\gamma)^{2}-\beta^{2}}{4\gamma}$

Recalling Heron's formula $\sqrt{p(p-\alpha)(p-\beta)(p-\gamma)}$ for the area
$\tau$ of a triangle with half perimeter $p$, gives the promised lower bound.

###  5.4 The case $\beta\geq\alpha\geq\gamma$

First we study Configuration 1 in which $x\geq\gamma/2$ and so

$T(x)=\alpha/2+\gamma-x+\max\\{AR_{2},\beta,2x-\gamma\\}=\alpha/2+\gamma-x+\max\\{AR_{2},\beta\\},$

because $2x-\gamma\leq\alpha-\gamma\leq\beta$, by the triangle inequality.

We show the next lemma.

###### Lemma 10

Given that $\beta\geq\alpha\geq\gamma$, we have that

$\displaystyle\max_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\beta+\gamma/2~{}~{}(\textrm{attained
at}~{}x=\gamma/2)$ $\displaystyle\min_{\gamma/2\leq x\leq\alpha/2}T(x)$
$\displaystyle=\beta+\gamma~{}~{}(\textrm{attained at}~{}x=\alpha/2).$

###### Proof

Recall that $T(x)=\alpha/2+\gamma-x+\max\\{AR_{2},\beta\\}$. As starting point
$S$ ranges on $BC$, we have $AR_{2}(x)\leq\max\\{\beta,\gamma\\}$, and
therefore $T(x)=\alpha/2+\gamma-x+\beta$ attaining its minimum at $x=\alpha/2$
and its maximum at $x=\gamma/2$.

Second, we study Configuration 2 in which $x\leq\gamma/2$ and therefore

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\}=\alpha/2+x+\max\\{CR_{1},\beta\\},$

because $\beta\geq\gamma$.

###### Lemma 11

Given that $\beta\geq\alpha\geq\gamma$, we have that

$\displaystyle\max_{0\leq x\leq\gamma/2}T(x)$
$\displaystyle=\alpha/2+\beta+\gamma/2~{}~{}(\textrm{attained
at}~{}x=\gamma/2)$ $\displaystyle\min_{0\leq x\leq\gamma/2}T(x)$
$\displaystyle=\alpha/2+\beta~{}~{}(\textrm{attained at}~{}x=0),$

###### Proof

We observe that for all $x\in[0,\gamma/2]$, we have that
$CR_{1}(x)\leq\max\\{\alpha,\beta\\}=\beta$, since point $R_{1}$ ranges in the
segment $AB$. Therefore $T(x)=\alpha/2+x+\beta,$ and so the maximum and
minimum are attained at $x=\gamma/2$ and $x=0$, respectively.

###  5.5 The case $\beta\geq\gamma\geq\alpha$

Regarding Configuration 1, we recall that $x\leq\alpha/2$. Since this
configuration happens only if $x\geq\gamma/2$ and $\gamma\geq\alpha$, we
conclude that the domain of the function in this case is either empty, or it
is covered by Configuration 2 (when $\alpha=\gamma$).

We now move to Configuration 2. Recall that $x\leq\alpha/2$, and since this
configuration happens only when $x\leq\gamma/2$ and $\gamma\geq\alpha$ we need
to determine the extreme values of

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\}=\alpha/2+x+\max\\{CR_{1},\beta\\},$

in the interval $x\in[0,\alpha/2]$ (since $\beta\geq\gamma$).

###### Lemma 12

Given that $\beta\geq\gamma\geq\alpha$, we have that

$\displaystyle\max_{0\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha+\beta~{}~{}(\textrm{attained at}~{}x=\alpha/2)$
$\displaystyle\min_{0\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\beta~{}~{}(\textrm{attained at}~{}x=0),$

###### Proof

We observe that for all $x\in[0,\alpha/2]$, we have that
$CR_{1}(x)\leq\max\\{\alpha,\beta\\}=\beta$, since point $R_{1}$ ranges in the
segment $AB$. Therefore $T(x)=\alpha/2+x+\beta,$ and so the maximum and
minimum are attained at $x=\alpha/2$ and $x=0$, respectively.

###  5.6 The case $\gamma\geq\alpha\geq\beta$

As in the previous section, the domain of our function in Configuration 1 is
either empty, or it is covered by Configuration 2 (when $\alpha=\gamma$). So
we move on to the study of Configuration 2. Recall that $x\leq\alpha/2$, and
since this configuration happens only when $x\leq\gamma/2$ and
$\gamma\geq\alpha$ we need to determine the extreme values of

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\},$

in the interval $x\in[0,\alpha/2]$.

The following lemma will be needed both for the proofs of Lemma 14 and Lemma
15.

###### Lemma 13

Let $T_{1}(x)=\alpha/2+x+CR_{1}(x)$, $T_{2}(x)=\alpha/2+\beta+x$,
$T_{3}(x)=\alpha/2+\gamma-x$, and suppose that
$\gamma\geq\max\\{\alpha,\beta\\}$. If in addition we have that $A\leq\pi/3$,
then $T_{1}(x)\leq\max\\{T_{2}(x),T_{3}(x)\\}$, for all $0\leq x\leq\alpha/2$.

###### Proof

We calculate $T_{2}(0)=\alpha/2+\beta$ and $T_{3}(0)=\alpha/2+\gamma$. Since
$\gamma\geq\max\\{\alpha,\beta\\}$ we see that $T_{3}(0)\geq T_{2}(0)$.
Moreover, $T_{2}(\alpha/2)=\alpha+\beta$ and $T_{3}(\alpha/2)=\gamma$. By the
triangle inequality we get that $T_{3}(\alpha/2)\leq T_{2}(\alpha_{2})$, so
that

$\max\\{T_{2}(x),T_{3}(x)\\}=\left\\{\begin{array}[]{ll}\alpha/2+\gamma-x&~{}\textrm{,
if}~{}x\leq\gamma/2-\beta/2\\\ \alpha/2+\beta+x&~{}\textrm{,
if}~{}x>\gamma/2-\beta/2\end{array}\right..$

Using Lemma 5, we also calculate
$T_{1}(0)=\alpha/2+x+CR_{1}(0)=3\alpha/2\leq\alpha/2+\gamma=T_{3}(0)$, because
$\gamma\geq\max\\{\alpha,\beta\\}$. Next we claim that $T_{1}(\alpha/2)\leq
T_{2}(\alpha/2)$. To see why, note that using the Cosine Law in $CR_{1}A$ we
have that
$CR_{1}(x)=\left(\beta^{2}+(\gamma-2x)^{2}-2\beta(\gamma-2x)\cos(A)\right)^{1/2}$,
where $\cos(A)=(\beta^{2}+\gamma^{2}-\alpha^{2})/(2\beta\gamma)$, by the
Cosine Law in $ABC$. Then, we solve the nonlinear program

$\displaystyle\max$ $\displaystyle~{}~{}T_{1}(\alpha/2)-T_{2}(\alpha/2)$
$\displaystyle s.t.~{}~{}$ $\displaystyle\gamma\geq\max\\{\beta,\gamma\\}$
$\displaystyle(\alpha,\beta,\gamma)\in\Delta.$

With the condition that $\alpha=1$, the minimizer is attained at again
$\alpha=\gamma=1,\beta=5/16$, and its value becomes $0$. This shows
that$T_{1}(\alpha/2)-T_{2}(\alpha/2)$.

Lastly, using also that $A\leq\pi/3$, we show that
$T_{1}(\gamma/2-\beta/2)\leq\alpha/2+\beta/2+\gamma/2$ (were the last
expression also equals to $T_{2}(\gamma/2-\beta/2)$ and to
$T_{2}(\gamma/2-\beta/2)$). Recalling also that $A\leq\pi/3$ and hence
$\cos(A)\geq 1/2$, we utilize the non linear program

$\displaystyle\max$
$\displaystyle~{}~{}T_{1}(\gamma/2-\alpha/2)-(\alpha/2-\beta/2-\gamma/2)$
$\displaystyle s.t.~{}~{}$ $\displaystyle\gamma\geq\max\\{\beta,\alpha\\}$
$\displaystyle\cos(A)\geq 1/2$ $\displaystyle(\alpha,\beta,\gamma)\in\Delta.$

Note that in particular $\cos(A)$ is expressed as a function of
$\alpha,\beta,\gamma$, as we also may assume that $\alpha=1$. Then, the
optimal value equals $0$ and is obtained for
$\beta=1/2,\gamma=(1+\sqrt{13})/4\approx 1.15139$, showing that
$T_{1}(\gamma/2-\beta/2)\leq\alpha/2+\beta/2+\gamma/2$.

Lastly, we observe that $T_{2},T_{3}$ are linear functions. When
$x\leq\gamma/2-\beta/2$, then $\max\\{T_{2}(x),T_{3}(x)\\}=T_{3}(x)$ which as
per our argument above, dominates $T_{1}(x)$ (for all
$x\leq\gamma/2-\beta/2$). Also when $x\geq\gamma/2-\beta/2$, then
$\max\\{T_{2}(x),T_{3}(x)\\}=T_{2}(x)$ which as per our argument above,
dominates $T_{1}(x)$ (for all $x\geq\gamma/2-\beta/2$). Our main claim
follows.

###### Lemma 14

Given that $\gamma\geq\alpha\geq\beta$, we have that

$\displaystyle\max_{0\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\max\\{\gamma,\alpha/2+\beta\\}~{}~{}(\textrm{attained
at}~{}x=0,\alpha/2,~{}\textrm{resp.})$ $\displaystyle\min_{0\leq
x\leq\alpha/2}T(x)$
$\displaystyle=\max\left\\{\frac{\alpha+\beta+\gamma}{2},\frac{(\alpha+\gamma)^{2}-\beta^{2}+4\sqrt{3}\tau}{4\gamma}\right\\}$

where $\tau$ is the area of triangle $ABC$, and $\cos(A),\sin(A)$ can be given
by the Cosine Law as functions of $\alpha,\beta,\gamma$. Moreover, the minimum
value of $T(x)$ is attained at $x=\gamma/2-\beta/2$ if $A\leq\pi/3$, and at
$x=\frac{\gamma}{2}-\frac{\beta}{2}\left(\cos(A)+\frac{\sqrt{3}}{3}\sin(A)\right)$
if $A\geq\pi/3$.

###### Proof

First we compute the maximum value of $T(x)$ over $[0,\alpha/2]$. Our analysis
(for the maximum value only) relies on that
$\gamma\geq\max\\{\alpha,\beta\\}$, and hence it also holds for the upper
bound claim of Lemma 15.

$T(x)$ is convex by Lemma 1, so its maximum value is attained either at $x=0$
or at $x=\alpha/2$. Using Lemma 5, we calculate

$T(0)=\alpha/2+\max\\{CR_{1}(0),\beta,\gamma\\}=\alpha/2+\max\\{\alpha,\beta,\gamma\\}=\alpha/2+\gamma,$

as well as

$T(\alpha/2)=\alpha/2+\alpha/2+\max\\{CR_{1}(\alpha/2),\beta,\gamma-\alpha\\}=\alpha+\max\\{CR_{1}(\alpha/2),\beta\\},$

where the last equality is due to that $\gamma-\alpha\leq\beta$, by the
triangle inequality, and $CR_{1}(\alpha/2)$ is given by Lemma 5. Next we argue
that for all triangles in which $\gamma$ is the dominant edge, we have
$CR_{1}(\alpha/2),\beta$. For this we set up the following nonlinear program

$\displaystyle\max$ $\displaystyle~{}~{}CR_{1}(\alpha/2)-\beta$ $\displaystyle
s.t.~{}~{}$ $\displaystyle\gamma\geq\max\\{\alpha,\beta\\}$
$\displaystyle(\alpha,\beta,\gamma)\in\Delta.$

Without loss of generality we may assume that $\alpha=1$, so that the
optimizers of the nonlinear program are of the form $\alpha=\gamma=1$, and
$\beta\leq\gamma$, giving maximum value $0$. Hence,
$CR_{1}(\alpha/2)\leq\beta$. We conclude that $T(\alpha/2)=\alpha+\beta$, so
that $\max_{0\leq x\leq\alpha/2}T(x)=\alpha/2+\max\\{\gamma,\alpha/2+\beta\\}$
attained at $x=0,\alpha/2$, respectively.

Next we calculate the lower bound. Note that $\alpha$ is the second largest
edge, and hence $A$ is the second largest angle of $ABC$. We examine two
cases.

In the first case, we assume that $A\leq\pi/3$. Then, Lemma 13 applies,
according to which $T(x)=\alpha/2+x+\max\\{\beta,\gamma-2x\\}$. Then we
observe that $\beta=\gamma-2x$ at $x_{0}=\gamma/2-\beta/2\leq\alpha/2$ (due to
the triangle inequality), and hence $T(x)$ is minimized at $x_{0}$. It is also
easy to see that $T(x_{0})=\alpha/2+\beta/2+\gamma/2$.

In the second case we assume that $A\geq\pi/3$. Let also
$T_{1}(x)=\alpha/2+x+CR_{1}(x)$. We show that the minimum of $T(x)$ over
$[0,\alpha/2]$ is the minimum of $T_{1}(x)$ in the same interval. For this, we
also set $T_{2}(x)=\alpha/2+\beta+x$ and $T_{3}(x)=\alpha/2+\gamma-x$ (and
note that $T(x)=\max\\{T_{1}(x),T_{2}(x),T_{3}(x)\\}$).

We compute some important values of $x$. First, we see that
$T_{1}(x)=T_{3}(x)$ at
$x_{1}:=\frac{(\gamma^{2}-\alpha^{2})\gamma}{2(\beta^{2}+\gamma^{2}-\alpha^{2})}$
as well as that $T_{1}(x)=T_{2}(x)$ at
$x_{2}:=\frac{(\alpha+\beta)(\alpha-\beta)}{2\gamma}$ (we also have
$T_{1}(\gamma/2)=T_{2}(\gamma/2)$, but this solution is rejected because
$x\leq\alpha/2$ and $\gamma\geq\max\alpha$). Since $T_{1}(0)\leq T_{3}(0)$, it
follows that $T_{1}(x)\geq T_{3}(x)$, for all $x\geq x_{1}$. Moreover, since
$T_{1}(\alpha/2)\leq T_{2}(\alpha/2)$, it follows that $T_{1}(x)\geq
T_{2}(x)$, for all $x\leq x_{2}$.

The next claim is that $x_{1}\leq\gamma/2-\beta/2\leq x_{2}$. For this, we
consider the nonlinear programs

$\displaystyle\max$ $\displaystyle~{}~{}f_{i}$ $\displaystyle s.t.~{}~{}$
$\displaystyle\gamma\geq\alpha\geq\beta$ $\displaystyle\cos(A)\leq 1/2$
$\displaystyle(\alpha,\beta,\gamma)\in\Delta.$

where $f_{1}=x_{1}-(\gamma/2-\beta/2)$ (when $i=1$) and
$f_{2}=(\gamma/2-\beta/2)-x_{2}$ (when $i=2$). Both of the non-linear programs
can be solved analytically using software for symbolic calculations. Without
loss of generality we assume that $\alpha=1$, so that both non linear programs
attain the maximum value $0$ and the maximizers are
$\alpha=1,\beta=\frac{1}{128}\left(69-\sqrt{2101}\right),\gamma=\frac{69}{64}$
, and $\alpha=1,\beta=\frac{1}{2},\gamma=\frac{1}{4}\left(\sqrt{13}+1\right)$,
for $i=1,2$, respectively. We conclude that $x_{1}\leq\gamma/2-\beta/2\leq
x_{2}$.

It follows that, when $A\geq\pi/3$, we have that $T(x)=T_{1}(x)$ for all
$x\in[x_{1},x_{2}]$. Next we show that the minimizer $y$ of $T_{1}(x)$ lies in
the interval $[x_{1},x_{2}]$. But then, that would mean that $y$ is a local
minimizer for $T(x)$ too. Since also by Lemma 1 $T(x)$ is convex, it follows
that $\min_{0\leq x\leq\alpha/2}T(x)=T(y)$. So it remains to find $y$, and
show that $y\in[x_{1},x_{2}]$ as promised.

To that end, we compute the critical values of $T_{1}(x)$ in $[0,\alpha/2]$,
by solving $T_{1}^{\prime}(x)=0$. The solution to the latter equation are

$y_{1,2}=\frac{\gamma}{2}-\frac{\beta}{2}\left(\cos(A)\pm\frac{\sqrt{3}}{3}\sin(A)\right).$

It is easy to see that when $A\geq\pi/3$, we have that
$\cos(A)-\frac{\sqrt{3}}{3}\sin(A)\leq 0$, and that means that
$y_{2}\geq\gamma/2$. Since also the domain of $T(x)$ is $[0,\alpha/2]$ and
$\gamma\geq\alpha$, we conclude that the minimizer of $T_{1}(x)$ is attained
at $x=y_{1}$. Finally, we calculate

$\displaystyle T_{1}(y_{1})$
$\displaystyle=\frac{\alpha}{2}+\frac{\gamma}{2}+\frac{\beta}{2}\left(\sqrt{3}\sin(A)-\cos(A)\right)$
$\displaystyle=\frac{\sqrt{3}\sqrt{-((\alpha-\beta-\gamma)(\alpha+\beta-\gamma)(\alpha-\beta+\gamma)(\alpha+\beta+\gamma))}+(\alpha+\gamma)^{2}-\beta^{2}}{4\gamma}$

Recalling Heron's formula $\sqrt{p(p-\alpha)(p-\beta)(p-\gamma)}$ for the area
$\tau$ of a triangle with half perimeter $p$, gives the promised lower bound
when $A\geq\pi/3$.

To conclude, we showed that

$\min_{0\leq
x\leq\alpha/2}T(x)=\left\\{\begin{array}[]{ll}\alpha/2+\beta/2+\gamma/2&~{},\textrm{
if}~{}A\leq\pi/3\\\
\frac{(\alpha+\gamma)^{2}-\beta^{2}+4\sqrt{3}\tau}{4\gamma}&~{},\textrm{
if}~{}A\geq\pi/3\end{array}\right.$

The claim of the lemma follows by verifying that, as long as
$\gamma\geq\alpha\geq\beta$ we have that

$\frac{\alpha+\beta+\gamma}{2}\geq\frac{(\alpha+\gamma)^{2}-\beta^{2}+4\sqrt{3}\tau}{4\gamma}$

if and only if $A\leq\pi/3$, i.e. if and only if $\cos{A}\geq 1/2$.

###  5.7 The case $\gamma\geq\beta\geq\alpha$

As in the previous section, the domain of our function in Configuration 1 is
either empty, or it is covered by Configuration 2 (when $\alpha=\gamma$).

Next we move to Configuration 2. Recall that $x\leq\alpha/2$, and since this
configuration happens only when $x\leq\gamma/2$ and $\gamma\geq\alpha$ we need
to determine the extreme values of

$T(x)=\alpha/2+x+\max\\{CR_{1},\beta,\gamma-2x\\},$

in the interval $x\in[0,\alpha/2]$.

###### Lemma 15

Given that $\gamma\geq\beta\geq\alpha$, we have that

$\displaystyle\max_{0\leq x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\max\\{\gamma,\alpha/2+\beta\\}~{}~{}(\textrm{attained
at}~{}x=0,\alpha/2,~{}\textrm{resp.})$ $\displaystyle\min_{0\leq
x\leq\alpha/2}T(x)$
$\displaystyle=\alpha/2+\beta/2+\gamma/2~{}~{}(\textrm{attained
at}~{}x=(\gamma-\beta)/2),$

###### Proof

The argument for the upper bound is given in the proof of Lemma 14 (which
holds as long as $\gamma\geq\max\\{\alpha,\beta\\}$. Next we provide the lower
bound relying specifically on that $\gamma\geq\beta\geq\alpha$. Note that the
latter inequality shows that $A$ is the smallest angle in $ABC$, and hence
$A\leq\pi/3$. But then, Lemma 13 applies according to which
$T(x)=\alpha/2+x+\max\\{\beta,\gamma-2x\\}$. Then we observe that
$\beta=\gamma-2x$ at $x_{0}=\gamma/2-\beta/2\leq\alpha/2$ (due to the triangle
inequality), and hence $T(x)$ is minimized at $x_{0}$. It is also easy to see
that $T(x_{0})=\alpha/2+\beta/2+\gamma/2$.

##  6 Evacuation Cost Bounds Starting from Anywhere on the Perimeter

For evacuation algorithm OppositeSearch, and for each $i\in\\{a,b,c\\}$, we
denote by $l_{i}(a,b,c)$ and $u_{i}(a,b,c)$ the smallest possible and largest
possible worst-case evacuation cost, respectively, when the evacuation
algorithm is restricted to start agents anywhere on edge $i$ (where the worst-
case cost is over all placements of the exit). From the definition of the four
algorithmic problems we introduced we have that

$\displaystyle\underline{\mathcal{L}}(a,b,c)$
$\displaystyle\leq\min_{i\in\\{a,b,c\\}}l_{i}(a,b,c)~{}~{}\textit{(Overall
smallest worst-case cost)}$ $\displaystyle\overline{\mathcal{L}}(a,b,c)$
$\displaystyle\leq\max_{i\in\\{a,b,c\\}}l_{i}(a,b,c)~{}~{}\textit{(Worst
starting-edge for best starting-point worst-case cost)}$
$\displaystyle\underline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq\min_{i\in\\{a,b,c\\}}u_{i}(a,b,c)~{}~{}\textit{(Best
starting-edge for worst starting-point worst-case cost)},$
$\displaystyle\overline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq\max_{i\in\\{a,b,c\\}}u_{i}(a,b,c)~{}~{}\textit{(Overall
largest worst-case cost)}$

In this section we are concerned with the exact evaluation of $l_{i}(a,b,c)$
and $u_{i}(a,b,c)$ of algorithm OppositeSearch, i.e. the smallest possible and
highest possible worst-case evacuation cost, respectively, when starting
anywhere on edge $i\in\\{a,b,c\\}$ of a non-obtuse triangle $ABC$, where
$a\geq b\geq c$. Recall that the analysis we performed in Section 5 was for
the smallest possible and highest possible worst-case evacuation cost on a
triangle with edges $\alpha,\beta,\gamma$ (of arbitrary relevant lengths).
Moreover, the setup configuration was that the agents' starting point was
always on the half segment of edge $\alpha$, that was closer to the
intersection of $\gamma$ with $\alpha$, than to the intersection of $\beta$
with $\alpha$.

###### Lemma 16

For the smallest and largest possible worst-case evacuation cost of
OppositeSearch, when starting from the largest edge $a$, we have

$\displaystyle l_{a}(a,b,c)$
$\displaystyle=\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}$
$\displaystyle u_{a}(a,b,c)$ $\displaystyle=\frac{a}{2}+b+\frac{c}{2},$

where $\tau$ is the area of the given triangle.

###### Proof

In this case we start on edge $a$, which is the same as starting on edge
$\alpha$ in our previous analysis. Hence, we set $\alpha=a$. The starting
point on $a$ can be either closer to the intersection of $a$ with $c$ or close
to the intersection of $a$ with $b$.

When the starting point is closer to the intersection of $a$ with $c$ (i.e.
closer to $B$), and since $a\geq b\geq c$, the best possible and worst
possible worst-case costs are given by Lemma 6 and Lemma 7, with the
assignment of $\alpha=a,\beta=b,\gamma=c$. On the other hand, if the starting
point is closer to the intersection of $a$ with $b$ (i.e. closer to $C$), then
the best possible and worst possible worst-case costs are given by Lemma 8 and
Lemma 9, with the assignment of $\alpha=a,\beta=c,\gamma=b$.

Therefore, we have

$l_{a}(a,b,c)=\min\left\\{b+c,\frac{a^{2}-b^{2}+ac+2bc}{2c},c+b,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}.$

We claim that
$\frac{a^{2}-b^{2}+ac+2bc}{2c}\geq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}$,
for all non-obtuse triangles. To see why, we note that

$\displaystyle\frac{a^{2}-b^{2}+ac+2bc}{2c}-\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}$
$\displaystyle=$
$\displaystyle\frac{-c\sqrt{6a^{2}\left(b^{2}+c^{2}\right)-3a^{4}-3\left(b^{2}-c^{2}\right)^{2}}+a^{2}(2b-c)+3b^{2}c-2b^{3}+c^{3}}{4bc}.$

It can be seen that $-2b^{3}+a^{2}(2b-c)+3b^{2}c+c^{3}\geq 0$, so that it
suffices to show that the next expression is non-negative

$\displaystyle\left(-2b^{3}+a^{2}(2b-c)+3b^{2}c+c^{3}\right)^{2}-c^{2}\left(6a^{2}\left(b^{2}+c^{2}\right)-3a^{4}-3\left(b^{2}-c^{2}\right)^{2}\right)$
$\displaystyle=$
$\displaystyle(-a^{2}+b^{2}-bc+c^{2})(b^{4}-2b^{3}c+bc^{3}+c^{4}-a^{2}(b^{2}-bc+c^{2})).$

Our claim then follows by showing that $-a^{2}+b^{2}-bc+c^{2}\leq 0$ and
$b^{4}-2b^{3}c+bc^{3}+c^{4}-a^{2}(b^{2}-bc+c^{2})\leq 0$, concluding that

$l_{a}(a,b,c)=\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}$

Now for calculating $u_{a}(a,b,c)$, and as described before, we invoke Lemma 6
and Lemma 7 with $\alpha=a,\beta=b,\gamma=c$, and Lemma 8 and Lemma 9 with
$\alpha=a,\beta=c,\gamma=b$. Taking the maximum of all expressions, we have

$u_{a}(a,b,c)=\max\left\\{\frac{a}{2}+b+\frac{c}{2},\frac{3a}{2},\frac{a}{2}+b+\frac{c}{2},\frac{a}{2}+c+\frac{b}{2},\frac{3a}{2}\right\\}=\frac{a}{2}+\max\left\\{a,b+\frac{c}{2}\right\\},$

where the last simplification is due to that $a\geq b\geq c$. Now taking into
consideration that the given triangle is non-obtuse, one case show that $a\leq
b+c/2$, concluding that $u_{a}(a,b,c)=\frac{a}{2}+b+\frac{c}{2}$.

It is worthwhile mentioning here that $l_{a}(a,b,c)$ cannot be further
simplified. Indeed, for $a=\sqrt{2},b=c=1$, the formula is given by
$l_{a}(a,b,c)=b+c=2$. On the other hand, when $a=b=c=1$, we have that
$l_{a}(a,b,c)=\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}=3/2$ (while formula
$b+c$ would evaluate to 2).

###### Lemma 17

For the smallest and largest possible worst-case evacuation cost of
OppositeSearch, when starting from the second largest edge $b$, we have

$\displaystyle l_{b}(a,b,c)$
$\displaystyle=\max\left\\{\frac{a+b+c}{2},\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\}$
$\displaystyle u_{b}(a,b,c)$ $\displaystyle=a+\frac{b}{2}+\frac{c}{2},$

where $\tau$ is the area of the given triangle.

###### Proof

In this case we start on edge $b$, either close to point $A$ (intersection of
edges $b,c$) or to point $C$ (intersection of edges $a,b$). When starting
closer to $A$, the incident edge is $c$, which in our case is the smallest
edge. Therefore, the best possible and worst possible worst-case costs in this
case are given by Lemma 10 and Lemma 11 with $a=\beta,b=\alpha$ and
$c=\gamma$, i.e. for our analysis in which $\beta\geq\alpha\geq\gamma$. On the
other hand, when we start close to vertex $C$, the incident edge is $a$, which
is the largest edge in the triangle. Therefore, the best possible and worst
possible worst-case costs in this case are given by Lemma 14 with
$a=\gamma,b=\alpha$ and $c=\beta$, i.e. for our analysis in which
$\gamma\geq\alpha\geq\beta$.

Towards computing $l_{b}(a,b,c)$ we need to evaluate the minimums of all lower
bounds given by the previous theorems (under the underlying interpretation of
$\alpha,\beta,\gamma$). A direct application of the lemmata gives

$l_{b}(a,b,c)=\min\left\\{a+c,\frac{b}{2}+a,\max\left\\{\frac{a+b+c}{2},\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\}\right\\}$
(1)

We proceed with a simplification of the previous expression.

As per the arguments in the proof of Lemma 14, we have that

$\max\left\\{\frac{a+b+c}{2},\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\}=\left\\{\begin{array}[]{ll}\frac{a+b+c}{2}&~{},\textrm{
if}~{}B\leq\pi/3\\\ \frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}&~{},\textrm{
if}~{}B\geq\pi/3\end{array}\right.$

Therefore towards analyzing (1), we examine the cases $B\leq\pi/3$ and
$B>\pi/3$. When $B\leq\pi/3$, we have that

$l_{b}(a,b,c)=\min\left\\{a+c,\frac{b}{2}+a,\frac{a+b+c}{2}\right\\}=\frac{a+b+c}{2},$

where the last simplification is due to that $a\geq b\geq c$. When $B>\pi/3$,
we have that

$l_{b}(a,b,c)=\min\left\\{a+c,\frac{b}{2}+a,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\},$

Recall that in this case we have $\cos(B)\leq 1/2$ and that $a\geq b\geq c$
and $(a,b,c)\in\Delta$ (for the edges to form a triangle). Under these
constraints, one can form non-linear programs and verify that

$a+c\geq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a},~{}~{}\textrm{and}~{}~{}\frac{b}{2}+a\geq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a},$

as promised (where the inequalities become tight for $a=b=1,c=0$ and
$a=b=c=1$, respectively).

Towards computing $l_{b}(a,b,c)$ we need to evaluate the minimums of all lower
bounds given by the previous theorems (under the underlying interpretation of
$\alpha,\beta,\gamma$). A direct application of the lemmata gives

$u_{b}(a,b,c)=\max\left\\{\frac{b}{2}+a+\frac{c}{2},\frac{b}{2}+a,b+c\right\\}=a+\frac{b}{2}+\frac{c}{2},$

where the last simplification is due to that $a\geq b\geq c$.

We note that the formula for $l_{b}(a,b,c)$ simplifies to a simpler formula
(one of the arguments of $\max\\{\cdot\\}$) depending on whether $B\geq\pi/3$
or not).

###### Lemma 18

For the smallest and largest possible worst-case evacuation cost of
OppositeSearch, when starting from the smallest edge $c$, we have

$\displaystyle l_{c}(a,b,c)$ $\displaystyle=\frac{a+b+c}{2}$ $\displaystyle
u_{c}(a,b,c)$ $\displaystyle=a+c.$

###### Proof

The starting edge here is $c$, which plays the role of edge $\alpha$ in our
original analysis of Section 5. There are two cases to consider. Either the
starting point is close to $A$ (intersection of $c$ and $b$), or it is closer
to $B$ (intersection of $a$ and $c$).

When starting from the a point on $c$ closer to $A$, we start closer to the
incident edge $b$, which is the second largest edge in the given triangle.
Since in the analysis of Section 5 we always start closer to the intersection
point with edge $\gamma$, it follows that the best possible and worst possible
worst-case costs in this case are given by Lemma 12, setting
$a=\beta,b=\gamma,c=\alpha$ (i.e. the case $\beta\geq\gamma\geq\alpha$).

When starting from the a point on $c$ closer to $B$, we start closer to the
incident edge $a$, which is the largest edge in the given triangle. Since in
the analysis of Section 5 we always start closer to the intersection point
with edge $\gamma$, it follows that the best possible and worst possible
worst-case costs in this case are given by Lemma 15, setting
$a=\gamma,b=\beta,c=\alpha$ (i.e. the case $\gamma\geq\beta\geq\alpha$).

Towards computing $l_{c}(a,b,c)$ we evaluate the minimum of all lower bounds
given by the previous lemmata (under the underlying interpretation of
$\alpha,\beta,\gamma$). A direct application of the lemmata gives

$l_{c}(a,b,c)=\min\left\\{\frac{c}{2}+a,\frac{a+b+c}{2}\right\\}=\frac{a+b+c}{2},$

where the last simplification is due to that $a\geq b\geq c$.

Similarly, towards computing $u_{c}(a,b,c)$ we evaluate the maximum of all
upper bounds given by the previous lemmata (under the underlying
interpretation of $\alpha,\beta,\gamma$). A direct application of the lemmata
gives

$u_{c}(a,b,c)=\max\left\\{c+a,\frac{c}{2}+a,c+b\right\\}=a+c,$

where the last simplification is due to that $a\geq b\geq c$.

We are now ready to prove the upper bounds of
$\underline{\mathcal{L}}(a,b,c),\overline{\mathcal{L}}(a,b,c),\underline{\mathcal{U}}(a,b,c)$
and $\overline{\mathcal{U}}(a,b,c)$ as stated in Theorem 3.1

######  Proof (Proof of the Upper bounds of Theorem 3.1)

By Lemmata 16, 17 and 18, we know all $l_{i}(a,b,c),u_{i}(a,b,c)$ for
$i\in\\{a,b,c\\}$. Therefore we compute

$\displaystyle\overline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq\max_{i\in\\{a,b,c\\}}u_{i}(a,b,c)$
$\displaystyle=\max\left\\{\frac{a}{2}+b+\frac{c}{2},a+\frac{b+c}{2},a+c\right\\}$
$\displaystyle=a+a+\frac{b+c}{2}.$

We also have

$\displaystyle\underline{\mathcal{U}}(a,b,c)$
$\displaystyle\leq\min_{i\in\\{a,b,c\\}}u_{i}(a,b,c)$
$\displaystyle=\min\left\\{\frac{a}{2}+b+\frac{c}{2},a+\frac{b+c}{2},a+c\right\\}$
$\displaystyle=\min\left\\{\frac{a}{2}+b+\frac{c}{2},a+c\right\\}$

Next we calculate $\min_{i\in\\{a,b,c\\}}l_{i}(a,b,c)$, which is an upper
bound to $\underline{\mathcal{L}}(a,b,c)$. By the already established results,
we have that

$\underline{\mathcal{L}}(a,b,c)\leq\min\left\\{\begin{array}[]{l}b+c\\\
\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\\\ \frac{a+b+c}{2}\\\
\max\left\\{\frac{a+b+c}{2},\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\}\end{array}\right.=\min\left\\{\begin{array}[]{l}b+c\\\
\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\\\ \frac{a+b+c}{2}\\\
\end{array}\right.=\min\left\\{\begin{array}[]{l}\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\\\
\frac{a+b+c}{2}\\\ \end{array}\right.,$

where the last equality is due to that $b+c\geq(a+b+c)/2$, by the triangle
inequality.

Next we show that
$\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\geq\frac{a+b+c}{2}$, which will
conclude our claim about $\underline{\mathcal{L}}(a,b,c)$ (but we will use
this inequality in our last argument too). To see why we calculate

$\displaystyle\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}-\frac{a+b+c}{2}$
$\displaystyle=\frac{a^{2}+\sqrt{3}\sqrt{-((a-b-c)(a+b-c)(a-b+c)(a+b+c))}-(b+c)^{2}}{4b}.$

Clearly it is enough to show that the next expression is non-negative

$3(b+c-a)(a+b-c)(a-b+c)(a+b+c)-\left((a+b)^{2}-c^{2}\right)^{2}=4(b+c-a)(a+b+c)\left(a^{2}-b^{2}+bc-c^{2}\right).$

The last expression is indeed non-negative, since $b+c-a\geq 0$ by the
triangle inequality, and since by the Cosine Law
$a^{2}-b^{2}+bc-c^{2}=bc(1-2\cos(A))\geq 0$, where the last inequality is
because $a$ is the largest edge, hence $A\geq\pi/3$, hence $\cos(A)\leq 1/2$.

Finally, we calculate $\max_{i\in\\{a,b,c\\}}l_{i}(a,b,c)$, which is an upper
bound to $\overline{\mathcal{L}}(a,b,c)$. For this, we have

$\overline{\mathcal{L}}(a,b,c)\leq\max\left\\{\begin{array}[]{l}\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}\\\
\frac{a+b+c}{2}\\\
\max\left\\{\frac{a+b+c}{2},\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\right\\}\end{array}\right.=\max\left\\{\begin{array}[]{l}\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}\\\
\frac{a+b+c}{2}\\\ \frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\end{array}\right.$

From the discussion above we know that $b+c\geq(a+b+c)/2$ and

$\frac{a+b+c}{2}\leq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b},$

and hence
$(a+b+c)/2\leq\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}$.
So, we have

$\overline{\mathcal{L}}(a,b,c)\leq\max\left\\{\begin{array}[]{l}\min\left\\{b+c,\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\right\\}\\\
\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}\end{array}\right..$

Lastly, we recall that $a\geq b$, and hence
$\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4b}\geq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}$.
Our main claim pertaining to $\overline{\mathcal{L}}(a,b,c)$ will follow once
we show that $b+c\geq\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}$. To that end we
we consider the non-linear program

$\displaystyle\min$
$\displaystyle~{}~{}(b+c)-\frac{(a+b)^{2}-c^{2}+4\sqrt{3}\tau}{4a}$
$\displaystyle s.t.~{}~{}$ $\displaystyle a=1$
$\displaystyle(a,b,c)\in\Delta.$

whose optimal value is 0, attained among others at $a=b=1,c=0$.

##  7 Lower Bounds

This section is concerned with proving the lower bounds of
$\underline{\mathcal{L}}(a,b,c),\overline{\mathcal{L}}(a,b,c),\underline{\mathcal{U}}(a,b,c)$
and $\overline{\mathcal{U}}(a,b,c)$ as stated in Theorem 3.1.

######  Proof (Proof of the Lower bounds of Theorem 3.1)

In all our arguments below, we denote by $A,B,C$ the vertices opposite to
edges $a\geq b\geq c$, respectively.

#### The lower bound of $\underline{\mathcal{L}}(a,b,c)$:

The proof follows by observing that $(a+b+c)/2$ is half the perimeter of the
geometric object where the exit is hidden. Indeed, consider any algorithm for
the triangle evacuation problem, where agents can possibly choose even
distinct starting location on the perimeter of the given triangle. In time
$(a+b+c)/2-\epsilon/2$, the two agents can search at most $a+b+c-\epsilon$,
and hence there will also be, at that moment, an unexplored point. In other
words, for every $\epsilon>0$, the evacuation time is at least
$(a+b+c)/2-\epsilon$.

#### The lower bound of $\overline{\mathcal{L}}(a,b,c)$:

In this problem, the adversary chooses a starting edge, and then the algorithm
may deploy the two robots on any point on that edge before attempting to
evacuate the given triangle (from an exit that is again chosen by the
adversary). An adversary who also allows the algorithm to choose the starting
edge is even weaker, and therefore the lower bound of
$\underline{\mathcal{L}}(a,b,c)$ is a lower bound to
$\overline{\mathcal{L}}(a,b,c)$ too.

#### The lower bound of $\underline{\mathcal{U}}(a,b,c)$:

Recall that in the underlying algorithmic problem, the algorithm chooses the
starting edge, while the adversary chooses the starting point on the edge. So
we consider some cases as to which starting edge an algorithm may choose. If
the starting edge is either $b$ or $c$, then the adversary can choose starting
point $A$. Consequently, the adversary can wait until at the first among $B,C$
is visited, and place the exit in the other vertex (the argument works even if
vertices are visited simultaneously). But then, the evacuation time would be

$\min\\{AB,AC\\}+BC=\min\\{b,c\\}+a=c+a.$

In the last case, the algorithm may choose to start from edge $a$. In that
case the adversary may choose strarting point $D$ which is $(a-c)/2$ away from
$B$, i.e. for which $BD=(a-c)/2$ and $DC=(a+c)/2$. For that starting point, an
adversary can wait until the first vertex among $A,C$ is visited. If $C$ is
the first (which happens at time at least $DC=(a+c)/2$), the exit can be
placed at $A$, then the induced running time would be at least $b+(a+c)/2$.
Overall that would mean that the performance of the arbitrary algorithm would
be $\min\\{c+a,b+(a+c)/2\\}$, which also equals our upper bound. If, on the
other hand, $A$, is visited before $C$, then that can happen in time at least

$AD=\left(c^{2}+(a-c)^{2}/4-c(a-c)\cos\left({B}\right)\right)^{1/2},$

where also $\cos(B)=\frac{-b^{2}+a^{2}+c^{2}}{2ac}$ (note that $AD\leq(a+c)/2$
by the triangle inequality). Then, placing the exit at $C$ induces evacuation
time at least $AD+b$. Overall, since the algorithm can choose the starting
edge, the induced lower bound to $\underline{\mathcal{U}}(a,b,c)$ is at least

$\min\\{a+c,AD+b\\}=\min\left\\{a+c,\frac{1}{2}\sqrt{\frac{2b^{2}(a-c)-(a-2c)(a+c)^{2}}{a}}+b\right\\}.$

If we call the latter expression $f(a,b,c)$, then a Non-Linear Program can
establish that

$f(a,b,c)\geq\frac{1}{10}\left(\sqrt{10}+5\right)\min\\{c+a,b+(a+c)/2\\}$

(over all triangles with $A\leq\pi/2$), meaning that our lower bound is off by
at most $\left(\sqrt{10}+5\right)\approx 0.816228$ from our upper bound. By
letting also denote by $h(t)$ the smallest ratio
$f(a,b,c)/\min{c+a,b+(a+c)/2}$ (over all triangles non-obtuse triangles)
condition on that $c/a=t\in(0,1]$, we can also derive that our lower bound is
much better than $0.816228$ times our upper bound, for the various values of
$t$, see Figure 2

Figure 2: The plot of
$h(t)=\min_{(a,b,c)\in\Delta}f(a,b,c)/\min\\{c+a,b+(a+c)/2\\}$ that quantifies
how far away is our lower bound from the derived upper bound to
$\underline{\mathcal{U}}(a,b,c)$, as a function of $c/a\in(0,1]$.

#### The lower bound of $\overline{\mathcal{U}}(a,b,c)$:

For this problem, the adversary can choose the agents' starting point on the
perimeter of the triangle $ABC$. Consider the starting point $D$, on edge $b$,
such that $AD=(b-c)/2$, and note that by the Cosine Law in triangle $ADB$ we
have that

$BD=\left(c^{2}+(b-c)^{2}/4-c(b-c)\cos\left({A}\right)\right)^{1/2}$

where also $\cos(A)=\frac{-a^{2}+b^{2}+c^{2}}{2bc}$ (note that $BD\leq(b+c)/2$
by the triangle inequality). Now, with starting point $D$, we let an arbitrary
algorithm run until the first point among $B,C$ is visited (our argument works
even if the points are visited simultaneously). If $C$ is visited first, and
since $DC=(b+c)/2$, this does not happen before time $(b+c)/2$, and so by
placing the exit at $B$, the evacuation time would be at least $a+(b+c)/2$
(and that would be equal to the established upper bound). If on the other hand
$B$ is discovered before $C$, then we can place the exit $C$ (when $B$ is
visited by any robot), and that would induce running time at least

$BD+a=\frac{1}{2}\sqrt{\frac{2a^{2}(b-c)-(b-2c)(b+c)^{2}}{b}}+a.$

If we call the last expression $f(a,b,c)$, then a Non-Linear Program can
establish that $f(a,b,c)\geq 0.852\left(a+\frac{b+c}{2}\right)$1110.852 is the
third smallest (also second largest) real root of polynomial
$20x^{6}-68x^{5}+671x^{4}-2776x^{3}+2550x^{2}-516x-25$ (the polynomial has 4
real and 2 complex roots).. By denoting the smallest ratio
$f(a,b,c)/\left(a+\frac{b+c}{2}\right)$ (over all triangles) condition on that
$c/b=t\in(0,1]$ as $h(t)$, we can also derive that our lower bound is much
better than $0.852$ times our upper bound, for the various values of $t$, see
Figure 3.

Figure 3: The plot of
$h(t)=\min_{(a,b,c)\in\Delta}f(a,b,c)/\left(a+\frac{b+c}{2}\right)$ that
quantifies how far away is our lower bound from the derived upper bound to
$\overline{\mathcal{U}}(a,b,c)$, as a function of $c/b\in(0,1]$.

##  8 Discussion

We provided upper and lower bounds to the 2 searcher evacuation problem from
triangles in the wireless model, extending results previously known only for
equilateral triangles. Our main contribution is a technical analysis of a
plain-vanilla algorithm that has been proven to be optimal for various search
domains in the wireless model. We also provided lower bounds that depending on
the given triangle could range from being tight to having a gap of at most
$.8$ depending on the considered algorithmic problem and the given triangle.
Providing tight upper and lower bounds for the entire spectrum of triangles is
an open problem. We also see the study of the same problem in the face-to-face
model as the next natural direction to consider, but definitely more
challenging.

## References

  * [1] Steve Alpern, Robbert Fokkink, L Gasieniec, Roy Lindelauf, and VS Subrahmanian.  Search Theory: A Game Theoretic Perspective.  Springer, 2013.
  * [2] Steve Alpern and Shmuel Gal.  The Theory of Search Games and Rendezvous.  Kluwer, 2003.
  * [3] R. Baeza Yates, J. Culberson, and G. Rawlins.  Searching in the plane.  Information and Computation, 106(2):234–252, 1993.
  * [4] Ricardo A Baeza-Yates, Joseph C Culberson, and Gregory JE Rawlins.  Searching with uncertainty.  In Scandinavian Workshop on Algorithm Theory, pages 176–189. Springer, 1988.
  * [5] Iman Bagheri, Lata Narayanan, and Jaroslav Opatrny.  Evacuation of equilateral triangles by mobile agents of limited communication range.  In Falko Dressler and Christian Scheideler, editors, ALGOSENSORS 2019, volume 11931 of Lecture Notes in Computer Science, pages 3–22. Springer, 2019.
  * [6] Anatole Beck.  On the linear search problem.  Israel Journal of Mathematics, 2(4):221–228, 1964.
  * [7] R. Bellman.  An optimal search.  SIAM Review, 5(3):274–274, 1963.
  * [8] Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, and Roger Wattenhofer.  Collaboration without communication: Evacuating two robots from a disk.  In International Conference on Algorithms and Complexity, pages 104–115. Springer, 2017.
  * [9] Huda Chuangpishit, Saeed Mehrabi 0001, Lata Narayanan, and Jaroslav Opatrny.  Evacuating equilateral triangles and squares in the face-to-face model.  Comput. Geom, 89:101624, 2020.
  * [10] Huda Chuangpishit, Konstantinos Georgiou, and Preeti Sharma.  A multi-objective optimization problem on evacuating 2 robots from the disk in the face-to-face model; trade-offs between worst-case and average-case analysis.  Information, 11(11):506, 2020.
  * [11] J Czyzowicz, K Georgiou, R Killick, E Kranakis, D Krizanc, L Narayanan, J Opatrny, and S Shende.  Priority evacuation from a disk: The case of $n\geq 4$.  Theoretical Computer Science, 846:91–102, 2020.
  * [12] Jurek Czyzowicz, Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis, and Fraser MacQuarrie.  Evacuating two robots from multiple unknown exits in a circle.  In ICDCN, pages 28:1–28:8. ACM, 2016.
  * [13] Jurek Czyzowicz, Leszek Gasieniec, Thomas Gorry, Evangelos Kranakis, Russell Martin, and Dominik Pajak.  Evacuating robots via unknown exit in a disk.  In Fabian Kuhn, editor, DISC 2014, volume 8784 of Lecture Notes in Computer Science, pages 122–136. Springer, 2014.
  * [14] Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter, and Michal Wlodarczyk.  Evacuation from a disc in the presence of a faulty robot.  In Shantanu Das and Sébastien Tixeuil, editors, SIROCCO 2017, volume 10641 of Lecture Notes in Computer Science, pages 158–173. Springer, 2017.
  * [15] Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende.  Priority evacuation from a disk: The case of n= 1, 2, 3.  Theoretical Computer Science, 806:595–616, 2020.
  * [16] Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Lata Narayanan, Jarda Opatrny, and Birgit Vogtenhuber.  Evacuating Robots from a Disk Using Face-to-Face Communication.  Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 4, August 2020.
  * [17] Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende.  Wireless autonomous robot evacuation from equilateral triangles and squares.  In Symeon Papavassiliou and Stefan Ruehrup, editors, 14th International Conference, ADHOC-NOW, volume 9143 of Lecture Notes in Computer Science, pages 181–194. Springer, 2015.
  * [18] Yann Disser and Sören Schmitt.  Evacuating two robots from a disk: a second cut.  In International Colloquium on Structural Information and Communication Complexity, pages 200–214. Springer, 2019.
  * [19] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors.  Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science.  Springer, 2019.
  * [20] K. Georgiou and W. Jang.  Triangle evacuation of 2 agents in the wireless model.  In 18th International Symposium on Algorithmics of Wireless Networks "(ALGOSENSORS)", to appear, Lecture Notes in Computer Science. Springer, 2022.
  * [21] Konstantinos Georgiou, George Karakostas, and Evangelos Kranakis.  Search-and-fetch with 2 robots on a disk: Wireless and face-to-face communication models.  Discrete Mathematics & Theoretical Computer Science, 21, 2019.
  * [22] Konstantinos Georgiou, Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis, and Ioannis Papaioannou.  Optimal circle search despite the presence of faulty robots.  In Falko Dressler and Christian Scheideler, editors, ALGOSENSORS 2019, volume 11931 of Lecture Notes in Computer Science, pages 192–205. Springer, 2019.
  * [23] Konstantinos Georgiou, Evangelos Kranakis, and Alexandra Steau.  Searching with advice: Robot fence-jumping.  J. Inf. Process, 25:559–571, 2017.
  * [24] Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier, and Somnath Kundu.  Evacuating from $\ell_{p}$ unit disks in the wireless model.  In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 76–93. Springer, 2021.
  * [25] Ryusuke Hohzaki.  Search games: Literature and survey.  Journal of the Operations Research Society of Japan, 59(1):1–34, 2016.
  * [26] Ioannis Lamprou, Russell Martin, and Sven Schewe.  Fast two-robot disk evacuation with wireless communication.  In International Symposium on Distributed Computing, pages 1–15. Springer, 2016.
  * [27] Wolfram Research.  Minimize.  https://reference.wolfram.com/language/ref/Minimize.html, 2021.  Accessed: 19-May-2022.