11institutetext:  Department of Mathematics, Toronto Metropolitan University,
Toronto, ON, Canada 11email<EMAIL_ADDRESS>22institutetext: Department of Computer Science, Toronto Metropolitan
University, Toronto, ON, Canada 22email<EMAIL_ADDRESS>
# The Fagnano Triangle Patrolling Problem ††thanks: Research supported in part
by NSERC. ††thanks:  This is the full version of the paper with the same title
which will appear in the proceedings of the 25th International Symposium on
Stabilization, Safety, and Security of Distributed Systems (SSS’23), October
2-4, 2023, in New Jersey, USA.

Konstantinos Georgiou 11 Somnath Kundu 22 Paweł Prałat 11

###### Abstract

We investigate a combinatorial optimization problem that involves patrolling
the edges of an acute triangle using a unit-speed agent. The goal is to
minimize the maximum (1-gap) idle time of any edge, which is defined as the
time gap between consecutive visits to that edge. This problem has roots in a
centuries-old optimization problem posed by Fagnano in 1775, who sought to
determine the inscribed triangle of an acute triangle with the minimum
perimeter. It is well-known that the orthic triangle, giving rise to a
periodic and cyclic trajectory obeying the laws of geometric optics, is the
optimal solution to Fagnano's problem. Such trajectories are known as Fagnano
orbits, or more generally as billiard trajectories. We demonstrate that the
orthic triangle is also an optimal solution to the patrolling problem.

Our main contributions pertain to new connections between billiard
trajectories and optimal patrolling schedules in combinatorial optimization.
In particular, as an artifact of our arguments, we introduce a novel 2-gap
patrolling problem that seeks to minimize the visitation time of objects every
three visits. We prove that there exist infinitely many well-structured
billiard-type optimal trajectories for this problem, including the orthic
trajectory, which has the special property of minimizing the visitation time
gap between any two consecutively visited edges. Complementary to that, we
also examine the cost of dynamic, sub-optimal trajectories to the 1-gap
patrolling optimization problem. These trajectories result from a greedy
algorithm and can be implemented by a computationally primitive mobile agent.

###### Keywords:

Patrolling Triangle Fagnano Orbits Billiard Trajectories

##  1 Introduction

Patrolling refers to the perpetual monitoring, protection, and supervision of
a domain or its perimeter using mobile agents. In a typical patrolling problem
involving one mobile agent, the agent must move through a given domain in
order to monitor or check specific locations or objects. The objective is to
find a trajectory that satisfies certain constraints and/or that addresses
quantitative objectives, such as minimizing the total distance traveled or
maximizing the frequency of visits to certain areas. The purpose of patrolling
could be to detect any intrusion attempts, monitor for possible faults or to
identify and rescue individuals or objects in a disaster environment, and for
this reason, such problems arise in a variety of real-world applications, such
as security patrol routes, autonomous robot navigation, and wildlife
monitoring. Overall the subject of patrolling has seen a growing number of
applications in Computer Science, including Infrastructure Security, Computer
Games, perpetual domain-surveying, and monitoring in 1D and 2D geometric
domains.

In addition to its practical applications, patrolling has emerged (not as a
combinatorial optimization problem) in the context of theoretical physics. In
particular, the problem of finding periodic trajectories in billiard systems
has been a topic of interest for many years. A billiard system is a model of a
particle or a waveform moving inside a domain (typically polygonal, but also
elliptical, convex, or even non-convex region) and reflecting off its
boundaries according to the laws of elastic collision. The problem of finding
periodic trajectories in a billiard system is equivalent to finding a closed
path in the domain that satisfies certain geometric conditions.

One important example of a periodic trajectory in billiard systems is the so-
called Fagnano orbit on acute triangles, a periodic, closed (and piece-wise
linear) curve that visits the three edges of an acute triangle. Fagnano
orbits, named after the Italian mathematician Giulio Fagnano who first studied
them in the mid-18th century, arise as solutions to the optimization problem
which asks for the shortest such curve. In this work we explore further
connections between billiard trajectories and patrolling as a combinatorial
optimization problem. In particular, we are asking what are the patrolling
strategies for the edges of an acute triangle that optimize standard
frequency-related objectives are. Our findings demonstrate that a family of
Fagnano orbits are actually optimal solutions to the corresponding
combinatorial optimization problems, revealing this way deeper connections
between the seemingly disparate areas of combinatorial patrolling and billiard
trajectories.

##  2 Related Work

Patrolling problems are a fundamental class of problems in computational
geometry, combinatorial optimization, and robotics that have attracted
significant research interest in recent years. Due to their practical
applications, they have received extensive treatment in the realm of robotics,
see for example [1, 6, 14, 15, 21, 30, 40], as well as surveys [3, 22, 34].
When patrolling is seen as part of infrastructure security, it leads to a
number of optimization problems [26], with one particular example being the
identification of network failures or web pages requiring indexing [30].

Combinatorial trade-offs of triangle edge visitation costs have been explored
in [19]. In contrast, the current work pertains to the cost associated with
the perpetual monitoring of the triangle edges by a single unit speed agent.
Numerous variations of similar patrolling problems have been explored in
computational geometry, which vary depending on the application domain,
patrolling specifications, agent restrictions, and computational abilities.
Many efficient algorithms have been developed for several of these variants,
utilizing a range of techniques from graph theory, computational geometry, and
optimization, see survey [10] for some recent developments. Some examples of
studied domains include the bounded line segment [24], networks [41],
polygonal regions [37], trees [11], disconnected boundaries of one dimensional
curves [8], arbitrary polygonal environments [32] (with a reduction to
graphs), or even 3-dimensional environments [16].

Identifying optimal patrolling strategies can be computationally hard [12],
while even in seemingly easy setups the optimal trajectories can be counter-
intuitive [25]. The addition of combinatorial specifications has given rise to
multiple intriguing variations, including the requirement of uneven coverage
[7, 33] or waiting times [13], the presence of high-priority segments [31],
and patrolling with distinct speed agents [9]. Patrolling has also been
studied extensively from the perspective of distributed computing [29], while
the class of these problems also admit a game-theoretic interpretation between
an intruder and a surveillance agent [2, 18].

Maybe not surprisingly, the optimal patrolling trajectories that we derive are
in fact billiard-type trajectories, that is, periodic and cyclic trajectories
obeying the standard law of geometric optics, and which are referred to as
Fagnano orbits specifically when the underlying billiard/domain is triangular.
Fagnano orbits have been studied extensively both experimentally [27] and
theoretically [38]. Billiard-type trajectories have been explored in
equilateral triangles [4], obtuse triangles [20], as well as polygons [39].
More recently, there have been studies on ellipses [17] and general convex
bodies [23], or even fractals [28] and polyhedra [5], with the list of domains
or trajectory specifications still growing.

##  3 Main Definitions and Results

A patrolling schedule $S$ (or simply a schedule) for triangle $\Delta$ with
edges (line segments) $E=\\{\alpha,\beta,\gamma\\}$ is an infinite sequence
$\\{s_{i}\\}_{i\geq 0}$, where each $s_{i}$ is on a line segment of $E$ that
we also denote by $e(s_{i})$, i.e. $e(s_{i})\in E$ for each $i\geq 0$. When
$e(s_{i})=\delta\in E$ we say that segment $\delta$ and point $s_{i}$ are
visited at step $i$ of the schedule. We will only be studying feasible
schedules, i.e. schedules for which eventually all segments in $E$ are visited
(and infinitely often).

For simplicity, our notation above is tailored to points $s_{i}$ that are not
vertices of $\Delta$. When $s_{i}$ is a vertex of $\Delta$ we assume that both
incident edges are visited. We also think of schedule $S$ as the trajectory of
a unit speed agent, and hence we refer to the time between the visitation of
$s_{j},s_{j+\ell}$ as the summation of the lengths of segments
$s_{j+i}s_{j+i+1}$ over $i\in\\{0,\ldots,\ell-1\\}$.

A schedule $S$ is called:
\- cyclic if $\\{e(s_{0}),e(s_{1}),e(s_{2})\\}=E$ and $e(s_{i+3})=e(s_{i})$,
for every $i\geq 0$, and
\- $k$-periodic (for $k\geq 3$) if $s_{i+k}=s_{i}$, for every $i\geq 0$.

For any segment $\delta\in E$ we define its $t$-gap sequence, $g^{t}(\delta)$,
that records the visitation time gaps of $\delta$ over every $t+1$ consecutive
visitations. In particular, $t=1$ corresponds to the standard _idle time_
considered previously, and that measures the additional time it takes for each
object to be revisited, after each visitation. Formally, let
$e(s_{j})=e(s_{j^{\prime}})=\delta$ and suppose that points
$s_{j},s_{j^{\prime}}$ are the $k$-th and $(k+t)$-th visitation of $\delta$,
respectively. Then the time between the visitations of $s_{j},s_{j^{\prime}}$
is exactly the value of $k$-th element of sequence $g^{t}(\delta)$. From this
definition, it is also immediate that
$\left(g^{t}(\delta)\right)_{i}=\sum_{i=1}^{t}\left(g^{1}(\delta)\right)_{i}$.

The $t$-gap $G^{t}(\delta)$ of $\delta\in E$ is defined as
$\sup_{i}\left(g^{t}(\delta)\right)_{i}$, while the $t$-gap $G^{t}$ of
schedule $S$ for edges $E$ (hence for input triangle $\Delta$) is defined as
$\max_{\delta\in E}G^{t}(\delta)$. When it is clear from the context, we will
abbreviate $G^{1}$ simply by $G$.

###  3.1 Main Contributions & More Terminology

In this section we summarize our main contributions, pertaining to the optimal
$1$-gap and $2$-gap patrolling schedules of acute triangles.

As a warm-up, we first give a self-contained proof of optimality for $1$-gap
patrolling schedules, restricted to cyclic and $3$-periodic schedules. In
order to present our result, we remind the reader of the so-called orthic
triangle, a pedal-type triangle of an acute triangle $\Delta$, which is a
triangle inscribed in $\Delta$ whose vertices are the projections of the
$\Delta$'s orthocenter (intersection of altitudes) to its three edges. Note
also the any $3$-periodic cyclic schedule corresponds to a triangle inscribed
in $\Delta$. The next theorem, given first by Fagnano in 1775, is proven in
Section 4, where we also introduce some key concepts for our follow-up main
contributions.

######  Theorem 3.1 (Fagnano's Theorem)

The optimal $1$-gap $3$-periodic cyclic patrolling schedule of a triangle
$\Delta$ is its orthic triangle.

Towards our goal to provide the optimal $1$-gap schedules, we find all
(infinitely many) optimal $2$-gap cyclic schedules, which are in fact
billiard-type trajectories. We prove the next theorem in Section 6.

###### Theorem 3.2

There are infinitely many optimal $2$-gap cyclic schedules of a triangle
$\Delta$, that include also the orthic triangle. Every $2$-gap optimal
schedule is $6$-periodic and has value equal to 2 times the perimeter of the
orthic triangle. Moreover, each optimal schedule is made up of segments that
are parallel to the edges of the orthic triangle.

Then in Section 7 we derive our main contribution.

###### Theorem 3.3

The optimal $1$-gap schedule of a triangle $\Delta$ is its orthic triangle.

In the same section we also quantify the $1$-gap cost of the orthic triangle,
and we compare it to the optimal $2$-gap schedules. Indeed, we ask which of
the optimal $2$-gap schedules minimizes the maximum time in-between the
visitation of any two edges of $\Delta$ (and not of the same edge), and we
prove that the orthic schedule is again the optimal, in this multi-objective
optimization problem.

From our previous contributions, we conclude that a mobile agent whose task is
to $1$-gap optimally patrol a triangle $\Delta$ needs to be able to compute
the base points of $\Delta$'s altitudes. Therefore, a natural question is
whether we can obtain efficient solutions with a primitive agent. In Section 8
we show the following result.

###### Theorem 3.4

There is a greedy-type schedule that converges to a $3$-periodic cyclic
schedule whose $1$-gap cost is off from the $1$-gap optimal cyclic schedule by
a factor $\gamma\in[1,\gamma_{0}]$, where $\gamma_{0}=\sqrt{2}/2+1/2$, and
$\gamma$ admits a closed formula as a function of the angles of the given
triangle.

It will follow from our analysis that our greedy algorithm will be nearly
optimal for any acute triangle with one arbitrarily small angle, and it will
be the worst off from the optimal solution when the given triangle is a right
isosceles.

##  4 The $1$-Gap Optimal $3$-Periodic Cyclic Schedule

There are many proofs known for the fact that inscribed triangle with the
shortest perimeter is its orthic triangle. In the language of triangle
patrolling, the statement is equivalent to that that the optimal $1$-gap
$3$-periodic cyclic schedule of a triangle is its orthic triangle, articulated
in Theorem 3.1. For completeness, we provide next a self-contained proof.

######  Proof (Proof of Theorem 3.1)

We consider triangle $ABC$, as in Figure 1. First we find the inscribed
triangle of minimum perimeter, and then we show the optimizer is the orthic
triangle.

Figure 1: Triangle figure supporting the proof of Fagnano's Theorem.

We start with an arbitrary point $L$ on $AC$, and we find the optimal points
$K,M$ on $BC,AB$, respectively, so as to minimize the perimeter of $KLM$ as a
function of $L$. Then, we show how to choose $L$ so as to minimize the
perimeter.

Consider the reflection $A_{1}$ of $A$ about $BC$, the reflection $C_{1}$ of
$C$ about $AB$, and the reflections $L_{1},L_{2}$ of $L$ about $BC,AB$,
respectively. Consider also the intersections $K,M$ of
$L_{1}{\color[rgb]{1,0,0}\textbf{\textst{,}}}L_{2}$ with $BC,AB$,
respectively. Clearly, the optimal way to start from $L$, visit edge $BC$,
then $AB$ and then return to $L$ is by following the edges of triangle $KLM$.
Moreover, the perimeter of $KLM$ equals segment $L_{1}L_{2}$. Next we minimize
the length of $L_{1}L_{2}$ as a function of $L$.

In this direction, we consider a Cartesian system centered at $B$ where
$A=(p,q),B=(0,0),C=(1,0)$ (in particular, w.l.o.g. we assume that $BC=1$).
Note that $A_{1}=(p,-q),C_{1}=(\cos(2B),\sin(2B))$, where also

$p=\frac{\cos(B)\sin(C)}{\sin(B+C)},~{}~{}q=\frac{\sin(B)\sin(C)}{\sin(B+C)}.$
(1)

Point $L$ is a convex combination of $A,C$, hence there exists $x\in[0,1]$
such that $L=xC+(1-x)A$. Therefore,
$L_{1}=xC+(1-x)A_{1},~{}~{}L_{2}=xC_{1}+(1-x)A,$ so that

$\displaystyle\left\lVert L_{1}-L_{2}\right\rVert^{2}$
$\displaystyle=\left\lVert x(C-C_{1})+(1-x)(A_{1}-A)\right\rVert^{2}$
$\displaystyle=\left\lVert x\left(\begin{array}[]{c}\cos(2B)-1\\\
\sin(2B)\end{array}\right)+(1-x)\left(\begin{array}[]{l}0\\\
2q\end{array}\right)\right\rVert^{2}.$

It follows that $\left\lVert L_{1}-L_{2}\right\rVert^{2}$ is convex in $x$
(degree 2 polynomial), and elementary calculations show that the minimum is
attained at $x_{0}=\frac{\cos(A)\sin(C)}{\sin(B)}.$ It can be seen that for
all acute triangles, we have $x_{0}\in[0,1]$. Then, the minimum patrolling
trajectory has length

$\left\lVert x_{0}(C-C_{1})+(1-x_{0})(A_{1}-A)\right\rVert=2\sin(B)\sin(C).$

Note that the choice of $x_{0}$ determines all points $K,L,M$. Now we show
that $KLM$ is the orthic triangle. In order to show that $K$ is the base of
the altitude corresponding to $A$, we verify that points $(p,0),L_{1},L_{2}$
are collinear (and hence $K=(p,0)$). For this observe that $L_{1},L_{2}$ are
already expressed as a function of $p,q,x_{0}$, and hence the claim follows by
straightforward calculations.

Next we show that $L$ is the base of the altitude corresponding to $B$. For
this we verify that $KL$ is perpendicular to $AC$. Indeed,
$L=x_{0}C+(1-x_{0})A,~{}~{}L_{2}=x_{0}C_{1}+(1-x_{0})A=(x_{0}+(1-x_{0})p,(1-x_{0})q),$
while vector $AC$ is $(1-p,-q)$. Taking the inner product of the vectors gives
$(x_{0}+(1-x_{0})p)(1-p)-(1-x_{0})q^{2}$ which, after elementary calculations
reduces to $0$, as promised.

Finally, we verify that $M$ is the base of the altitude corresponding to $C$.
For this, we compute the projection of $C=(1,0)$ onto the line passing through
$A,B$ which reads as $py-qx=0$, which is point $\frac{p}{p^{2}+q^{2}}(p,q)$.
Finally, elementary calculations can verify that the latter point, together
with $K,L_{2}$ are collinear, and hence $M=\frac{p}{p^{2}+q^{2}}(p,q)$ as
promised. ∎

The next complementary lemma effectively provides a formula for the optimal
$1$-gap cost of cyclic 3-periodic schedules.

###### Lemma 1

Let $p$ be the perimeter of an acute triangle. Then, the perimeter of its
orthic triangle is given by

$2p\left(\frac{1}{\sin(B)\sin(C)}+\frac{1}{\sin(A)\sin(C)}+\frac{1}{\sin(A)\sin(B)}\right)^{-1}.$
(2)

###### Proof

As in the proof of Theorem 3.1 we assume that $A=(p,q),B=(0,0),C=(1,0)$ and
hence that $\alpha=1$. From the derived formulas for the coordinates of points
$K,L,M$ we have that

$\displaystyle\left\lVert K-L\right\rVert$
$\displaystyle=\frac{1}{2}\csc(B+C)\sin(2C)$ $\displaystyle\left\lVert
K-M\right\rVert$ $\displaystyle=\frac{1}{2}\csc(B+C)\sin(2B)$
$\displaystyle\left\lVert K-L\right\rVert$ $\displaystyle=\cos(B+C).$

But then, elementary trigonometric calculations give

$\left\lVert K-L\right\rVert+\left\lVert K-M\right\rVert+\left\lVert
K-L\right\rVert=2\sin(B)\sin(C).$

It follows that for arbitrary edge length $\alpha$ (not necessarily equal to
1), we have that the perimeter of the orthic triangle equals
$X=2\alpha\sin(B)\sin(C)$. Due to the symmetry of the formula, the perimeter
must be also equal to $2\beta\sin(A)\sin(C)$ and to $2\gamma\sin(A)\sin(B)$.
We conclude that

$\alpha=\frac{X}{2\sin(B)\sin(C)},~{}~{}\beta=\frac{X}{2\sin(A)\sin(C)},~{}~{}\gamma=\frac{X}{2\sin(A)\sin(B)}.$

So if we denote by $p$ the perimeter of the given triangle, i.e.
$p=\alpha+\beta+\gamma$, adding the previous equations and solving for $X$
gives the promised formula. ∎

##  5 Technical Properties of the Orthic Patrolling Schedule

In this section we explore a number of technical properties associated with
the orthic patrolling schedule, which will be the cornerstone of our main
results. All observations in this section refer to Figure 2 which we explain
gradually as we present our findings.

Figure 2: The orthic channel (stripe enclosed between the red dotted lines) as
it is obtained by 5 triangle reflections.

Our starting point is triangle $ABC$ with edges $\alpha\geq\beta\geq\gamma$,
and hence the same relation holds for the opposite angles. We also depict the
base points $K,L,K$ of altitudes corresponding to $A,B,C$ respectively. It
follows that inscribed triangle $KLM$ is the orthic triangle.

We apply a number of reflections of triangle $ABC$ as follows: we obtain
reflection $C_{1}$ of $C$ around $AB$, reflection $B_{1}$ of $B$ around
$AC_{1}$, reflection $A_{1}$ of $A$ around $B_{1}C_{1}$, reflection $C_{2}$ of
$C_{1}$ around $A_{1}B_{1}$, and reflection $B_{2}$ of $B_{1}$ around
$A_{1}C_{2}$. We refer to the resulting triangles as the _reflected
triangles_.

###### Lemma 2

The line passing through $B_{2},C_{2}$ is parallel to line passing through
$BC$.

###### Proof

We consider the slope of several line segments relevant to $BC$. We have the
following observations pertaining to counterclockwise rotation of line
segments about one of their endpoints. The rotation of $BC$ about $B$ by angle
$2B$ gives segment $BC_{1}$. The rotation of $BC_{1}$ about $C_{1}$ by angle
$3C$ gives segment $C_{1}A_{1}$. The rotation of $C_{1}A_{1}$ about $A_{1}$ by
angle $3A$ gives segment $A_{1}B_{2}$. Finally, the rotation of $A_{1}B_{2}$
about $B_{2}$ by angle $B$ gives segment $B_{2}C_{2}$.

It follows that segment $B_{2}C_{2}$ follows by repeated rotation of angle
$2B+3C+3A+B=3(A+B+C)=6\pi.$ Since $6\pi$ is a multiple of $\pi$ we conclude
the claim. ∎

Next we provide an alternative representation of the orthic trajectory.

###### Lemma 3

The line passing through MK (green dotted line in Figure 2) passes through the
following points: $L_{1}$ on $AC_{1}$, $K_{1}$ on $B_{1}C_{1}$, $M_{1}$ on
$A_{1}B_{1}$, $L_{2}$ on $A_{1}C_{2}$, and $K_{2}$ on $B_{2}C_{2}$. Moreover,
points $L_{1},K_{1},M_{1},L_{2},K_{2}$ are the bases of corresponding
altitudes in the series of the reflected triangles.

###### Proof

By the proof of Theorem 3.1, the orthic triangle $KLM$ can be obtained by
considering the image $K_{1}$ of $K$ (on $B_{1}C_{1}$) along the same
reflections that resulted into the reflected triangles. Now consider the
intersections $M,L_{1}$ of $KK_{1}$ with $AB,AC_{1}$, respectively. It follows
that $CM$ and $C_{1}M$ are altitudes in triangles $ABC,ABC_{1}$, and $BL_{1}$
and $B_{1}L_{1}$ are altitudes in triangles $ABC_{1},AB_{1}C_{1}$. In
particular, it follows that $K,M,L_{1},K_{1}$ are collinear.

The same argument applies if we start from triangle $AB_{1}C_{1}$ and invoke
the same reflections starting from the third one, in the series that gave us
the reflected triangles. It follows that by extending line $KK_{1}$ we
intersect segment $A_{1}B_{1}$ at a point $M_{1}$, and segment $A_{1}C_{2}$ at
a point $L_{2}$, where $C_{1}M_{1}$ and $C_{2}M_{1}$ are altitudes in
triangles $A_{1}B_{1}C_{1}$, and $B_{1}L_{2}$ is altitudes in triangles
$A_{1}B_{1}C_{2}$. Hence, $L_{2},M_{1},K_{1},L_{1},M,K$ are also collinear.

Finally, we observe that the base $K_{2}$ of altitude $A_{1}K_{2}$ is obtained
as the reflection of $K_{1}$ using the last two reflections of the series of
reflections that gave us the reflected triangles. It follows that $K_{2}$ is
also collinear with $L_{2}$ and $M_{1}$ concluding our argument. ∎

It follows from Lemma 3 that the orthic trajectory along two cycles of the
patrolling schedule can also be described by the line segment $K_{1}K_{2}$. We
refer to the line passing through $K,K_{2}$ as the _orthic line_.
Alternatively, we showed that all points within segment $K_{1}K_{2}$ lie
within the reflected triangles. Our observation justifies that the following
concept is well-defined.

###### Definition 1

The _orthic channel_ is defined by two lines $\ell_{1},\ell_{2}$ parallel to
the orthic line of maximum distance, and with the following properties:
$\ell_{1},\ell_{2}$ intersect segments $BC$ and $B_{2}C_{2}$ and all points on
lines $\ell_{1},\ell_{2}$ in-between segments $BC$ and $B_{2}C_{2}$ lie within
the reflected triangles.

Similar reflection-induced channels were studied in [35, 36], while the
orthic-channel that we use was also observed experimentally in [27]. Next we
formalize its usefulness.

###### Lemma 4

Any line parallel to the orthic line within the orthic channel gives rise to a
cyclic $6$-periodic patrolling schedule with $2$-gap cost equal to twice the
orthic perimeter.

###### Proof

Consider an arbitrary line, parallel to the orthic line, that intersects line
segments $BC,B_{1}C_{1},B_{2}C_{2}$ at points $R,R_{1},R_{2}$ respectively,
see Figure 2. We observe that $KK2$ is parallel to $RR_{2}$, and by Lemma 2 we
have that $K_{2}R_{2}$ is parallel to $KR$. Therefore, $KRR_{2}K_{2}$ is a
parallelogram with $KR=KR_{2}$.

We conclude that $R_{2}$ is the reflection of $R$ using the same reflections
that obtained $K_{2}$ from $K$. But then, it follows $RR_{2}$ corresponds to
cyclic $6$-periodic patrolling schedule of $2$-gap cost equal to
$RR_{2}=KK_{2}=KK_{1}+K_{1}K2=2KK1$, as promised. ∎

Next we identify all cyclic $6$-periodic patrolling schedules of the same
$2$-gap costs. We note that in the following lemma we make explicit use of
that the repeated reflections were done first along the smallest two edges.

###### Lemma 5

The lines identifying the orthic channel are the two lines parallel to the
orthic line, one passing through $A$ and one passing through $A_{1}$.

###### Proof

Consider a line parallel to the orthic line passing through $A$, and
intersecting $BC$ at $T$ and the line passing through $B_{1}C_{1}$ at point
$T_{1}$. We will show that $T_{1}$ lies in the segment $K_{1}B_{1}$.

First we claim that $KT=K_{1}T_{1}$. To see why, recall that $KK_{1}$ is
parallel to $TT_{1}$. It is enough to show that $KTT_{1}K_{1}$ is an isosceles
trapezoid. Indeed, note that angle $AT_{1}C_{1}$ (read counterclockwise)
equals angle $KK_{1}C$ (because $TT_{1}$ is parallel to $KK_{1}$), and angle
$KK_{1}C$ equals angle $BKM$ (because $KK_{1}$ corresponds to the orthic
trajectory that results from reflections). Finally, angle $BKM$ equals angle
$BTT_{1}$, because $TT_{1}$ is parallel to $KK_{1}$. Overall, this shows that
indeed, angles $KTT_{1}$ and $TT_{1}K_{1}$ are equal, showing that
$KTT_{1}K_{1}$ is an isosceles trapezoid as claimed.

We conclude that in order to show that $T_{1}$ lies within segment
$K_{1}B_{1}$ it is enough to show that $KT<KB$. Equivalently, it is enough to
show that the middle point of $BT$ lies within segment $BK$. To see why recall
that $AT$ is parallel to $MK$. Moreover, because angle $A$ is at least as
large as angle $B$ (that is our initial reflections where done using the
largest edge last), it follows that the base $M$ of altitude $CM$ is closer to
$A$ than to $B$. Effectively, this shows that $BM\geq AB/2$, and hence $BK\geq
BT/2$ as wanted.

Now let the extention of $TT_{1}$ intersect the line passing through
$B_{2}C_{2}$ at point $T_{2}$. From the parallelogram $KTT_{2}K_{2}$ we have
that $KT=K_{2}T_{2}$, and hence $T_{2}$ lies within segment $K_{2}C_{2}$, and
by construction is it clear than $T_{1}T_{2}$ intersect segments $A_{1}B1$ and
$A_{1}C_{2}$. This shows that indeed the line passing throught $AT$ is one of
the extreme lines of the orthic channel.

The proof follows by observing that we can repeat the same argument, starting
from triangle $A_{1}B_{2}C_{2}$ and applying the reverse list of reflections
that gave us the reflected triangles (where $ABC$ would be the final reflected
triangle, and note that these reflections would still be first with respect to
the two smallest edges). Indeed, we can consider line, parallel to the orthic
line, and passing through $A_{1}$, which by the same argument that line is the
other extreme line of the orthic channel. ∎

##  6 The Optimal $2$-Gap Cyclic Schedules

In this section we prove Theorem 3.2. We do so by proving that the cyclic
$6$-periodic patrolling schedule of Lemma 4 are the $2$-gap optimal cyclic
schedules of cost twice the perimeter of the orthic triangle.

Indeed, as per our result, any line parallel to the orthic line within the
orthic channel (whose boundaries are given in Lemma 5) gives rise to a cyclic
$6$-periodic schedules that we call _sub-orthic_ schedules. We depict such a
sub-orthic schedule in Figure 3.

Figure 3:  A sub-orthic trajectory example.

In order to show that any sub-orthic trajectory is $2$-gap optimal, we
consider a new patrolling problem on input triangle $ABC$ with a limited
visitation horizon. In particular, in the _$2k$ -limited_ patrolling problem
the goal is to find a cyclic trajectory that starts from edge $BC$ (the
largest edge) ends after $2k$ visitations of $BC$ and is of minimum total
length. Given triangle $ABC$, we denote by $v_{k}$ the cost of the optimal
solution to the _$2k$ -limited_ patrolling problem. The following is immediate
from our definitions.

###### Observation 6.1

For every $k\geq 1$, the optimal cyclic $2$-gap solution has cost at least
$v_{k}/k$.

Now recall that by Lemma 4, any sub-orthic trajectory has $2$-gap cost equal
to twice the orthic triangle. Hence, Theorem 3.2 is a corollary of the
following lemma.

###### Lemma 6

The value of $\lim_{k\rightarrow\infty}v_{k}/k$ equals twice the perimeter of
the orthic triangle.

###### Proof

In order to visualize the _$2k$ -limited_ patrolling problem we apply
repeatedly ($k$ times) the gadget induced by the reflected triangles of
Section 5, see also Figure 4 for an example when $k=2$.

Figure 4:  Two applications of reflections.

Indeed, the gadget of the reflected triangles defines $B_{2}C_{2}$ which is
parallel to $BC$. One more reflection of $A_{1}$ about $B_{2}C_{2}$ results
into triangle $A_{2}B_{2}C_{2}$ whose edges are piecewise parallel to the
edges of $ABC$, hence the same reflection sequence, applied on
$A_{2}B_{2}C_{2}$ defines $B_{3}C_{3}$ parallel to $B_{2}C_{2}$ and so on.

This way, we define a sequence of parallel segments $B_{k}C_{k}$. Now consider
the orthic channel of $ABC$ identified by lines passing through $R,A_{1}$ and
$T,A$ (as per Lemma 5). Consider also the corresponding points $R_{k},T_{k}$
that these two lines intersect segments $B_{k}C_{k}$.

By the definition of the $2k$-limited patrolling problem, its optimal schedule
(with cost $v_{k}$) is the shortest trajectory that starts from $BC$ and ends
at $B_{k}C_{k}$. Since the orthic channel stays within all reflected
triangles, the optimal solution to the $2k$-limited patrolling problem is the
shortest line segment with endpoints within $RT$ and $R_{k}T_{k}$. Observe
that the shortest such segment is the shortest diagonal of parallelogram
$RTT_{k}R_{k}$. Now as $k$ grows, one side $RT$ of these parallelograms stays
constant, while the length of both diagonals tend (in the limit) to the length
of $RR_{k}=TT_{k}$ which are also equal to $k$ times the $2$-gap cost of any
sub-orthic trajectory, and hence are equal to $2k$ times the orthic perimeter.
∎

Note that the orthic trajectory is one among the sub-orthic trajectories, and
hence optimal too to the $2$-gap patrolling problem (among cyclic algorithms).
In the following lemma we show that the orthic trajectory is also the optimal
solution to a multi-objective optimization problem.

###### Lemma 7

Among all $2$-gap optimal sub-orthic trajectories, the one that minimizes the
visitation gap between any two (not necessarily same) edges is the orthic
trajectory.

###### Proof

Consider an arbitrary sub-orthic trajectory $RR_{1}R_{2}R_{3}R_{4}R_{5}R$, see
Figure 3. Note that the sub-orthic schedule is made up of segments that are
piecewise parallel to the segments of the orthic trajectory, and any of the
orthic line segments lies in the middle of any of the two parallel segments of
the sub-orthic schedule.

In particular we have $RR_{1},R_{3}R_{4}$ are parallel to $MK$, as well as
$R_{1}R2,R_{4}R_{5}$ are parallel to $ML$, and $RR_{5},R_{2}R_{3}$ are
parallel to $KL$. Moreover,
$MK\leq\max\\{RR_{1},R_{3}R_{4}\\},ML\leq\max\\{R_{1}R2,R_{4}R_{5}\\}$, and
$KL\leq\max\\{RR_{5},R_{2}R_{3}\\}$. It follows that maximum visitation gap
$\max\\{MK,ML,KL\\}$ between any two edges in the orthic trajectory is at most
the maximum visitation gap between any two edges in any sub-orthic trajectory.
∎

##  7 The $1$-Gap Optimal Schedule

It is immediate from the definitions that half the cost of the $2$-gap optimal
patrolling schedule is a lower bound to the cost of the $1$-gap optimal
patrolling schedule. By Theorem 3.2, the $2$-gap optimal patrolling schedule
has cost 2 times the perimeter of the orthic triangle. Hence, the cost of the
$1$-gap optimal schedule is at least the perimeter of the orthic triangle. On
the other hand, by Theorem 3.1 we have a patrolling schedule (the orthic
trajectory) with $1$-gap cost equal to the orthic perimeter. Therefore, we
obtain the following immediate corollary.

###### Corollary 1

The optimal $1$-gap cyclic schedule of a triangle $\Delta$ is its orthic
triangle.

The purpose of this section is to prove Theorem 3.3, that is to strengthen the
statement of Corollary 1 by showing that the optimal $1$-gap schedule is
actually cyclic. We do so by showing how to modify an arbitrary schedule into
a cyclic schedule, without increasing its $1$-gap cost. Effectively, the next
lemma implies Theorem 3.3.

###### Lemma 8

There is a $1$-gap optimal schedule that is cyclic.

###### Proof

Consider an arbitrary schedule $S=\\{s_{i}\\}_{i}$ that is not cyclic. We show
how to construct a new schedule that is cyclic and 3-periodic, without
increasing its $1$-gap. Indeed, since $S$ is not cyclic, and after renaming
edges, there are two consecutive visitations of edge $\alpha$ so that both
edges $\beta,\gamma$ are visited in between, with at least one of them being
visited more than once. In other words, for some $k,\ell\in\mathbb{N}$,
$\ell\geq 4$ we have that $e(s_{k})=e(s_{k+\ell})=\alpha$,
$e(s_{k+1})=e(s_{k+3})=\beta$ and $e(s_{k+2})=\gamma$.

In what follows we denote by $s_{i}s_{j}$ the distance between points
$s_{i},s_{j}$. Then, we see that for the $1$-gap cost $G$ of $S$, we have that

$\displaystyle G=$ $\displaystyle\max_{\delta\in E}G(\delta)\geq
G(\alpha)\geq\sum_{i=0}^{\ell-1}s_{k+i}s_{k+i+1}$ $\displaystyle\geq$
$\displaystyle s_{k}s_{k+1}+s_{k+1}s_{k+2}+s_{k+2}s_{k+3}+s_{k+3}s_{k+\ell}$
$\displaystyle\geq$ $\displaystyle
2\min\\{s_{k}s_{k+1}+s_{k+1}s_{k+2},s_{k+2}s_{k+3}+s_{k+3}s_{k+\ell}\\},$

where the second to last inequality is due to the triangle inequality.

Now we consider two different cyclic and $3$-periodic schedules,
$S^{\prime},S^{\prime\prime}$, with $1$-gap costs
$G^{\prime},G^{\prime\prime}$, respectively, and we show that
$\min\\{G^{\prime},G^{\prime\prime}\\}\leq G$. The two schedules are the
following.

$\displaystyle S^{\prime}$
$\displaystyle=s_{k},s_{k+1},s_{k+2},s_{k},s_{k+1},s_{k+2},s_{k},s_{k+1},s_{k+2},\ldots$
$\displaystyle S^{\prime\prime}$
$\displaystyle=s_{k+2},s_{k+3},s_{k+\ell},s_{k+2},s_{k+3},s_{k+\ell},s_{k+2},s_{k+3},s_{k+\ell},\ldots$

Since both $S^{\prime},S^{\prime\prime}$ are cyclic and periodic, we have that
$G^{\prime}=G^{\prime}(\alpha)=G^{\prime}(\beta)=G^{\prime}(\gamma)$ and
$G^{\prime\prime}=G^{\prime\prime}(\alpha)=G^{\prime\prime}(\beta)=G^{\prime\prime}(\gamma)$.
In particular, using the triangle inequalities again, we have

$\displaystyle G^{\prime}$
$\displaystyle=s_{k}s_{k+1}+s_{k+1}s_{k+2}+s_{k+2}s_{k}\leq
2(s_{k}s_{k+1}+s_{k+1}s_{k+2})$ $\displaystyle G^{\prime\prime}$
$\displaystyle=s_{k+2}s_{k+3}+s_{k+3}s_{k+\ell}+s_{k+\ell}s_{k+2}\leq
2(s_{k+2}s_{k+3}+s_{k+3}s_{k+\ell}).$

But then, $\min\\{G^{\prime},G^{\prime\prime}\\}\leq
2\min\\{s_{k}s_{k+1}+s_{k+1}s_{k+2},s_{k+2}s_{k+3}+s_{k+3}s_{k+\ell}\\}\leq
G$, as wanted. ∎

##  8 The Greedy Cyclic Algorithm

In this section we prove Theorem 3.4 that is we describe a patrolling schedule
that converges to a $3$-periodic cyclic schedule whose $1$-gap cost is off
from the $1$-gap optimal cyclic schedule by a factor $\gamma\in[1,1.20711]$.
It will follow from our analysis that our greedy algorithm will be nearly
optimal for any acute triangle with one arbitrarily small angle, and it will
be the worst off from the optimal solution when the given triangle is a right
isosceles.

We proceed by the description of a greedy patrolling schedule. We assume that
the patroller can remember the current and previously visited edges (not
necessarily their points), as well as that it can compute (move along) the
projection of its current position to any other edge. Formally, we label the
three edges $BC,AB,AC$ as $0,1,2$, respectively. The patrolling schedule
starts from an arbitrary point $p_{0}$ on $BC$. For each $i\geq 1$, the
patroller moves to point $p_{i}$, which is the projection of $p_{i-1}$ onto
edge $i\bmod 3$. Referring to triangle $ABC$ as in Figure 5, we note that the
patrolling schedule induces a clockwise cyclic visitation of the given
triangle. An immediate corollary of our results will imply that also the
corresponding counterclockwise cyclic visitation induces the same $1$-gap
cost.

Figure 5:  Six iterations of the greedy patrolling schedule that starts from
point $p_{0}$ of edge $BC$. Figure 6: One iteration of the greedy patrolling
schedule, stating from point $D$ 1 iteration

###### Lemma 9

On input acute triangle $ABC$, and for any starting point, the greedy
algorithm converges to a cyclic $3$-periodic schedule that has $1$-gap cost

$p\cdot\frac{\sin(A)\sin(B)\sin(C)}{1+\cos(A)\cos(B)\cos(C)}$ (3)

where $p$ is the perimeter of triangle $ABC$.

###### Proof

Consider an arbitrary iteration of the greedy algorithm and a point $D$ on
$BC$, see Figure 6. After 3 consecutive steps, the patroller has moved to the
projection $E$ of $D$ onto $AB$, its projection $F$ on $AC$ and to its
projection $G$ back on $BD$. To simplify calculations, assume also that $AB$
has length $1$. Below, we derive a relation between $BG$ and $BD$.

First we note that $AF=\cos(A)AE=\cos(A)(\gamma-
BE)=\cos(A)(\gamma-\cos(B)BD)$. Then, we use the derived formula for $AF$ to
calculate

$\displaystyle BG$ $\displaystyle=1-CG=1-\cos(C)CF=1-\cos(C)(\beta-
AF)=1-\cos(C)\left(\beta-\cos(A)(\gamma-\cos(B)BD)\right).$

It follows that there exists a constant $c$, independent of points $G,D$, such
that $BG=c-\cos(A)\cos(B)\cos(C)BD.$ If we denote by $d_{i}$ the distance of a
point on the greedy patrolling schedule at the $i$-th visitation of edge $BC$,
the previous argument shows that for the same constant $c$, we have
$d_{i+1}=c-\cos(A)\cos(B)\cos(C)d_{i}.$

Since $|\cos(A)\cos(B)\cos(C)|<1$, it follows that
$\lim_{i\rightarrow\infty}d_{i}$ exists and its value is obtained when in the
previous argument points $D,G$ coincide, see Figure 7.

Figure 7:  The limiting cyclic $3$-periodic trajectory of the (clockwise)
greedy algorithm

We proved that inscribed triangle $DEF$ is the limiting patrolling schedule of
the greedy algorithm, which is indeed a cyclic $3$-periodic schedule. Next we
calculate its cost. To this end, we claim that triangles $DEF$ and $ABC$ are
similar. By denoting by $F,E,G$ the angles of the inscribed triangle, and
looking at right triangle $FD$ we have $F=\pi-\pi/2-(\pi-C-\pi/2)=C$.
Similarly we obtain that angles $D,B$ are equal, and angles $E,A$ are equal.

Finally we compute the similarity ratio $k<1$ of triangles $DEF,ABC$. We have
that

$\alpha=BD+D\frac{ED}{\sin(B)}+\frac{DF}{\tan(c)}=\frac{k\gamma}{\sin(B)}+\frac{k\alpha}{\tan(C)}=\frac{k\alpha\sin(C)}{\sin(B)}+\frac{k\alpha}{\tan(C)},$

where the last equality follows from the sin Law in triangle $ABC$. But then,
solving for $k$ and simplifying the trigonometric expressions yields
$k=\frac{\sin(A)\sin(B)\sin(C)}{1+\cos(A)\cos(B)\cos(C)}.$ It follows that the
$1$-gap cost of the induced patrolling schedule is equal to the perimeter of
triangle $DEF$ which equals $k$ times the perimeter of $ABC$ as claimed. ∎

We are now ready to prove Theorem 3.4. An immediate corollary of Lemma 9 is
that the (limiting) cost of the greedy algorithm is the same also for the
corresponding counter-clock wise trajectory. Moreover, the ratio between its
cost and the optimal $1$-gap cost, as per Lemma 1, is given by

$\displaystyle\frac{\sin(A)\sin(B)\sin(C)}{2(1+\cos(A)\cos(B)\cos(C))}\left(\frac{1}{\sin(B)\sin(C)}+\frac{1}{\sin(A)\sin(C)}+\frac{1}{\sin(A)\sin(B)}\right)$
$\displaystyle=\frac{\sin(A)+\sin(B)+\sin(C)}{2(1+\cos(A)\cos(B)\cos(C))}.$

The latter expression, over all non-obtuse triangles, is maximized when any of
the angles $A,B,C$ is a right angle, and the other two are equal, that is for
the right isosceles, in which case the ratio becomes
$\frac{1}{2}\left(\sqrt{2}+1\right)$. In the other extreme case, it is also
easy to show that the ratio tends to 1 if any of the angles tends to 0 (hence
the other two tend to $\pi/2$), while also for the equilateral triangle, the
ratio becomes $2\sqrt{3}/3$.

##  9 Discussion

In this work we demonstrated the connection between billiard-type trajectories
and optimal patrolling schedules in combinatorial optimization. Specifically,
we introduced and solved the problem of patrolling the edges of an acute
triangle using a unit-speed agent with the goal of minimizing the maximum
1-gap and 2-gap idle time of any edge. We show that billiard-type trajectories
are optimal solution to these combinatorial patrolling problems.

Our findings point to several future directions. One natural extension of our
work is to generalize the patrolling problem to arbitrary polygons with one or
more agents. Moreover, the introduction of the novel 2-gap patrolling problem
suggests the investigation of optimal solutions for more complex frequency
requirements or time restrictions, especially with the presence of multiple
patrolling agents or multiple objects to be patrolled. In that direction, it
would be interesting to examine how our results extend to patrolling 3 or more
arbitrary line segments on the plane, as subsets of the edges of convex
polygones with one or more agents.

## References

  * [1] A. Almeida, G. Ramalho, H. Santana, P. Azevedo Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyre.  Recent advances on multi-agent patrolling.  In SBIA, pages 474–483, 2004.
  * [2] Steve Alpern, Alec Morton, and Katerina Papadaki.  Patrolling games.  Oper. Res, 59(5):1246–1257, 2011.
  * [3] Nicola Basilico.  Recent trends in robotic patrolling.  Current Robotics Reports, 3(2):65–76, 2022.
  * [4] Andrew M Baxter and Ronald Umble.  Periodic orbits for billiards on an equilateral triangle.  The American Mathematical Monthly, 115(6):479–491, 2008.
  * [5] Nicolas Bedaride.  Periodic billiard trajectories in polyhedra.  arXiv preprint arXiv:1104.1051, 2011.
  * [6] Y. Chevaleyre.  Theoretical analysis of the multi-agent patrolling problem.  In IAT, pages 302–308, 2004.
  * [7] Huda Chuangpishit, Jurek Czyzowicz, Leszek Gasieniec, Konstantinos Georgiou, Tomasz Jurdzinski, and Evangelos Kranakis.  Patrolling a path connecting a set of points with unbalanced frequencies of visits.  In A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, and Jirí Wiedermann, editors, SOFSEM 2018, volume 10706 of Lecture Notes in Computer Science, pages 367–380. Springer, 2018.
  * [8] Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc, Russell Martin, and Oscar Morales-Ponce.  Optimal patrolling of fragmented boundaries.  In Guy E. Blelloch and Berthold Vöcking, editors, 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada - July 23 - 25, 2013, pages 241–250. ACM, 2013.
  * [9] Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie, and Dominik Pajak.  Distributed patrolling with two-speed robots (and an application to transportation).  In Begoña Vitoriano and Greg H. Parlier, editors, ICORES (Selected Papers), volume 695 of Communications in Computer and Information Science, pages 71–95, 2016.
  * [10] Jurek Czyzowicz, Kostantinos Georgiou, and Evangelos Kranakis.  Patrolling.  Distributed Computing by Mobile Entities: Current Research in Moving and Computing, pages 371–400, 2019.
  * [11] Jurek Czyzowicz, Adrian Kosowski, Evangelos Kranakis, and Najmeh Taleb.  Patrolling trees with mobile robots.  In Frédéric Cuppens, Lingyu Wang, Nora Cuppens-Boulahia, Nadia Tawbi, and Joaquín García-Alfaro, editors, FPS, volume 10128 of Lecture Notes in Computer Science, pages 331–344. Springer, 2016\.
  * [12] Peter Damaschke.  Two robots patrolling on a line: Integer version and approximability.  In Leszek Gasieniec, Ralf Klasing, and Tomasz Radzik, editors, IWOCA, volume 12126 of Lecture Notes in Computer Science, pages 211–223. Springer, 2020.
  * [13] Peter Damaschke.  Distance-based solution of patrolling problems with individual waiting times.  In Matthias Müller-Hannemann and Federico Perea, editors, ATMOS 2021, volume 96 of OASIcs, pages 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [14] Y. Elmaliach, N. Agmon, and G. A. Kaminka.  Multi-robot area patrol under frequency constraints.  Ann. Math. Artif. Intell., 57(3-4):293–320, 2009.
  * [15] Y. Elmaliach, A. Shiloni, and G. A. Kaminka.  A realistic model of frequency-based multi-robot polyline patrolling.  In AAMAS (1), pages 63–70, 2008.
  * [16] Luigi Freda, Mario Gianni, Fiora Pirri, Abel Gawel, Renaud Dubé, Roland Siegwart, and Cesar Cadena.  3d multi-robot patrolling with a two-level coordination strategy.  Auton. Robots, 43(7):1747–1779, 2019.
  * [17] Ronaldo Garcia.  Elliptic billiards and ellipses associated to the 3-periodic orbits.  Am. Math. Mon, 126(6):491–504, 2019.
  * [18] Tristan Garrec.  Continuous patrolling and hiding games.  Eur. J. Oper. Res, 277(1):42–51, 2019.
  * [19] Konstantinos Georgiou, Somnath Kundu, and Pawel Pralat.  Makespan trade-offs for visiting triangle edges - (extended abstract).  In Paola Flocchini and Lucia Moura, editors, IWOCA 2021, volume 12757 of Lecture Notes in Computer Science, pages 340–355. Springer, 2021\.
  * [20] Lorenz Halbeisen and Norbert Hungerbühler.  On periodic billiard trajectories in obtuse triangles.  SIAM Review, 42(4):657–670, 2000.
  * [21] N. Hazon and G. A. Kaminka.  On redundancy, efficiency, and robustness in coverage for multiple robots.  Robotics and Autonomous Systems, 56(12):1102–1114, 2008.
  * [22] Li Huang, MengChu Zhou, Kuangrong Hao, and Edwin S. H. Hou.  A survey of multi-robot regular and adversarial patrolling.  IEEE CAA J. Autom. Sinica, 6(4):894–903, 2019.
  * [23] Roman N Karasev.  Periodic billiard trajectories in smooth convex bodies.  Geometric and Functional Analysis, 19(2):423–428, 2009.
  * [24] Akitoshi Kawamura and Yusuke Kobayashi 0001.  Fence patrolling by mobile agents with distinct speeds.  Distributed Comput, 28(2):147–154, 2015.
  * [25] Akitoshi Kawamura and Makoto Soejima.  Simple strategies versus optimal schedules in multi-agent patrolling.  Theoretical Computer Science, 839:195–206, 2020.
  * [26] Evangelos Kranakis and Danny Krizanc.  Optimization problems in infrastructure security.  In Foundations and Practice of Security - 8th International Symposium, FPS 2015, Clermont-Ferrand, France, October 26-28, 2015, Revised Selected Papers, pages 3–13, 2015.
  * [27] C Lafargue, M Lebental, A Grigis, C Ulysse, I Gozhyk, N Djellali, J Zyss, and S Bittner.  Localized lasing modes of triangular organic microlasers.  Physical Review E, 90(5):052922, 2014.
  * [28] Michel L. Lapidus and Robert G. Niemeyer.  Families of periodic orbits of the koch snowflake fractal billiard, 2011\.
  * [29] Seoung Kyou Lee, Sándor P. Fekete, and James McLurkin.  Structured triangulation in multi-robot systems: Coverage, patrolling, voronoi partitions, and geodesic centers.  Int. J. Robotics Res, 35(10):1234–1260, 2016.
  * [30] A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul.  Multi-agent patrolling: An empirical analysis of alternative architectures.  In MABS, pages 155–170, 2002.
  * [31] Oscar Morales-Ponce.  Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots.  In Nandini Mukherjee and Sriram V. Pemmaraju, editors, ICDCN 2020: 21st International Conference on Distributed Computing and Networking, Kolkata, India, January 4-7, 2020, pages 10:1–10:10. ACM, 2020.
  * [32] Fabio Pasqualetti, Antonio Franchi, and Francesco Bullo.  On optimal cooperative patrolling.  In CDC, pages 7153–7158. IEEE, 2010.
  * [33] Claudio Piciarelli and Gian Luca Foresti.  Drone swarm patrolling with uneven coverage requirements.  IET Comput. Vis, 14(7):452–461, 2020.
  * [34] David Portugal and Rui P. Rocha.  A survey on multi-robot patrolling algorithms.  In Luis M. Camarinha-Matos, editor, DoCEIS, volume 349 of IFIP Advances in Information and Communication Technology, pages 139–146. Springer, 2011.
  * [35] Richard Evan Schwartz.  Obtuse triangular billiards i: Near the (2, 3, 6) triangle.  Exp. Math, 15(2):161–182, 2006.
  * [36] Richard Evan Schwartz.  Obtuse triangular billiards ii: One hundred degrees worth of periodic trajectories.  Exp. Math, 18(2):137–171, 2009.
  * [37] Xuehou Tan and Bo Jiang 0004.  Minimization of the maximum distance between the two guards patrolling a polygonal region.  Theor. Comput. Sci, 532:73–79, 2014.
  * [38] Serge Troubetzkoy.  Dual billiards, fagnano orbits, and regular polygons.  Am. Math. Mon, 116(3):251–260, 2009.
  * [39] Ya B Vorobets, Gregorii Aleksandrovich Gal'perin, and Anatolii M Stepin.  Periodic billiard trajectories in polygons: generating mechanisms.  Russian Mathematical Surveys, 47(3):5, 1992.
  * [40] V. Yanovski, I. A. Wagner, and A. M. Bruckstein.  A distributed ant algorithm for efficiently patrolling a network.  Algorithmica, 37(3):165–186, 2003.
  * [41] Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein.  A distributed ant algorithm for efficiently patrolling a network.  Algorithmica, 37(3):165–186, 2003.


# Frequency combs with multiple offsets in THz-rate microresonators

D.N. Puzyrev1,2 and D.V. Skryabin1,2  1Department of Physics, University of
Bath, Bath, BA2 7AY, United Kingdom
2Centre for Photonics and Photonic Materials, University of Bath, Bath, BA2
7AY, United Kingdom<EMAIL_ADDRESS>
###### Abstract

Octave-wide frequency combs in microresonators are essential for self-
referencing. However, it is difficult for the small-size and high-repetition-
rate microresonators to achieve perfect soliton modelocking over the broad
frequency range due to the detrimental impact of dispersion. Here we examine
the stability of the soliton states consisting of one hundred modes in
silicon-nitride microresonators with the one-THz free spectral range. We
report the coexistence of fast and slow solitons in a narrow detuning range,
which is surrounded on either side by the breather states. We decompose the
breather combs into a sequence of sub-combs with different carrier–envelope
offset frequencies. The large detuning breathers have a high frequency of
oscillations associated with the perturbation extending across the whole
microresonator. The small detuning breathers create oscillations localised on
the soliton core and can undergo the period-doubling bifurcation, which
triggers a sequence of intense sub-combs.

††journal: oe††articletype: Research Article

##  1 Introduction

Broadband optical frequency combs find their applications in optical
metrology, spectroscopy and optical information processing [2]. The high
repetition rate, small footprint, and possibility of integrating the resonator
and pump source on the same chip are the attractive features of the
microresonator frequency comb technology [3]. Comb self-referencing requires
achieving the octave-wide soliton spectral spans. Methods to generate the
broad soliton combs rely on, e.g., reducing the microresonator radius [4, 5],
higher order dispersion [6, 7], frequency doubling in a material with
$\chi^{(2)}$ nonlinearity [8] and bi-chromatic pump [9, 10, 11].

Figure 1: (a) Soliton peak power as a function of the frequency detuning
$\delta/\kappa$ for the fixed laser power ${\cal W}=29.5$mW. (b) Difference
between the soliton repetition rate, $\tilde{D}_{1}$, and the bare resonator
rate, $D_{1}$. Full black lines in (a), (b) show stable solitons. Dashed-black
and dashed-blue lines show unstable solitons. The insets in (a) show the
stationary (unstable) soliton profiles vs $\theta/\pi$ at points (2) and (3).
Panels (c)-(h) show the soliton breathers and their radio frequency (RF)
spectra at points (1), (2), and (3). $2\pi/\Omega$ is the breather period.
$\Omega$ is given in units of $\kappa$.

In the microresonators, the comb lines start making their equidistant spectral
steps from the pump laser frequency. However, this ideal grid does not always
extend across the entire comb. The spectral structure of the octave combs
should be carefully examined on a case-by-case basis because it can be
composed of the overlapping combs having different repetition rates and
different carrier–envelope offset frequencies [9, 10, 12, 11]. For the sake of
brevity, we refer below to the carrier–envelope offset frequencies as the
offset frequencies or offsets. The Significant changes in the dispersion and
growth of specific modes triggering new four-wave mixing cascades can be the
reasons behind this unwanted complexity. Therefore, developing more profound
insights into the physical mechanisms behind the multiple offset frequencies
and repetition rates is beneficial.

Our goal is to present a theoretical framework and associated numerical data
using an example of the silicon nitride THz-rate resonator [4, 5, 13]. We
report the coexisting stable soliton combs with different repetition rates,
i.e., fast and slow solitons. The soliton instability happens via the
oscillatory scenario leading to the formation of soliton breathers [14, 15,
16, 17, 18, 19, 20, 21]. The range of the breather existence is broad and
happens on either side from the pump detuning interval supporting stable
solitons. For small detunings, the unstable waveforms are localised around the
soliton core, while the large detuning instabilities are driven by the
perturbations smeared along the resonator circumference. We demonstrate that
the breather spectra are composed of several, sometimes very intense,
overlapping combs having different offset frequencies and sharing the same
repetition rates. Mathematics underpinning our formalism is described in
Appendix, while the main text is focused on the data analysis.

Figure 2: Space-time trajectories of the slow (a) and fast (b) solitons
plotted in the reference frame rotating with the rate of the bare resonator,
$D_{1}$. The laser power $\mathcal{W}=29.5$mW and $\delta/\kappa=4.6$. (c)
Random switching between the fast (longer time intervals) and slow (shorter
intervals) for the two solitons simultaneously present in the resonator.

##  2 Fast and slow solitons

We assume that the electric field, ${\cal E}$, inside the resonator is

${\cal E}=e^{iM\vartheta-i\omega_{p}t}\psi(t,\vartheta)+c.c.,$ (1)

where $\omega_{p}$ is the pump laser frequency, $t$ is time,
$\vartheta\in[0,2\pi)$ is the angular coordinate in the laboratory frame, and
$M$ is the mode number of the resonance nearest to $\omega_{p}$. The envelope
function $\psi$ is sought as the mode expansion in the rotating frame of
reference,

$\psi=\sum_{\mu=-N/2+1}^{N/2}\psi_{\mu}(t)e^{i\mu\theta},~{}\theta=\vartheta-\tilde{D}_{1}t.$
(2)

Here, $\psi_{\mu}$ are the complex modal amplitudes, $\mu$ are the relative
mode numbers, and $\theta$ is the coordinate in the frame rotating with the
repetition rate $\tilde{D}_{1}$. We assume here that the bare resonator
spectrum, $\omega_{\mu}$, is approximated by $\omega_{\mu}=\omega_{0}+\mu
D_{1}+\tfrac{1}{2!}\mu^{2}D_{2}+\tfrac{1}{3!}\mu^{3}D_{3}+\tfrac{1}{4!}\mu^{4}D_{4}+\tfrac{1}{5!}\mu^{5}D_{5}+\tfrac{1}{6!}\mu^{6}D_{6}$,
where $\omega_{0}/2\pi=193$THz. The dispersion parameters match the THz-rate
Si3N4 resonator used in Ref. [13], see Fig. 4 there: $D_{1}/2\pi=1$THz,
$D_{2}/2\pi=20$MHz, $D_{3}/2\pi=0$Hz, $D_{4}/2\pi=-120$kHz,
$D_{5}/2\pi=5.3$kHz, $D_{6}/2\pi=-150$Hz. The linewidth is
$\kappa/2\pi=125$MHz. $\psi_{\mu}(t)$ are driven by the well-established
coupled-mode equations described in Appendix.

Soliton frequency combs realise a particular case of Eq. (2) such that

$\psi_{\mu}(t)=\hat{\psi}_{\mu}=\text{const}_{\mu},~{}\psi=\sum_{\mu}\hat{\psi}_{\mu}e^{i\mu\theta}.$
(3)

The interplay of nonlinearity and higher-order dispersion makes the soliton
repetition rate $\tilde{D}_{1}$ to be different from the bare resonator rate
value, $D_{1}$. The repetition rate difference, $\tilde{D}_{1}-D_{1}$, depends
on the resonator and pump parameters and has been determined numerically self-
consistently with the modal amplitudes $\hat{\psi}_{\mu}$. Numerical data
assembled in Fig. 1 trace the soliton peak power, $\max_{\theta}|\psi|^{2}$,
and $\tilde{D}_{1}-D_{1}$ as functions of the pump detuning,
$\delta=\omega_{0}-\omega_{p}$, for the fixed input power ${\cal W}=29.5$mW.

The relatively large angular soliton width, $\approx 2\pi/10$, boosts the role
played by the finite size effects. This makes the bifurcation structure of the
THz-rate solitons to be more complex than the one in the case of low
repetition rate resonators, see, e.g., Fig. 4 in Supplemental Materials of
Ref. [22], which corresponds to the damped-driven Nonlinear Shrödinger
equation (Lugiato-Lefever model) solved on the effectively infinite spatial
interval [23, 24]. The complex behaviour of the soliton peak power in Fig.
1(a) corresponds to the more transparent structure of the
$\tilde{D}_{1}-D_{1}$ vs $\delta$ plot in Fig. 1(b). Sufficiently rapid change
of $\tilde{D}_{1}-D_{1}$ around $\delta/\kappa=5$ separates the ranges of the
slow and fast solitons. Numerical investigation of the power dependencies of
the soliton families shows that the fast solitons emerge for powers above
$\simeq 20$mW.

The stability of solitons relative to small perturbations is an important
issue that we have analysed in detail using the formalism described in
Appendix. The dashed and full lines in Figs. 1(a) and 1(b) correspond to the
unstable and stable solitons, respectively. It should be noted that the
stability intervals of the fast and slow solitons overlap, see the shading in
Fig. 1(b). The space-time trajectories of the slow and fast solitons in the
reference frame rotating with the bare resonator rate $D_{1}$ are shown in
Figs. 2(a) and 2(b), respectively. If the model is initialised simultaneously
with the fast and slow solitons, e.g., located on the opposing sides of the
resonator, see Fig. 2(c), then we have observed the convergence of the slow
soliton to the fast one. This process could not, however, fully stabilise
itself, and the pair was making random switches to the slow state and back to
fast.

##  3 Soliton breathers and combs with multiple offsets

The unstable soliton branches marked with the blue dashed lines represent the
so-called low-branch solitons. If the model is initialised with these
solitons, it collapses to the single mode state, $\mu=0$. The solitons shown
by the dashed black lines are unstable to the oscillatory (Hopf) instability.
The waveforms driving the Hopf instability are either localised on the soliton
core (small $\delta$’s) or extend along the entire resonator circumference
(large $\delta$’s), see Appendix. Typical operation regimes emerging from the
initial conditions on the black dashed lines correspond to the soliton
breathers; see Figs. 1 (c)-(e).

The breather dynamics computed at points (1),(2) and (3), see Figs. 1(a),(b),
is shown in Figs. 1(c),(d) and (e). The reference frame is chosen to rotate
with the breather rate, which is generally different from the rate of the
unstable stationary solitons taken for the same parameters. Figs. 1(f)-(h)
show the RF (power) spectra computed in the rotating frame,
$\int_{0}^{\tau}\sum_{\mu}|\psi_{\mu}|^{2}e^{-i\Delta t}dt/\tau$. Points (2)
and (3) are nearest to the stable solitons, and the RF spectra are near
harmonic. Here, the breather frequency $\Omega$ practically coincides with the
imaginary part $\beta$ of the eigenvalues driving instabilities of the
stationary solitons, $e^{\lambda t-i\beta t}$, see Appendix for details. Point
(1) is the furthest from the Hopf threshold and is beyond the period doubling
threshold also. Here, the breather frequency becomes $\Omega=\beta/2$. The
primary oscillations are still happening with $\beta$, but the small up and
down shifts of the neighbouring intense spots, see Fig. 1(c), double the
period and half the breathing frequency.

Figure 3: Illustration of the breather spectrum. The breathing period is
$2\pi/\Omega$. $m=0$ is the primary comb and $m=\pm 1$ are the sub-combs. The
repetition rate, $\tilde{D}_{1}$, is the same for the primary and all sub-
combs, while the offset frequencies differ by $m\Omega$.  Figure 4:  Panel (a)
shows the two-dimensional map representing the power spectrum of the soliton
breather, $|\hat{\psi}_{\mu,m}|^{2}$, computed at the point (2) in Fig. 1, see
Eq. (5). The horizontal lines are separated by the breather frequency
$\Omega/\kappa=3.19$. The small panels below show the full (b), the primary
(c), $|\hat{\psi}_{\mu,0}|^{2}$, and the higher order,
$|\hat{\psi}_{\mu,|m|>0}|^{2}$, sub-combs; see Eq. (7). White circles in (a)
show the spectrum of excitations around the single mode solution, $\mu=0$, see
Eq.(8). The colour map interpolation obscures the discreteness of the spectrum
in (a). Figure 5:  Panel (a) shows the two-dimensional map representing the
power spectrum of the soliton breather, $|\hat{\psi}_{\mu,m}|^{2}$, computed
at the point (3) in Fig. 1, see Eq. (5). The horizontal lines are separated by
the breather frequency $\Omega/\kappa=28.76$. The small panels below show the
full (b), the primary (c), $|\hat{\psi}_{\mu,0}|^{2}$, and the higher order,
$|\hat{\psi}_{\mu,|m|>0}|^{2}$, sub-combs; see Eq. (7). White circles in (a)
show the spectrum of excitations around the single mode solution, $\mu=0$, see
Eq.(8). The colour map interpolation obscures the discreteness of the spectrum
in (a). Note, the difference of the y-axis scale in (a) here and in Fig. 4.

Since the breather combs have periodic modal amplitudes,

$\psi_{\mu}(t)=\hat{\psi}_{\mu}(t)=\hat{\psi}_{\mu}(t+2\pi/\Omega),$ (4)

the time-domain Fourier expansion of $\hat{\psi}_{\mu}(t)$ yields

$\psi=\sum_{\mu}\left[\sum_{m}\hat{\psi}_{\mu,m}e^{-im\Omega
t}\right]e^{i\mu\theta},$ (5)

where $\hat{\psi}_{\mu,m}$ are the time-independent amplitudes of the breather
spectrum. Using Eq. (1) and Eq. (5) and rearranging we find that the electric
field of a breather is

${\cal
E}=\sum_{m}\left[e^{iM\vartheta-i(\omega_{p}+m\Omega)t}\sum_{\mu}\hat{\psi}_{\mu,m}e^{i\mu\theta}\right]+c.c..$
(6)

Thus, the breather is a superposition of the primary, $m=0$, and higher order,
$m\neq 0$, sub-combs which all share the same repetition rate,
$\tilde{D}_{1}$, but have different central frequencies $\omega_{p}+m\Omega$,
and, therefore, different offsets from zero. The multiple spectral grids of
the breather combs are represented by

$\omega_{\mu,m}=\omega_{p}+m\Omega+\mu\tilde{D}_{1},~{}m=0,\pm 1,\pm 2,\dots,$
(7)

with $|\hat{\psi}_{\mu,m}|^{2}$ being the sideband powers in the $m$’s
subcomb, see Fig. 3 for an illustration.

The colour map in Fig. 4(a) shows the dB levels of the
$|\hat{\psi}_{\mu,m}|^{2}$ spectrum for the breather found at the point (2),
i.e., on the left from the soliton stability interval in Fig. 1(a). The
discreteness of the horizontal lines in Fig. 4(a) is smoothed over by the
colour map interpolation. The vertical separation of these lines equals
$\Omega$. The upward, $\beta_{\mu}^{+}$, and downward, $\beta_{\mu}^{-}$,
parabolas, and the sparsely separated circles for larger $\mu$ show the
spectrum of the stable small amplitude excitations,
$e^{(\lambda_{\mu}^{\pm}-i\beta_{\mu}^{\pm})t}$, $\lambda_{\mu}<0$, existing
on top of the single mode, $\mu=0$, state,

$\begin{split}\beta_{\mu}^{\pm}=&\tfrac{1}{2}\left(\omega_{\mu}-\omega_{-\mu}-2\mu\tilde{D}_{1}\right)\\\
\pm&\sqrt{3\left(\textsl{g}-\tfrac{1}{2}(\omega_{\mu}+\omega_{-\mu}-2\omega_{p})\right)\left(\textsl{g}-\tfrac{1}{6}(\omega_{\mu}+\omega_{-\mu}-2\omega_{p})\right)}.\end{split}$
(8)

Here, $\textsl{g}\sim|\psi_{0}|^{2}$ is the nonlinear shift of the resonance;
see Appendix for further details.

Data in Fig. 4(a) bring us to an immediate conclusion that, in this instance,
the breather frequency $\Omega$ equals
$\beta_{0}^{+}=\sqrt{3(g-\delta)(g-\delta/3)}$. Hence, the primary physical
reason for breathing comes from the resonance excitation of the group of modes
around $\mu=0$. This is further corroborated by the spectral shapes of the
$m=\pm 1$ sub-combs, where the central group of modes is either dominant, see
Fig. 4(d), or more pronounced than the $\mu=-40$ group, see Fig. 4(e).

Now, we are moving onto describing the sub-combs driving the breather dynamics
for large detunings, i.e., on the right from the soliton stability interval in
Fig. 1(a). The colour map of $|\hat{\psi}_{\mu,m}|^{2}$ in Fig. 5(a) shows
that the breather frequency $\Omega$ is now much larger and is given by
$\beta_{52}^{+}\approx\beta_{20}^{+}\approx\beta_{-42}^{+}$. The shape of the
$m=\pm 1$ sub-combs in Figs. 5(d), (e) is unambiguous that spectral groups
around $\mu=-42,20$, and $52$ are now dominant in the breather structure, and
the spectrum around $\mu=0$ is practically absent.

The higher-order sub-combs with $|m|\geq 2$ have very small power in the
examples presented in Figs. 4, 5. This is because points (2) and (3) are
located not deep enough into the instability range, see Fig. 1(a). However,
point (1) corresponds to well-developed instability, which has already crossed
the period doubling threshold. The higher-order sub-combs become well
developed here, see the $m=0,\pm 1,\pm 2,\pm 3$, and $\pm 4$ cases in Fig. 6.
Predictably, the even order sub-combs are more powerful because they
correspond to a subsequence of the stronger peaks in the RF spectrum in Fig.
1(f). Figs. 4-6 show the mode-number spectra, while the optical frequencies,
as measured on a spectrum analyser, must be found using Eq. (7). Fig. 7,
however, shows the selected spectral lines and a whole of the numerically
computed frequency spectrum corresponding to the mode-number data in Fig. 5.
Zooming on the individual lines reconstructs the schematic illustration in
Fig. 3. The predicted spectral features are amenable to measurements on the
high resolution spectrum analysers. Possible oscillatory instabilities due to
interaction of different mode families may yield higher values of $\Omega$.

Figure 6:  Full (a), primary (b) and higher-order sub-combs computed away from
the Hopf instability boundary at point (1) in Fig. 1.  Figure 7: Selected
spectral lines (a-j) and a whole of the numerically computed frequency
spectrum (k) corresponding to the mode-number data in Fig. 5. Zooming on the
individual spectral lines reconstructs the schematic illustration in Fig. 3.
The red lines in (a-j) correspond to the primary $m=0$ comb. The green and
blue lines are the $m=1$ and $m=-1$ sub-combs: $\Omega/2\pi=3.6$GHz.

##  4 Summary

Soliton breather states in the damped and driven nonlinear Schrödinger
(Lugiato-Lefever) equation have been known for a long time [14, 15]. The
recent resurgence in studies of their properties has happened primarily
through the context of the frequency comb generation in microresonators [9,
10, 12, 11, 16, 17, 18, 19, 20, 21]. What was particularly interesting for us
to find and report here is the significant power and bandwidth of the breather
sub-combs with different offset frequencies. The modal composition of these
sub-combs varies between the ones spectrally localised around the pump and
others detuned away. These detuned sub-combs are associated with relatively
high-frequency breathers. All this complexity happens through the interplay of
the large second and higher order dispersions and a relatively small number of
modes covering the significant bandwidth, which are all features of the small-
size and high-repetition-rate microresonators. Stable solitons can also be
found under this extreme spectral broadening. The bifurcation structure of the
THz-rate solitons and breathers differs from the one found in the idealised
Lugiato-Lefever equation solved on the infinite spatial domain. In addition to
the breathers found at the small and large detunings, we have reported the
coexisting stable solitons having two different repetition rates, i.e., slow
and fast solitons.

Funding Engineering and Physical Sciences Research Council (2119373); Horizon
2020 Framework Programme (812818).

Acknowledgments Authors thank S.B. Papp for sharing and discussing
experimental data.

Disclosures The authors declare no conflicts of interest.

Data Availability Statement Data underlying the results presented in this
paper are not publicly available but may be obtained from the authors upon
reasonable request.

## Appendix

The starting point of the derivation of our model is the Maxwell equations in
the ring-resonator geometry and with Kerr nonlinearity [22, 25, 26]. The modal
amplitudes $\psi_{\mu}$ and the field envelope $\psi$, see Eq. (2), comply
with the coupled-mode equations that can be cast to the following form [26],

$i\partial_{t}\psi_{\mu}=\Big{(}\omega_{\mu}-\omega_{p}-\mu\tilde{D}_{1}\Big{)}\psi_{\mu}-\frac{i\kappa}{2}\left(\psi_{\mu}-\hat{\delta}_{0,\mu}{\cal
H}\right)-\gamma\int_{0}^{2\pi}\psi|\psi|^{2}e^{-i\mu\theta}\frac{d\theta}{2\pi}.$
(9)

Eq. (9) contains several parameters in addition to the ones defined in the
main text. ${\cal H}$ is the pump parameter linked to the laser power, ${\cal
W}$, as ${\cal H}^{2}=\eta{\cal W}D_{1}/2\pi\kappa$, where $\eta$ is the
dimensionless coupling parameter. $\hat{\delta}_{\mu^{\prime},\mu}=1$ for
$\mu=\mu^{\prime}$ and $\hat{\delta}_{\mu^{\prime},\mu}=0$ otherwise, and
$\gamma$ is the nonlinear parameter, $\gamma/2\pi=20$MHz/W. The $\psi_{\mu}$
representation of the nonlinear term yields [26],

$i\partial_{t}\psi_{\mu}=\Big{(}\omega_{\mu}-\omega_{p}-\mu\tilde{D}_{1}\Big{)}\psi_{\mu}-\frac{i\kappa}{2}\left(\psi_{\mu}-\hat{\delta}_{0,\mu}{\cal
H}\right)-\gamma\sum_{\mu_{1}\mu_{2}\mu_{3}}\hat{\delta}_{\mu_{1}+\mu_{2}-\mu_{3},\mu}\psi_{\mu_{1}}\psi_{\mu_{2}}\psi_{\mu_{3}}^{*}.$
(10)

The stationary soliton solutions, $\psi_{\mu}=\hat{\psi}_{\mu}$, see Eq. (3),
have been found using the Newton method.

To differentiate between stable and unstable solitons and identify the
oscillatory (Hopf) instabilities we have analysed the linear stability of the
soliton family. We perturbed the time-independent soliton amplitudes,
$\hat{\psi}_{\mu}$, with small perturbations,
$\epsilon_{\mu}(t)=x_{\mu}(t)+y_{\mu}^{*}(t)$,

$\psi_{\mu}(t)=\hat{\psi}_{\mu}+x_{\mu}(t)+y^{*}_{\mu}(t),$ (11)

and then linearised Eq. (10),

$\begin{split}i(\partial_{t}+\tfrac{1}{2}\kappa)x_{\mu}&=\Big{(}\omega_{\mu}-\omega_{p}-\mu\tilde{D}_{1}\Big{)}x_{\mu}\\\
&-\gamma\sum_{\mu_{1}\mu_{2}\mu_{3}}\hat{\delta}_{\mu_{1}+\mu_{2}-\mu_{3},\mu}\left(\psi_{\mu_{2}}\psi_{\mu_{3}}^{*}x_{\mu_{1}}+\psi_{\mu_{1}}\psi_{\mu_{3}}^{*}x_{\mu_{2}}+\psi_{\mu_{1}}\psi_{\mu_{2}}y_{\mu_{3}}\right),\\\
i(\partial_{t}+\tfrac{1}{2}\kappa)y_{\mu}&=-\Big{(}\omega_{\mu}-\omega_{p}-\mu\tilde{D}_{1}\Big{)}y_{\mu}\\\
&+\gamma\sum_{\mu_{1}\mu_{2}\mu_{3}}\hat{\delta}_{\mu_{1}+\mu_{2}-\mu_{3},\mu}\left(\psi_{\mu_{1}}^{*}\psi_{\mu_{2}}^{*}x_{\mu_{3}}+\psi_{\mu_{1}}^{*}\psi_{\mu_{3}}y_{\mu_{2}}+\psi_{\mu_{2}}^{*}\psi_{\mu_{3}}y_{\mu_{1}}\right).\end{split}$
(12)

By substituting
$\left\\{x_{\mu}(t),y_{\mu}(t)\right\\}=\left\\{X_{\mu},Y_{\mu}\right\\}e^{\lambda
t-i\beta t}$, we have reduced Eq. (12) to the algebraic $2N\times 2N$
eigenvalue problem, which was solved numerically. The soliton is stable if all
$\lambda<0$ and becomes Hopf unstable when a pair of identical $\lambda$’s
with $\pm\beta\neq 0$ crosses zero. Near the Hopf threshold, $\beta$ closely
matches the breather frequency $\Omega$, see Figs. 1(g), (h). Components of
the eigenvectors in physical space are expressed as
$X(\theta)=\sum_{\mu}X_{\mu}e^{i\mu\theta}$ and
$Y(\theta)=\sum_{\mu}Y_{\mu}e^{i\mu\theta}$.

Figure 8: Eigenvalues and eigenvectors of the perturbations of the solitons
unstable relative to the breather excitations. The first, second and third
rows correspond to the points (1), (2) and (3) in Fig. 1, respectively. Each
panel in the first column has a distinct pair of unstable eigenvalues,
$\lambda>0$. The second and third columns show the corresponding eigenvectors
in the physical and Fourier spaces, respectively.

Numerically computed eigenvalues of the unstable solitons at points (1), (2)
and (3) in Fig. 1(a) are shown in Figs. 8(a)-(c). As one can see, all three
cases correspond to the Hopf instability with the pairs of complex conjugate
eigenvalues. For points (1) and (2), i.e., left from the soliton stability
interval, the eigenvectors are localised around the soliton core and are
largely shaped by the group of modes around $\mu=0$, see Fig. 8. For point
(3), i.e., right from the soliton stability interval, the eigenvectors are
spread across the entire resonator circumference and spectrally centred around
$\mu=-42,20$, and $52$. The eigenvector analysis supports the conclusions from
decomposing the dynamical data into sub-combs described in the main text.

Frequencies of the excitations supported by the single mode, $\psi_{\mu\neq
0}=0$, state, see Eq. (8), are found from the simple two-by-two eigenvalue
problem,

$i\left(\lambda_{\mu}^{\pm}-i\beta_{\mu}^{\pm}+\tfrac{1}{2}\kappa\right)\begin{bmatrix}x_{\mu}\\\
y_{-\mu}\end{bmatrix}=\begin{bmatrix}\displaystyle(\omega_{\mu}-\omega_{p}-\mu\tilde{D}_{1})-2\textsl{g}&\displaystyle-\textsl{g}e^{i\phi}\\\
\displaystyle\textsl{g}e^{-i\phi}&\displaystyle-(\omega_{-\mu}-\omega_{p}+\mu\tilde{D}_{1})+2\textsl{g}\end{bmatrix}\begin{bmatrix}x_{\mu}\\\
y_{-\mu}\end{bmatrix}.$ (13)

Here, $\textsl{g}=\gamma|\psi_{0}|^{2}$ and
$\textsl{g}e^{i\phi}=\gamma\psi_{0}^{2}$. In this case, each eigenvalue is
attributed to a particular pair of sidebands, $\pm\mu$. The ’$\pm$’
superscripts in the left side of Eq. (13) are used to distinguish between the
two eigenvalues of the matrix, see Eq. (8).

## References

  * [1]
  * [2] S.A. Diddams, K. Vahala, and T. Udem, “Optical frequency combs: Coherently uniting the electromagnetic spectrum,” Science 369, eaay3676 (2020).
  * [3] A.L. Gaeta, M. Lipson, and T.J. Kippenberg, “Photonic-chip-based frequency combs,” Nature Photon 13, 158–169 (2019).
  * [4] Q. Li, T.C. Briles, D.A. Westly, T.E. Drake, J.R. Stone, R.B. Ilic, S.A. Diddams, S.B. Papp, and K. Srinivasan, “Stably accessing octave-spanning microresonator frequency combs in the soliton regime,” Optica 4, 193–203 (2017).
  * [5] M.H.P. Pfeiffer, C. Herkommer, J. Liu, H. Guo, M. Karpov, E. Lucas, M. Zervas, and T.J. Kippenberg, “Octave-spanning dissipative Kerr soliton frequency combs in Si3N4 microresonators,” Optica 4, 684-691 (2017).
  * [6] C. Milian and D.V. Skryabin, “Soliton families and resonant radiation in a micro-ring resonator near zero group-velocity dispersion,” Opt. Express 22(3), 3732 (2014).
  * [7] V. Brasch, M. Geiselmann, T. Herr, G. Lihachev, M.H.P. Pfeiffer, M.L. Gorodetsky, and T.J. Kippenberg, “Photonic chip-based optical frequency comb using soliton Cherenkov radiation,” Science 351, 357–360 (2016).
  * [8] X. Liu, Z. Gong, A.W. Bruch, J.B. Surya, J. Lu, and H.X. Tang, “Aluminum nitride nanophotonics for beyond-octave soliton microcomb generation and self-referencing,” Nat Commun 12, 5428 (2021).
  * [9] S. Zhang, J.M. Silver, T. Bi, and P. Del’Haye, “Spectral extension and synchronization of microcombs in a single microresonator,” Nat Commun 11, 6384 (2020).
  * [10] G. Moille, E.F. Perez, J.R. Stone, A. Rao, X. Lu, T.S. Rahman, Y.K. Chembo, and K. Srinivasan, “Ultra-broadband Kerr microcomb through soliton spectral translation,” Nat Commun 12, 7275 (2021).
  * [11] P.C. Qureshi, V. Ng, F. Azeem, L.S. Trainor, H.G.L. Schwefel, S. Coen, M. Erkintalo, and S.G. Murdoch “Soliton linear-wave scattering in a Kerr microresonator,” Commun Phys 5, 123 (2022).
  * [12] S.B. Papp (private communication).
  * [13] J.R. Stone and S.B. Papp, “Harnessing Dispersion in Soliton Microcombs to Mitigate Thermal Noise,” Phys. Rev. Lett. 125, 153901 (2020).
  * [14] K. Nozaki and N. Bekki, “Solitons as attractors of a forced dissipative nonlinear Schrödinger equation,” Phys. Lett. A 102, 383–386 (1984).
  * [15] D.V. Skryabin, “Energy of internal modes of nonlinear waves and complex frequencies due to symmetry breaking,” Phys. Rev. E 64, 055601 (2001).
  * [16] C. Milian, A.V. Gorbach, M. Taki, A.V. Yulin, and D.V. Skryabin, “Solitons and frequency combs in silica microring resonators: Interplay of the Raman and higher-order dispersion effects,” Phys. Rev. A 92(3), 033851 (2015).
  * [17] E. Lucas, M. Karpov, H.M. Guo, L. Gorodetsky, and T.J. Kippenberg, “Breathing dissipative solitons in optical microresonators,” Nat Commun 8, 736 (2017).
  * [18] M. Yu, J. Jang, Y. Okawachi, A.G. Griffith, K. Luke, S.A. Miller, X. Ji, M. Lipson, and A.L. Gaeta, “Breather soliton dynamics in microresonators,” Nat Commun 8, 14569 (2017).
  * [19] M. Johansson, V.E. Lobanov, and D.V. Skryabin, “Stability analysis of numerically exact time-periodic breathers in the Lugiato-Lefever equation: Discrete vs continuum,” Phys. Rev. Research 1, 033196 (2019).
  * [20] C. Bao, B. Shen, M.G. Suh, H. Wang, K. Şafak, A. Dai, A.B. Matsko, F.X. Kartner, and K. Vahala, “Oscillatory motion of a counterpropagating Kerr soliton dimer,” Phys. Rev. A 103, L011501 (2021).
  * [21] A.A. Afridi, H. Weng, J. Li, J. Liu, M. McDermott, Q. Lu, W. Guo, and J.F. Donegan, “Breather solitons in AlN microresonators,” Opt. Continuum 1, 42-50 (2022).
  * [22] T. Herr, V. Brasch, J.D. Jost, C.Y. Wang, N.M. Kondratiev, M.L. Gorodetsky, and T.J. Kippenberg, “Temporal solitons in optical microresonators,” Nat. Photonics 8(2), 145–152 (2014).
  * [23] D.J. Kaup and A.C. Newell, “Theory of nonlinear oscillating dipolar excitations in one-dimensional condensates,” Phys. Rev. B 18, 5162–5167 (1978).
  * [24] I.V. Barashenkov and Y.S. Smirnov, “Existence and stability chart for the ac-driven, damped nonlinear Schrödinger solitons,” Phys. Rev. E 54, 5707–5725 (1996).
  * [25] Y.K. Chembo and N. Yu, “Modal expansion approach to optical-frequency-comb generation with monolithic whispering-gallery-mode resonators,” Phys. Rev. A 82, 033801 (2010).
  * [26] D.V. Skryabin, “Hierarchy of coupled mode and envelope models for bi-directional microresonators with Kerr nonlinearity,” OSA Continuum 3, 1364-1375 (2020).