# Partitioning orthogonal polygons into $\leq$ 8-vertex pieces, with
application to an art gallery theorem

Ervin Győri<EMAIL_ADDRESS>Tamás Róbert Mezei<EMAIL_ADDRESS>MTA Alfréd Rényi Institute of Mathematics, Reáltanoda u. 13–15, 1053 Budapest,
Hungary  Central European University, Department of Mathematics and its
Applications, Nádor u. 9, 1051 Budapest, Hungary

###### Abstract

We prove that every simply connected orthogonal polygon of $n$ vertices can be
partitioned into $\left\lfloor\frac{3n+4}{16}\right\rfloor$ (simply connected)
orthogonal polygons of at most 8 vertices. It yields a new and shorter proof
of the theorem of A. Aggarwal that $\left\lfloor\frac{3n+4}{16}\right\rfloor$
mobile guards are sufficient to control the interior of an $n$-vertex
orthogonal polygon. Moreover, we strengthen this result by requiring
combinatorial guards (visibility is only needed at the endpoints of patrols)
and prohibiting intersecting patrols. This yields positive answers to two
questions of O’Rourke [7, Section 3.4]. Our result is also a further example
of the “metatheorem” that (orthogonal) art gallery theorems are based on
partition theorems.

###### keywords:

art gallery , polyomino partition , mobile guard

††journal: Computational Geometry: Theory and Applications

plainthmTheorem#1plainthmtheorem#1 plainlemmaLemma#1plainlemmalemma#1
plainclaimClaim#1plainclaimclaim#1 plaindefDefinition#1plaindefdefinition#1
plaincase#1plaincase#1 plainremRemark#1plainremremark#1

111The research is partially supported by OTKA Grant 116 769.

##  1 Introduction

First let us define the basic object studied in this paper.

######  Definition 1.

A simply connected orthogonal polygon or simple polyomino $P$ is the closed
region of the plane bounded by a closed (not self-intersecting) polygon, whose
angles are all $\pi/2$ (convex) or $3\pi/2$ (reflex). We denote the number of
$P$’s vertices by $n(P)$.

This definition implies that $n(P)$ is even. We want to emphasize the
combinatorial structure of $P$ rather than its geometry, so in this paper we
refer to such objects as simple polyominoes, or polyominoes for short. When we
talk about not necessarily simply connected polyominoes, we explicitly state
it.

Kahn, Klawe and Kleitman [6] in 1980 proved that $\lfloor n/4\rfloor$ guards
are sometimes necessary and always sufficient to cover the interior of a
simple polyomino of $n$ vertices. Later the first author of this paper
provided a simple and short proof of

######  Theorem 2 ([3], [7, Thm. 2.5]).

Every simple polyomino of $n$ vertices can be partitioned into $\lfloor
n/4\rfloor$ polyominoes of at most 6 vertices.

thm:static is a deeper result than that of Kahn, Klawe and Kleitman, and gave
the first hint of the existence of a “metatheorem”: (orthogonal) art gallery
theorems have underlying partition theorems. The general case was proved by
Hoffmann [5].

######  Theorem 3 ([5]).

Every (not necessarily simply connected!) orthogonal polygon with $n$ vertices
can be covered by $\lfloor n/4\rfloor$ guards.

Hoffmann’s method (partitioning into smaller pieces that can be covered by one
guard) is another example of the metatheorem.

In this paper, we present further evidence that the metatheorem holds, namely
we prove the following partition theorem:

######  Theorem 4.

Any simple polyomino of $n$ vertices can be partitioned into at most
$\left\lfloor\frac{3n+4}{16}\right\rfloor$ simple polyominoes of at most 8
vertices.

A mobile guard is one who can patrol a line segment, and it covers a point $x$
of the gallery if there is a point $y$ on its patrol such that the line
segment $[x,y]$ is contained in the gallery. The mobile guard art gallery
theorem for simple polyominoes follows immediately from thm:mobile, as a
polyomino of at most 8 vertices can be covered by a mobile guard:

######  Theorem 5 ([1], proof also in [7, Thm. 3.3]).

$\left\lfloor\frac{3n+4}{16}\right\rfloor$ mobile guards are sufficient for
covering an $n$ vertex simple polyomino.

thm:mobile is a stronger result than thm:mobilecover and it is interesting on
its own. It fits into the series of results in [3], [5], [7, Thm. 2.5], [4]
showing that rectilinear art gallery theorems are based on theorems on
partitions of polyominoes into smaller (“one guardable”) polyominoes.

Moreover, thm:mobile directly implies the following corollary which
strengthens the previous theorem and answers two questions raised by O’Rourke
[7, Section 3.4].

######  Corollary 6.

$\left\lfloor\frac{3n+4}{16}\right\rfloor$ mobile guards are sufficient for
covering an $n$ vertex simple polyomino such that the patrols of two guards do
not pass through one another and visibility is only required at the endpoints
of the patrols.

The proof of thm:mobile is similar to the proofs of thm:static in that it
finds a suitable cut and then uses induction on the parts created by the cut.
However, here a cut along a line segment connecting two reflex vertices is not
automatically good. In case we have no such cuts, we also rely heavily on a
tree structure of the polyomino (sec:treestructure). However, while O’Rourke’s
proof only uses straight cuts, in our case this is not sufficient:
fig:LisNeccessary shows a polyomino of 14 vertices which cannot be cut into 2
polyominoes of at most 8 vertices using cuts along straight lines. Therefore
we must consider L-shaped cuts too.

Figure 1: An L-shaped cut creating a partition into 8-vertex polyominoes

Interested readers can find a thorough introduction to the subject of art
gallery problems in [7].

##  2 Definitions and preliminaries

Let $P,P_{1},P_{2}$ be simple polyominoes of $n,n_{1},n_{2}$ vertices,
respectively. If $P=P_{1}\cup P_{2}$,
$\mathrm{int}(P_{1})\cap\mathrm{int}(P_{2})=\emptyset$, $0<n_{1},n_{2}$ and
$n_{1}+n_{2}\leq n+2$ are satisfied, we say that $P_{1},P_{2}$ form an
admissible partition of $P$, which we denote by
$P=P_{1}\mathop{\overset{\star}{\cup}}P_{2}$. Also, we call $L=P_{1}\cap
P_{2}$ a cut in this case. We may describe this relationship concisely by
$L(P_{1},P_{2})$. If, say, we have a number of cuts $L_{1},L_{2},$ etc., then
we usually write $L_{i}(P_{1}^{i},P_{2}^{i})$. Generally, if a subpolyomino is
denoted by $P_{x}^{y}$, then $y$ refers to a cut and $x\in\\{1,2\\}$ is the
label of the piece in the partition created by said cut. Furthermore, if

$\left\lfloor\frac{3n_{1}+4}{16}\right\rfloor+\left\lfloor\frac{3n_{2}+4}{16}\right\rfloor\leq\left\lfloor\frac{3n+4}{16}\right\rfloor.$
(1)

is also satisfied, we say that $P_{1},P_{2}$ form an induction-good partition
of $P$, and we call $L$ a good cut.

######  Lemma 7.

An admissible partition $P=P_{1}\mathop{\overset{\star}{\cup}}P_{2}$ is also
and induction-good partition if
(a) $n_{1}+n_{2}=n+2$ and $n_{1}\equiv 2,8,\text{ or }14\pmod{16}$,
or
(b) $n_{1}+n_{2}=n$ and $n_{1}\equiv 0,2,6,8,12,\text{ or }14\pmod{16}$,
or
(c) $n\not\equiv 14\mod 16$ and either

$n_{1}+n_{2}=n\text{ and }n_{1}\equiv 10\pmod{16}\textbf{\quad or
\quad}n_{1}+n_{2}=n+2\text{ and }n_{1}\equiv 12\pmod{16}.$

###### Proof.

Using the fact that the floor function satisfies the triangle inequality, the
proof reduces to an easy case-by-case analysis, which we leave to the reader.
∎

Any cut $L$ in this paper falls into one of the following 3 categories (see
fig:cuts):

  1. (a)

1-cuts: $L$ is a line segment, and exactly one of its endpoints is a (reflex)
vertex of $P$.

  2. (b)

2-cuts: $L$ is a line segment, and both of its endpoints are (reflex) vertices
of $P$.

  3. (c)

L-cuts: $L$ consists of two connected line segments, and both endpoints of $L$
are (reflex) vertices of $P$.

Note that for 1-cuts and L-cuts the size of the parts satisfy
$n_{1}+n_{2}=n+2$, while for 2-cuts we have $n_{1}+n_{2}=n$.

a 1-cut

b1 2-cut

b2 2-cut

c L-cut

Figure 2: Examples for all types of cuts. Light gray areas are subsets of
$\mathrm{int}(P)$.

In the proof of thm:mobile we are searching for an induction-good partition of
$P$. As a good cut defines an induction-good partition, it is sufficient to
find a good cut. We could hope that a good cut of a subpolyomino of $P$ is
extendable to a good cut of $P$, but unfortunately a good cut of a
subpolyomino may only be an admissible cut with respect to $P$ (if it is a cut
of $P$ at all). lemma:tech, however, allows us to look for cut-systems
containing a good cut. Fortunately, it is sufficient to consider non-crossing,
nested cut-systems of at most 3 cuts, defined as follows.

######  Definition 8 (Good cut-system).

The cuts $L_{1}(P_{1}^{1},P_{2}^{1})$, $L_{2}(P_{1}^{2},P_{2}^{2})$ and
$L_{3}(P_{1}^{3},P_{2}^{3})$ (possibly $L_{2}=L_{3}$) constitute a good cut-
system if $P_{1}^{1}\subset P_{1}^{2}\subseteq P_{1}^{3}$, and the set

$\left\\{n(P_{1}^{i})\ |\ i\in\\{1,2,3\\}\right\\}\cup\left\\{n(P_{1}^{i})+2\
|\ i\in\\{1,2,3\\}\text{ and }L_{i}\text{ is a 2-cut}\right\\}$

contains three consecutive even elements modulo 16 (ie., the union of their
residue classes contains a subset of the form $\\{a,a+2,a+4\\}+16\mathbb{Z}$).
If this is the case we also define their kernel as
$\ker\\{L_{1},L_{2},L_{3}\\}=(P_{1}^{1}-L_{1})\cup(P_{2}^{3}-L_{3})$, which
will be used in lemma:extendconsecutives.

lemma:tech:a and 7 immediately yield that any good cut-system contains a good
cut.

######  Remark 9.

It is easy to see that if a set of cuts satisfies this definition, then they
obviously satisfy it in the reverse order too (the order of the generated
parts are also switched). Actually, these are exactly the two orders in which
they do so. Thus the kernel is well-defined, and when speaking about a good
cut-system it is often enough to specify the set of participating cuts.

##  3 Tree structure

Any reflex vertex of a polyomino defines a (1- or 2-) cut along a horizontal
line segment whose interior is contained in $\mathrm{int}(P)$ and whose
endpoints are the reflex vertex and another point on the boundary of the
polyomino. Next we define a graph structure derived from $P$, which is a
standard tool in the literature, for example it is called the $R$-graph of $P$
in [4].

######  Definition 10 (Horizontal cut tree).

The horizontal cut tree $T$ is obtained as follows. First, partition $P$ into
a set of rectangles by cutting along all of the horizontal cuts of $P$. Let
$V(T)$, the vertex set of $T$ be the set of resulting (internally disjoint)
rectangles. Two rectangles of $T$ are connected by an edge in $E(T)$ iff their
boundaries intersect.

The graph $T$ is indeed a tree as its connectedness is trivial and since any
cut creates two internally disjoint polyominoes, $T$ is also cycle-free. We
can think of $T$ as a sort of dual of the planar graph determined by $P$ and
its horizontal cuts. The nodes of $T$ represent rectangles of $P$ and edges of
$T$ represent horizontal 1- and 2-cuts of $P$. For this reason we may refer to
nodes of $T$ as rectangles. This nomenclature also helps in distinguishing
between vertices of $P$ (points) and nodes of $T$. Moreover, for an edge $e\in
E(T)$, we may denote the cut represented by $e$ by simply $e$, as the context
should make it clear whether we are working in the graph $T$ or the polyomino
$P$ itself.

Note that the vertical sides of rectangles are also edges of the polyomino. We
will also briefly use vertical cut trees, which can be defined analogously.

######  Definition 11.

Let $T$ be the horizontal cut tree of $P$. Define $t:E(T)\to\mathbb{N}$ as
follows: given any edge $\\{R_{1},R_{2}\\}\in E(T)$, let

$t(\\{R_{1},R_{2}\\})=n(R_{1}\cup R_{2})-8.$

Observe that

$t(e)=\left\\{\begin{array}[]{rl}0,&\text{ if $e$ represents a 2-cut;}\\\
-2,&\text{ if $e$ represents a 1-cut.}\\\ \end{array}\right.$

The following claim is used throughout the paper to count the number of
vertices of subpolyominoes.

######  Claim 12.

Let $T$ be the horizontal cut tree of $P$. Then

$n(P)=4|V(T)|+\sum_{e\in E(T)}t(e).$

###### Proof.

The proof is straightforward. ∎

######  Remark 13.

The equality still holds even if some of the rectangles of $T$ are cut into
several rows (and the corresponding edges, for which the function $t$ takes
$-4$, are added to $T$).

###  3.1 Extending cuts and cut-systems

The following two technical lemmas considerably simplify our analysis in
sec:proof, where many cases distinguished by the relative positions of reflex
vertices of $P$ on the boundary of a rectangle need to be handled. For a
rectangle $R$ let us denote its top left, top right, bottom left, and bottom
right vertices with $v_{TL}(R)$, $v_{TR}(R)$, $v_{BL}(R)$, and $v_{BR}(R)$,
respectively.

(a) $Q\subseteq R_{TL}$, and $e_{TL}(R)$ is a 1-cut

(b) $Q\subseteq R_{TL}$, $e_{TL}(R)$ is a 1-cut, and $R_{TR}=\emptyset$

(c) $Q\subseteq R_{TL}$, and $e_{TL}(R)$ is a 2-cut

(d) $R_{TL}=R_{TR}=\emptyset$, $R$ is either a corridor or a pocket (see
sec:proof)

(e) $R_{TL}=\emptyset$, but $Q\subseteq R_{TR}$

Figure 3: $R\cup Q$ in all essentially different relative positions of $R,Q\in
V(T)$, where $\\{R,Q\\}\in E(T)$ and $v_{TL}(R)\in Q$

######  Definition 14.

Let $R,Q\in V(T)$ be arbitrary. We say that $Q$ is adjacent to $R$ at
$v_{TL}(R)$, if $v_{TL}(R)\in Q$ and $v_{TL}(R)$ is not a vertex of the
polyomino $R\cup Q$, or $v_{TR}(R)\notin Q$. Such situations are depicted on
Figures 3(a), 3(b), and 3(c). However, in the case of Figure 3(d) and 3(e) we
have $v_{TR}(R)\in Q\not\subseteq R_{TL}\;(=\emptyset)$.

If $Q$ is adjacent to $R$ at $v_{TL}(R)$, let $e_{TL}(R)=\\{R,Q\\}$; by
cutting $P$ along the dual of $e_{TL}(R)$, ie., $R\cap Q$, we get two
polyominoes, and we denote the part containing $Q$ by $R_{TL}$. If there is no
such $Q$, let $e_{TL}(R)=\emptyset$ and $R_{TL}=\emptyset$. These relations
can be defined analogously for top right ($R_{TR}$, $e_{TR}(R)$), bottom left
($R_{BL}$, $e_{BL}(R)$), and bottom right ($R_{BR}$, $e_{BR}(R)$).

######  Lemma 15.

Let $R$ be an arbitrary rectangle such that $R_{BL}\neq\emptyset$. Let $U$ be
the remaining portion of the polyomino, ie.,
$P=R_{BL}\mathop{\overset{\star}{\cup}}U$ is a polyomino-partition. Take an
admissible polyomino-partition $U=U_{1}\mathop{\overset{\star}{\cup}}U_{2}$
such that $v_{BL}(R)\in U_{1}$. We can extend this to an admissible polyomino-
partition of $P$ where the two parts are $U_{1}\cup R_{BL}$ and $U_{2}$.

###### Proof.

Let $Q_{1}=R\cap U_{1}$ and let $Q_{2}\in V(T)$ be the rectangle which is a
subset of $R_{BL}$ and adjacent to $R$.

Observe that $U_{1}$ and $R_{BL}$ only intersect on $R$’s bottom side,
therefore their intersection is a line segment $L$ and so $U_{1}\cup R_{BL}$
is a polyomino. Trivially, $P=(U_{1}\cup
R_{BL})\mathop{\overset{\star}{\cup}}U_{2}$ is partition into polyominoes, so
only admissibility remains to be checked.

Let the horizontal cut tree of $U_{1}$ and $R_{BL}$ be $T_{U_{1}}$ and
$T_{R_{BL}}$, respectively. The horizontal cut tree of $U_{1}\cup R_{BL}$ is
$T_{U_{1}}\cup T_{R_{BL}}+\\{Q_{1},Q_{2}\\}$, except if
$t(\\{Q_{1},Q_{2}\\})=-4$. Either way, by referring to rem:refine we can use
claim:tsize to write that

$\displaystyle n(U_{1}\cup R_{BL})$
$\displaystyle+n(U_{2})-n(P)=n(U_{1})+n(R_{BL})+t(\\{Q_{1},Q_{2}\\})+n(U_{2})-n(P)=$
$\displaystyle=\Big{(}n(U_{1})+n(U_{2})-n(U)\Big{)}+\Big{(}n(U)+n(R_{BL})-n(P)\Big{)}+t(\\{Q_{1},Q_{2}\\})=$
(2)
$\displaystyle=(n(U_{1})+n(U_{2})-n(U))-t(\\{R,Q_{2}\\})+t(\\{Q_{1},Q_{2}\\}).$

Now it is enough to prove that $t(\\{Q_{1},Q_{2}\\})\leq t(\\{R,Q_{2}\\})$. If
$t(\\{R,Q_{2}\\})=0$ this is trivial. The remaining case is when
$t(\\{R,Q_{2}\\})=-2$. This means that $v_{BL}(R)$ is not a vertex of $R\cup
Q_{2}$, therefore it is not a vertex of $Q_{1}\cup Q_{2}$ either, implying
that $n(Q_{1}\cup Q_{2})<8$. ∎

######  Lemma 16.

Let $R\in V(T)$ be such that $R_{BL}\neq\emptyset$. Let $U$ be the other half
of the polyomino, ie., $P=R_{BL}\mathop{\overset{\star}{\cup}}U$. If $U$ has a
good cut-system $\mathcal{L}$ such that $v_{BL}(R)\in\ker\mathcal{L}$ then $P$
also has a good cut-system.

###### Proof.

Let us enumerate the elements of $\mathcal{L}$ as $L_{i}$ where $i\in I$. Take
$L_{i}(U_{1}^{i},U_{2}^{i})$ such that $v_{BL}(R)\in U_{1}^{i}$. Using
lemma:extend extend $L_{i}$ to a cut $L_{i}^{\prime}(P_{1}^{i},P_{2}^{i})$ of
$P$ such that $U_{2}^{i}=P_{2}^{i}$.

eq:newsize and the statement following it implies that
$n(P_{1}^{i})+n(P_{2}^{i})=n(P)+2\implies n(U_{1}^{i})+n(U_{2}^{i})=n(U)+2$.
In other words, if $L_{i}$ is a 2-cut then so is $L_{i}^{\prime}$. Therefore

$\displaystyle\left\\{n(U_{2}^{i})\ |\ i\in I\right\\}$
$\displaystyle\cup\left\\{n(U_{2}^{i})+2\ |\ i\in I\text{ and }L_{i}\text{ is
a 2-cut}\right\\}\subseteq$ $\displaystyle\subseteq\left\\{n(P_{2}^{i})\ |\
i\in I\right\\}\cup\left\\{n(P_{2}^{i})+2\ |\ i\in I\text{ and
}L_{i}^{\prime}\text{ is a 2-cut}\right\\}$

and by referring to rem:invert we get that $\\{L_{i}^{\prime}\ |\ i\in I\\}$
is a good cut-system of $P$. ∎

##  4 Proof of thm:mobile

We will prove thm:mobile by induction on the number of vertices. For $n\leq 8$
the theorem is trivial.

For $n>8$, let $P$ be the polyomino which we want to partition into smaller
polyominoes. It is enough to prove that $P$ has a good cut. The rest of this
proof is an extensive case study. Let $T$ be the horizontal cut tree of $P$.
We need two more definitions.

  * 1.

A pocket in $T$ is a degree-1 rectangle $R$, whose only incident edge in $T$
is a 2-cut of $P$ and this cut covers the entire top or bottom side of $R$.

  * 2.

A corridor in $T$ is a rectangle $R$ of degree $\geq 2$ in $T$, which has an
incident edge in $T$ which is a 2-cut of $P$ and this cut covers the entire
top or bottom side of $R$.

We distinguish 4 cases.

case:Tisapath.

$T$ is a path, fig:cases(a);

case:corridors.

$T$ has a corridor, fig:cases(b);

case:pockets.

$T$ does not have a corridor, but it has a pocket, fig:cases(c);

case:twisted.

None of the previous cases apply, fig:cases(d).

(a) $T$ is a path.

(b) $T$ has a corridor.

(c) $T$ does not have a corridor, but it has a pocket.

(d) $T$ does not have a corridor or a pocket, and it is not a path.

Figure 4: The 4 cases of the proof.

##  Case 1 $T$ is a path

######  Claim 17.

If an edge incident to a degree-2 vertex $R$ of $T$ is a 2-cut of $P$ then the
incident edges of $R$ form a good cut-system.

###### Proof.

Let the two incident edges of $R$ be $e_{1}$ and $e_{2}$. Let their generated
partitions be $e_{1}(P_{1}^{1},P_{2}^{1})$ and $e_{2}(P_{1}^{2},P_{2}^{2})$,
such that $R\subseteq P_{2}^{1}\cap P_{1}^{2}$. Then $P_{1}^{2}=P_{1}^{1}\cup
R$, so

$\displaystyle n(P_{1}^{2})=n(P_{1}^{1})+n(R)+t(e_{1})=n(P_{1}^{1})+4.$

def:goodcutsystem is satisfied by $\\{e_{1},e_{2}\\}$, as
$\\{n(P_{1}^{1}),n(P_{1}^{2})\\}\cup\\{n(P_{1}^{1})+2\\}$ is a set of three
consecutive even elements. ∎

######  Claim 18.

If there are two rectangles $R_{1}$ and $R_{2}$ which are adjacent degree-2
vertices of $T$ then the union of the set of incident edges of $R_{1}$ and
$R_{2}$ form a good cut-system.

###### Proof.

Let the two components of $T-R_{1}-R_{2}$ be $T_{1}$ and $T_{2}$, so that
$e_{1},e_{2},f\in E(T)$ joins $T_{1}$ and $R_{1}$, $R_{1}$ and $R_{2}$,
$R_{2}$ and $T_{2}$, respectively. Obviously, $\cup V(T_{1})\subset(\cup
V(T_{1}))\cup R_{1}\subset(\cup V(T_{1}))\cup R_{1}\cup R_{2}$. If one of
$\\{e_{1},e_{2},f\\}$ is a 2-cut, we are done by the previous claim. Otherwise

$\displaystyle n((\cup V(T_{1}))\cup R_{1})=n(\cup
V(T_{1}))+n(R_{1})+t(e_{1})$ $\displaystyle=n(\cup V(T_{1}))+2,$
$\displaystyle n((\cup V(T_{1}))\cup R_{1}\cup R_{2})=n(\cup
V(T_{1}))+n(R_{1})+n(R_{2})+t(e_{1})+t(f)$ $\displaystyle=n(\cup V(T_{1}))+4,$

and so $\\{n(\cup V(T_{1})),n((\cup V(T_{1}))\cup R_{1}),n((\cup V(T_{1}))\cup
R_{1}\cup R_{2})\\}$ are three consecutive even elements. This concludes the
proof that $\\{e_{1},e_{2},f\\}$ is a good cut-system of $P$. ∎

Suppose $T$ is a path. If $T$ is a path of length $\leq 3$ such that all of
its edges are 1-cuts, then $n(P)\leq 8$. Also, if $T$ is path of length 2 and
its only edge represents a 2-cut, then $n(P)=8$. Otherwise either
claim:deg2doublecut or claim:deg2path can be applied to provide a good cut-
system of $P$.

##  Case 2 $T$ has a corridor

Let $e=\\{R^{\prime},R\\}\in E(T)$ be a horizontal 2-cut such that
$R^{\prime}$ is a wider rectangle than $R$ and $\deg(R)\geq 2$. Let the
generated partition be $e(P_{1}^{e},P_{2}^{e})$ such that $R^{\prime}\subseteq
P_{1}^{e}$. We can handle all possible cases as follows.

  1. (a)

If $n(P_{1}^{e})\not\equiv 4,10\bmod 16$ or $n(P_{2}^{e})\not\equiv 4,10\bmod
16$, then $e$ is a good cut by lemma:tech:b.

  2. (b)

If $\deg(R)=2$, we find a good cut using claim:deg2doublecut.

  3. (c)

If $R_{BL}=\emptyset$, then $L(P_{1}^{L},P_{2}^{L})$ such that
$R^{\prime}\subseteq P_{1}^{L}$ in fig:corridor_b is a good cut, since
$n(P_{1}^{L})=n(P_{1}^{e})+4-0\equiv 8,14\bmod 16$.

Figure 5: $L$ is a good cut

  4. (d)

If $R_{BL}\neq\emptyset$ and $\deg(R)\geq 3$, then let us consider the
following five cuts of $P$ (fig:corridor_c): $L_{1}(R_{BL},R\cup P_{1}^{e})$,
$L_{2}(R_{BL}\cup Q_{1},Q_{2}\cup Q_{3}\cup P_{1}^{e})$, $L_{3}(R_{BL}\cup
Q_{1}\cup Q_{2},Q_{3}\cup P_{1}^{e})$, $L_{4}(Q_{3},R_{BL}\cup Q_{1}\cup
Q_{2}\cup P_{1}^{e})$, and $L_{5}(Q_{3}\cup Q_{2},R_{BL}\cup Q_{1}\cup
P_{1}^{e})$.

Figure 6: $\deg(R)\geq 3$ and $R_{BL}\neq\emptyset$

The first piece of these partitions have the following number of vertices
(respectively).

    1. (1)

$n(R_{BL})$

    2. (2)

$n(R_{BL}\cup
Q_{1})=n(R_{BL})+n(Q_{1})+(t(e_{BL}(R))-2)=n(R_{BL})+t(e_{BL}(R))+2$

    3. (3)

$n(R_{BL}\cup Q_{1}\cup Q_{2})=n(R_{BL})+n(Q_{1}\cup
Q_{2})+t(e_{BL}(R))=n(R_{BL})+t(e_{BL}(R))+4$

    4. (4)

$n(Q_{3})$

    5. (5)

$n(Q_{3}\cup Q_{2})=n(Q_{3})+n(Q_{2})-2=n(Q_{3})+2$

     * (a)

If $t(e_{BL}(R))=0$, then $\\{L_{1},L_{2},L_{3}\\}$ is a good cut-system, so
one of them is a good cut.

     * (b)

If $t(e_{BL}(R))=-2$, and none of the 5 cuts above are good cuts, then using
lemma:tech:b on $L_{2}$ and $L_{3}$ gives ${n(R_{BL})\equiv 4,10\bmod 16}$.
The same argument can be used on $L_{4}$ and $L_{5}$ to conclude that
$n(Q_{3})\equiv 4,10\bmod 16$. However, previously we derived that

$\displaystyle n(P_{2}^{e})$ $\displaystyle\equiv 4,10\bmod 16$ $\displaystyle
n(R_{BL}\cup Q_{1}\cup Q_{2}\cup Q_{3})=n(R_{BL}\cup Q_{1}\cup
Q_{2})+n(Q_{3})-2=n(R_{BL})+n(Q_{3})$ $\displaystyle\equiv 4,10\bmod 16$

This is only possible if $n(R_{BL})\equiv n(Q_{3})\equiv 10\bmod 16$. Let
$e_{BL}(R)=\\{R,S\\}$.

       * i.

If $\deg(S)=2$, then let $E(T)\ni e^{\prime}\neq e_{BL}(R)$ be the other edge
of $S$. Let the partition generated by it be
$e^{\prime}(P_{1}^{e^{\prime}},P_{2}^{e^{\prime}})$ such that
$R^{\prime}\subseteq P_{1}^{e^{\prime}}$. We have

$\displaystyle n(R_{BL})$
$\displaystyle=n(P_{2}^{e^{\prime}})+n(S)+t(e^{\prime})$ $\displaystyle
n(P_{2}^{e^{\prime}})$ $\displaystyle=n(R_{BL})-4-t(e^{\prime})\equiv
6-t(e^{\prime})\bmod 16$

Either $e^{\prime}$ is a 1-cut, in which case $n(P_{2}^{e^{\prime}})\equiv
8\bmod 16$, or $e^{\prime}$ is a 2-cut, giving $n(P_{2}^{e^{\prime}})\equiv
6\bmod 16$. In any case, lemma:tech says that $e^{\prime}$ is a good cut.

       * ii.

If $\deg(S)=3$, then we can partition $P$ as in fig:corridor_e. Since
$n(Q_{5}\cup Q_{6})=4+n(Q_{6})-2$, by lemma:tech:a the only case when neither
$L_{6}(Q_{5}\cup Q_{6},Q_{4}\cup R\cup P_{1}^{e})$ nor $L_{7}(Q_{6},Q_{4}\cup
Q_{5}\cup R\cup P_{1}^{e})$ is a good cut of $P$ is when $n(Q_{6})\equiv
4,10\bmod 16$. Also,

$10\equiv n(Q_{4}\cup Q_{5}\cup Q_{6})=n(Q_{4})+n(Q_{5})+n(Q_{6})-2-2\equiv
n(Q_{4})+n(Q_{6})\bmod 16.$

         * A.

If $n(Q_{6})\equiv 10\bmod 16$, then $n(Q_{4})\equiv 0\bmod 16$, hence

$\displaystyle n(Q_{4}\cup Q_{5}\cup Q_{11}\cup Q_{12})=n(Q_{4}\cup
Q_{5})+4-4=n(Q_{4})+n(Q_{5})-2\equiv 2\bmod 16,$

showing that $L_{8}(Q_{4}\cup Q_{5}\cup Q_{11}\cup Q_{12},Q_{6}\cup Q_{13}\cup
Q_{2}\cup Q_{3}\cup P_{1}^{e})$ is a good cut.

         * B.

If $n(Q_{6})\equiv 4\bmod 16$,

$\displaystyle n(Q_{6}\cup Q_{13}\cup Q_{2}\cup Q_{3})$
$\displaystyle=n(Q_{6})+n(Q_{13}\cup Q_{2})+n(Q_{3})-2-2\equiv$
$\displaystyle\equiv n(Q_{6})+10\equiv 14\mod 16,$

therefore $L_{9}(Q_{6}\cup Q_{13}\cup Q_{2}\cup Q_{3},Q_{4}\cup Q_{5}\cup
Q_{11}\cup Q_{12}\cup P_{1}^{e})$ is a good cut.

Figure 7: $\deg(Q)\geq 3$ and $Q_{BL}\neq\emptyset$

In all of the above subcases we found a good cut.

##  Case 3 There are no corridors in $T$, but there is a pocket

Let $S$ be a (horizontal) pocket. Also, let $R$ be the neighbor of $S$ in $T$.
If $\deg(R)=2$, then claim:deg2doublecut provides a good cut-system of $P$.
However, if $\deg(R)\geq 3$, we have two cases.

##  Case 3.1 If $R$ is adjacent to at least two pockets

Let $U$ be the union of $R$ and its adjacent pockets, and let $T_{U}$ be its
vertical cut tree. It contains at least $4$ reflex vertices, therefore
$V(T_{U})\geq 3$.

  * 1.

If $V(T_{U})=3$, then $|E(T_{U})|=2$. Thus $t(e)=0$ for any $e\in E(T_{U})$,
and claim:deg2doublecut gives a good cut-system $\mathcal{L}$ of $U$ such that
all 4 vertices of $R$ are contained in $\ker\mathcal{L}$.

  * 2.

If $V(T_{U})\geq 4$, then claim:deg2path gives a good cut-system $\mathcal{L}$
of $U$ such that all 4 vertices of $R$ are contained in $\ker\mathcal{L}$.

Since there are no corridors in $P$, we have

$P=\Big{(}\big{(}(U\cup R_{BL})\cup R_{TL}\big{)}\cup R_{BR}\Big{)}\cup
R_{TR}.$

By applying lemma:extendconsecutives repeatedly, the good cut-system
$\mathcal{L}$ can be extended to a good cut-system of $P$.

##  Case 3.2 If $S$ is the only pocket adjacent to $R$

We may assume without loss of generality that $S$ intersect the top side of
$R$. Again, define $U$ as the union of $R$ and its adjacent pockets.

  * 1.

If $R_{TL}\neq\emptyset$, let $V=U\mathop{\overset{\star}{\cup}}R_{TL}$. The
cut-system $\\{L_{1},L_{2},L_{3}\\}$ in fig:pockets1 is a good cut-system of
$V$, and all 4 vertices of $R$ are contained in $\ker\\{L_{1},L_{2},L_{3}\\}$.
By applying lemma:extendconsecutives repeatedly, we get a good cut-system of
$P$.

Figure 8: $\\{L_{1},L_{2},L_{3}\\}$ is a good cut-system of $V=R\cup
R_{TL}\cup S$

  * 2.

If $R_{TR}\neq\emptyset$, the case can be solved analogously to the previous
case.

  * 3.

Otherwise $R_{BL}\neq\emptyset$ and $R_{BR}\neq\emptyset$. Let
$L_{1}(U_{1}^{1},U_{2}^{1})$ and $L_{2}(U_{1}^{2},U_{2}^{2})$ be the vertical
cuts (from right to left) defined by the two reflex vertices of $U$, such that
$v_{BR}(R)\in U_{1}^{1}\subset U_{1}^{2}$. Let
$V=R_{BL}\mathop{\overset{\star}{\cup}}U$. As before, $L_{1}$ and $L_{2}$ can
be extended to cuts of $V$, say $L_{1}^{\prime}(U_{1}^{1},V_{2}^{1})$,
$L_{2}^{\prime}(U_{1}^{2},V_{2}^{2})$. We claim that together with
$e_{BL}(R)(U,V_{2}^{3})$, they form a good cut-system $\mathcal{L}$ of $V$.
This is obvious, as $\\{n(U_{1}^{1}),n(U_{1}^{2}),n(U)\\}=\\{4,6,8\\}$. Since
$v_{BR}(R)\in\ker\mathcal{L}$, $P$ also has a good cut-system by
lemma:extendconsecutives.

##  Case 4 $T$ is not a path and it does not contain either corridors or
pockets

By the assumptions of this case, any two adjacent rectangles are adjacent at
one of their vertices, so the maximum degree in $T$ is 3 or 4. We distinguish
between several sub-cases.  case:toporbotcontained. There exists a rectangle
of degree $\geq 3$ such that its top or bottom side is entirely contained by
one of its neighboring rectangle; case:last. Every rectangle of degree $\geq
3$ is such that its top and bottom side are not entirely contained by any of
their neighboring rectangle; case:last1. There exist at least two rectangles
of degree $\geq 3$; case:last2. There is exactly one rectangle of degree $\geq
3$.

##  Case 4.1 There exists a rectangle of degree $\geq 3$ such that its top or
bottom side is entirely contained by one of its neighboring rectangle

Let $R$ be a rectangle and $R^{\prime}$ its neighbor, such that the top or
bottom side of $R$ is $\subset\partial R^{\prime}$. Moreover, choose $R$ such
that if we partition $P$ by cutting $e=\\{R,R^{\prime}\\}$, the part
containing $R$ is minimal (in the set theoretic sense).

Without loss of generality, the top side of $R$ is contained entirely by a
neighboring rectangle $R^{\prime}$ and $R_{TL}=\emptyset$.

Figure 9:

This is pictured in fig:topside, where $R=R_{1}\cup R_{2}\cup R_{3}$. We can
cut off $R_{BL}$, $R_{BL}\cup R_{1}$, and $R_{BL}\cup R_{1}\cup R_{2}$, whose
number of vertices are respectively

  1. (1)

$n(R_{BL})$

  2. (2)

$n(R_{BL}\cup
R_{1})=n(R_{BL})+n(R_{1})+(t(e_{BL}(R)))-2)=n(R_{BL})+t(e_{BL}(R))+2$

  3. (3)

$n(R_{BL}\cup R_{1}\cup R_{2})=n(R_{BL})+n(R_{1}\cup
R_{2})+t(e_{BL}(R)))=n(R_{BL})+t(e_{BL}(R))+4$

If $t(e_{BL}(R))=0$, then one of the 3 cuts is a good cut by lemma:tech:a.

Otherwise $t(e_{BL}(R))=-2$, thus either one of the 3 cuts is a good cut or
$n(R_{BL})\equiv 4,10\bmod 16$. Let $S$ be the rectangle for which
$e_{BL}(R)=\\{R,S\\}$. Since $e_{BL}(R)$ is a 1-cut containing the top side of
$S$, we cannot have $\deg(S)=3$, as it contradicts the choice of $R$. We
distinguish between two cases.

##  Case 4.1.1 $\deg(S)=1$

Let $U=R^{\prime}\cup R\cup R_{BL}\cup R_{BR}$, which is depicted on
fig:topside3cuts:before. It is easy to see that $L_{1}(Q_{1},U_{2}^{1})$,
$L_{2}(Q_{1}\cup Q_{2},U_{2}^{2})$, and $L_{3}(Q_{1}\cup Q_{2}\cup
Q_{3},U_{2}^{3})$ in fig:topside3cuts:after is a good cut-system of $U$.

(a)

(b)

Figure 10:

As all 4 vertices of $S$ are contained in $\ker\\{L_{1},L_{2},L_{3}\\}$, we
can extend this good cut-system to $P$ by reattaching $S_{TL}$, $S_{BL}$,
$S_{TR}$ (if non-empty) via lemma:extendconsecutives. Therefore $P$ has a good
cut.

##  Case 4.1.2 $\deg(S)=2$

Let $f$ be the edge of $S$ which is different from $e_{BL}(R)=e_{TL}(S)$. Let
the partition generated by it be $f(P_{1}^{f},P_{2}^{f})$, where $S\subseteq
P_{2}^{f}$. We have $n(P_{1}^{f})=n(R_{BL})-n(S)-t(f)$.

  * 1.

If $t(f)=-2$, then $n(P_{1}^{f})\equiv 2,8\bmod 16$, so $f$ is a good cut by
lemma:tech:a.

  * 2.

If $t(f)=0$, then $n(P_{1}^{f})\equiv 0,6\bmod 16$, so $f$ is a good cut by
lemma:tech:b.

##  Case 4.2 Every rectangle of degree $\geq 3$ is such that its top and
bottom side are not entirely contained by any of their neighboring rectangle

Let $R$ be a rectangle of degree $\geq 3$ and $e=\\{R,S\\}$ be one of its
edges. Let the partition generated by $e$ be $e(P_{1}^{e},P_{2}^{e})$, where
$R\subset P_{1}^{e}$ and $S\subseteq P_{2}^{e}$. If $e$ is a 1-cut then by the
assumptions of this case $\deg(S)\leq 2$.

  * 1.

If $\deg(S)=1$ and $t(e)=-2$, then $n(P_{2}^{e})+t(e)=2$.

  * 2.

If $\deg(S)=1$ and $t(e)=0$, then $n(P_{2}^{e})+t(e)=4$.

  * 3.

If $\deg(S)=2$ and one of the edges of $S$ is a 0-cut, then $P$ has a good cut
by claim:deg2doublecut.

  * 4.

If $\deg(S)=2$ and both edges of $S$, $e$ and (say) $f$ are 1-cuts: Let the
partition generated by $f$ be
$P=P_{1}^{f}\mathop{\overset{\star}{\cup}}P_{2}^{f}$, such that $S\in
P_{1}^{f}$. Then $n(P_{2}^{e})=n(P_{2}^{f})+n(S)+t(f)=n(P_{2}^{f})+2$. Either
one of $e$ and $f$ is a good cut, or by lemma:tech:a we have
$n(P_{2}^{f})\equiv 4,10\mod 16$. In other words, $n(P_{2}^{e})+t(e)\equiv
4,10\mod 16$. Similarly, $n(P_{1}^{f})=n(P_{1}^{e})+4-2=n(P_{1}^{e})+2$, so
$n(P_{1}^{e})\equiv 4,10\mod 16$.

  * 5.

If $\deg(S)\geq 3$, then $t(e)=0$. Either $e$ is a good cut, or by
lemma:tech:b we have $n(P_{2}^{e})+t(e)\equiv 4,10\mod 16$. lemma:tech:b also
implies $n(P_{1}^{e})\equiv 4,10\mod 16$.

From now on, we assume that none of the edges of the neighbors of a degree
$\geq 3$ rectangle represent a good cut, so in particular we have

$n(P_{2}^{e})+t(e)\equiv 2,4,\text{ or }10\mod 16.$

In addition to the simple analysis we have just conducted, we deduce an easy
claim to be used in the following subcases.

######  Claim 19.

Let $R\in V(T)$ be of degree $\geq 3$ and suppose both $R_{BR}\neq\emptyset$
and $R_{TR}\neq\emptyset$. Then $P$ has two admissible cuts $L_{1}$ and
$L_{2}$ such that they form a good cut-system or

$\begin{array}[]{rl}\textbf{(i)}&\text{one of the parts generated by $L_{1}$
has size
}\Big{(}n(R_{BR})+t(e_{BR}(R))\Big{)}+\Big{(}n(R_{TR})+t(e_{TR}(R))\Big{)}+2,\\\
\mbox{}&\textbf{\quad and }\\\ \textbf{(ii)}&\text{one of the parts generated
by $L_{2}$ has size
}\Big{(}n(R_{BR})+t(e_{BR}(R))\Big{)}+\Big{(}n(R_{TR})+t(e_{TR}(R))\Big{)}+4.\end{array}$

###### Proof.

Let $U=R\cup R_{BL}\cup R_{BR}$. Let $L_{1}(U_{1}^{1},U_{2}^{1})$ and
$L_{2}(U_{1}^{2},U_{2}^{2})$ be the vertical cuts of $U$ defined by the two
reflex vertices of $U$ that are on the boundary of $R$, such that
$v_{BR}(R)\in U_{1}^{1}\subset U_{1}^{2}$. By lemma:extend, $L_{1}$ and
$L_{2}$ can be extended to cuts of $V=R\cup R_{BL}\cup R_{BR}\cup R_{TR}$, say
$L_{1}^{\prime}(V_{1}^{1},U_{2}^{1})$, $L_{2}^{\prime}(V_{1}^{2},U_{2}^{2})$.
If one of $L_{1}^{\prime}$ or $L_{2}^{\prime}$ is a 2-cut, then similarly to
claim:deg2doublecut one can verify they form a good cut-system of $V$ which we
can extend to $P$. Otherwise

$\displaystyle n(V_{1}^{1})$ $\displaystyle=n(R\cap
U_{1}^{1})+n(R_{BR})+n(R_{TR})+(t(e_{BR}(R))-2)+t(e_{TR}(R))=$
$\displaystyle=\Big{(}n(R_{BR})+t(e_{BR}(R))\Big{)}+\Big{(}n(R_{TR})+t(e_{TR}(R))\Big{)}+2,$
$\displaystyle n(V_{1}^{2})$ $\displaystyle=n(R\cap
U_{1}^{2})+n(R_{BR})+n(R_{TR})+t(e_{BR}(R))+t(e_{TR}(R))=$
$\displaystyle=\Big{(}n(R_{BR})+t(e_{BR}(R))\Big{)}+\Big{(}n(R_{TR})+t(e_{TR}(R))\Big{)}+4.$

Lastly, we extend $L_{1}^{\prime}$ and $L_{2}^{\prime}$ to $P$ by reattaching
$R_{TL}$ using lemma:extend. This step does not affect the parts $V_{1}^{1}$
and $V_{1}^{2}$, so we are done. ∎

##  Case 4.2.1 There exist at least two rectangles of degree $\geq 3$

In the subgraph $T^{\prime}$ of $T$ which is the union of all paths of $T$
which connect two degree $\geq 3$ rectangles, let $R$ be a leaf and
$e=\\{R,S\\}$ its edge in the subgraph. As defined in the beginning of
case:last, the set of incident edges of $R$ (in $T$) is $\\{e_{i}\ |\ 1\leq
i\leq\deg(R)\\}$, and without loss of generality we may suppose that
$e=e_{\deg(R)}$. The analysis also implies that for all $1\leq i\leq\deg(R)-1$
we have $n(P_{2}^{e_{i}})+t(e_{i})=2,4$.

By the assumptions of this case $\deg(S)\geq 2$, therefore $n(P_{1}^{e})\equiv
4\text{ or }10\mod 16$. If $\deg(S)\geq 3$ let $Q=S$. Otherwise $\deg(S)=2$
and let $Q$ be the second neighbor of $R$ in $T^{\prime}$. The degree of $Q$
cannot be 1 by its choice. If $\deg(Q)=2$, then we find a good cut using
claim:deg2path. In any case, we may suppose from now on that $\deg(Q)\geq 3$.

Let $\\{f_{i}\ |\ 1\leq i\leq\deg(Q)\\}$ be the set of incident edges of $Q$
such that they generate the partitions
$P=P_{1}^{f_{i}}\mathop{\overset{\star}{\cup}}P_{2}^{f_{i}}$ where $R\subset
P_{1}^{f_{i}}$ and $Q\subset P_{2}^{f_{1}}$. We have

$\displaystyle n(P_{1}^{e})$
$\displaystyle=n(R)+\sum_{i=1}^{\deg(R)-1}\Big{(}n(P_{2}^{e_{i}})+t(e_{i})\Big{)}\in
4+\\{2,4\\}+\\{2,4\\}+\\{0,2,4\\}=\\{8,10,12,14,16\\},$

so the only possibility is $n(P_{1}^{e})=10$.

  * 1.

If $\deg(S)\geq 3$, $e$ is a 2-cut (by the assumption of case:last), so by
lemma:tech:c either $e$ is a good cut or $n(P)\equiv 14\bmod 16$. Since $Q=S$
and $e=f_{1}$, we have

$\displaystyle n(P_{1}^{f_{1}})+t(f_{1})$ $\displaystyle=n(P_{1}^{e})+t(e)=10$
$\displaystyle n(P_{2}^{f_{1}})$
$\displaystyle=n(P)-n(P_{1}^{f_{1}})-t(f_{1})\equiv 14-10\equiv 4\bmod 16.$

  * 2.

If $\deg(S)=2$, either $e$ is a 1-cut or we find a good cut using
claim:deg2doublecut. Also, $f_{1}=\\{S,Q\\}$ is a 1-cut too (otherwise apply
claim:deg2doublecut), so

$n(P_{1}^{f_{1}})+t(f_{1})=n(P_{1}^{e})+n(S)+t(e)+t(f_{1})=10.$

By lemma:tech:c, either $f_{1}$ is a good cut (as $n(P_{1}^{f_{1}})=12$) or
$n(P)\equiv 14\bmod 16$. Thus

$n(P_{2}^{f_{1}})=n(P)-n(P_{1}^{f_{1}})-t(f_{1})\equiv 14-12+2\equiv 4\bmod
16$

We have

$\displaystyle n(P)$
$\displaystyle=n(Q)+\Big{(}n(P_{1}^{f_{1}})+t(f_{1})\Big{)}+\sum_{i=2}^{\deg(Q)}\Big{(}n(P_{2}^{f_{i}})+t(f_{i})\Big{)}\in$
$\displaystyle\in 14+\\{2,4,10\\}+\\{2,4,10\\}+\\{0,2,4,10\\}\mod 16.$

The only way we can get $14\bmod 16$ on the right hand side is when
$\deg(Q)=4$ and out of

$n(Q_{BL}),n(Q_{BR}),n(Q_{TL}),n(Q_{TR})\mod 16$

one is $2$, another is $4$, and two are $10\bmod 16$.

The last step in this case is to apply claim:opposite to $Q$. If it does not
give a good cut-system then it gives an admissible cut where one of the parts
has size congruent to $2+10+2=14$ or $2+4+2=8$ modulo 16, therefore we find a
good cut anyway.

##  Case 4.2.2 There is exactly one rectangle of degree $\geq 3$

Let $R$ be the rectangle of degree $\geq 3$ in $T$, and let $\\{e_{i}\ |\
1\leq i\leq\deg(R)\\}$ the edges of $R$, which generate the partitions
$P=P_{1}^{e_{i}}\mathop{\overset{\star}{\cup}}P_{2}^{e_{i}}$ where $R\subset
P_{1}^{e_{i}}$. Then $P_{2}^{e_{i}}$ is path for all $i$. If either
claim:deg2doublecut or claim:deg2path can be applied, $P$ has a good cut. The
remaining possibilities can be categorized into 3 types:

$\begin{array}[]{lllll}\text{Type 1: }&t(e_{i})=-2,&n(P_{2}^{e_{i}})=4,&\text{
and }&n(P_{2}^{e_{i}})+t(e_{i})=2;\\\ \text{Type 2:
}&t(e_{i})=-2,&n(P_{2}^{e_{i}})=4+4-2=6,&\text{ and
}&n(P_{2}^{e_{i}})+t(e_{i})=4;\\\ \text{Type 3:
}&t(e_{i})=0,&n(P_{2}^{e_{i}})=4,&\text{ and
}&n(P_{2}^{e_{i}})+t(e_{i})=4.\end{array}$

Without loss of generality $R_{BR}\neq\emptyset$ and $R_{TR}\neq\emptyset$. We
will now use claim:opposite. If it gives a good cut-system, we are done.
Otherwise

  * 1.

If exactly one of $e_{BR}(R)$ and $e_{TR}(R)$ is of type 1, apply
claim:opposite:2: it gives an admissible cut which cuts off a subpolyomino of
size $2+4+2=8$, so $P$ has a good cut.

  * 2.

If both $e_{BR}(R)$ and $e_{TR}(R)$ are of type 1, apply claim:opposite:4: it
gives an admissible cut which cuts off a subpolyomino of size $2+2+4=8$, so
$P$ has a good cut.

  * 3.

If none of $e_{BR}(R)$ and $e_{TR}(R)$ are of type 1 and $n(P)\not\equiv
14\pmod{16}$, apply claim:opposite:2: it gives an admissible cut which cuts
off a subpolyomino of size $4+4+4=12$, which is a good cut by lemma:tech:c.

Now we only need to deal with the case where $n(P)=14$ and neither $e_{BR}(R)$
nor $e_{TR}(R)$ is of type 1.

If $R$ still has two edges of type 1, again claim:opposite:2 gives a good cut
of $P$. If $R$ has at most one edge of type 1, we have

$14=n(P)=n(R)+\sum_{i=1}^{\deg(R)}\Big{(}n(P_{2}^{e_{i}})+t(e_{i})\Big{)}\in
4+\\{2,4\\}+\\{4\\}+\\{4\\}+\\{0,4\\}=\\{14,16,18,20\\},$

and the only way we can get $14$ on the right hand is when $\deg(R)=3$ and
both $e_{BR}(R)$ and $e_{TR}(R)$ are of type 2 or 3 while the third incident
edge of $R$ is of type 1. We may assume without loss of generality that the
cut represented by $e_{TR}(R)$ is longer than the cut represented by
$e_{BR}(R)$.

  * 1.

If $P$ is vertically convex, its vertical cut tree is a path, so it has a good
cut as deduced in case:Tisapath.

  * 2.

If $P$ is not vertically convex, but $e_{TR}(R)$ is a type 2 edge of $R$, such
that the only horizontal cut of $R_{TR}$ is shorter than the cut represented
by $e_{TR}(R)$, then $P^{\prime}=P-R_{BR}$ is vertically convex, and has
$(10-4)/2=3$ reflex vertices. By claim:deg2doublecut or claim:deg2path,
$P^{\prime}$ has a good cut-system such that its kernel contains $v_{BR}(R)$,
since its $x$ coordinate is maximal in $P^{\prime}$. lemma:extendconsecutives
states that $P$ also has a good cut-system.

  * 3.

Otherwise we find that the top right part of $P$ looks like to one of the
cases in fig:44. It is easy to see that in all three pictures $L$ is an
admissible cut which generates two subpolyominoes of 8 vertices.

(a)

(b)

(c)

Figure 11:

The proof of thm:mobile is complete. To complement the formal proof, we now
demonstrate the algorithm on fig:partition.

Figure 12: The output of the algorithm on a polyomino $n=52$ vertices.

First, we resolve a corridor via the $L$-cut 1, which creates two pieces of 20
and 34($\equiv 2\bmod 16$) vertices. As a result of this cut, a new corridor
emerges in the 20-vertex piece, so we cut the polyomino at 2, cutting off a
piece of 8 vertices. The other piece of 14 vertices containing two pockets is
further divided by 3 into a piece of 6 and 8 vertices. Another pocket is dealt
with by cut 4, which divides the polyomino into an 8- and a 28-vertex piece.
To the larger piece, case:last applies, and we find cut 5, which produces a
16- and a 14-vertex piece. The 16-vertex piece is cut into two 8-vertex pieces
by 6. Lastly, fig:44:c of case:last2 applies to the 14-vertex piece, so cut 7
divides it into two 8-vertex pieces.

We got lucky with cuts 2 and 6 in the sense that they both satisfy the
inequality in (1) strictly. Hence, only 8 pieces are needed to partition the
polyomino on fig:partition into polyominoes of $\leq 8$-vertex pieces, instead
of the upper bound of $(3\cdot 52+4)/16=10$.

##  5 Conclusion

We have not dealt with algorithmic aspects yet in this paper, but the proof
given in the previous section can easily be turned into an $O(n^{2})$
algorithm which partitions $P$ into at most
$\left\lfloor\frac{3n+4}{16}\right\rfloor$ simple polyominoes. The running
time can be improved to $O(n)$ by using linear-time triangulation [2] to
construct the horizontal cut tree of $P$ (such that the edge list of a vertex
is ordered by the $x$ coordinates of the corresponding cuts) and a list of
pockets, corridors, and rectangles of case:toporbotcontained, all of which can
be maintained in $O(1)$ for the partitions after finding and performing a cut
in $O(1)$.

thm:mobile fills a gap between two already established (sharp) results: in [3]
it is proved that polyominoes can be partitioned into at most
$\lfloor\frac{n}{4}\rfloor$ polyominoes of at most 6 vertices, and in [4] it
is proved that any polyomino in general position (a polyomino without 2-cuts)
can be partitioned into $\lfloor\frac{n}{6}\rfloor$ polyominoes of at most
$10$ vertices. However, we do not know of a sharp theorem about partitioning
polyominoes into polyominoes of at most 12 vertices.

Furthermore, for $k\geq 4$, not much is known about partitioning (not
necessarily simply connected) orthogonal polygons into polyominoes of at most
$2k$ vertices. According to the “metatheorem,” the first step in this
direction would be proving that an orthogonal polygon of $n$ vertices with $h$
holes can be partitioned into $\lfloor\frac{3n+4h+4}{16}\rfloor$ polyominoes
of at most 8 vertices. This would generalize the corresponding art gallery
result in [4, Thm. 5.].

## Acknowledgment

The authors would like to thank Joseph O’Rourke and an anonymous referee for
their helpful comments and remarks.

## References

  * Aggarwal [1984] Aggarwal, A., 1984.  The art gallery theorem: its variations, applications, and algorithmic aspects.  Ph.D. thesis. Johns Hopkins University.
  * Chazelle [1991] Chazelle, B., 1991.  Triangulating a simple polygon in linear time.  Discrete & Computational Geometry 6, 485–524.
  * Győri [1986] Győri, E., 1986.  A short proof of the rectilinear art gallery theorem.  SIAM J. Algebraic Discrete Methods 7, 452–454.  URL: http://dx.doi.org/10.1137/0607051, doi:10.1137/0607051.
  * Győri et al. [1996] Győri, E., Hoffmann, F., Kriegel, K., Shermer, T., 1996\.  Generalized guarding and partitioning for rectilinear polygons.  Computational Geometry 6, 21–44.
  * Hoffmann and Kaufmann [1991] Hoffmann, F., Kaufmann, M., 1991\.  On the rectilinear art gallery problem—algorithmic aspects, in: Graph-theoretic concepts in computer science (Berlin, 1990). Springer, Berlin. volume 484 of Lecture Notes in Comput. Sci., pp. 239–250.  URL: http://dx.doi.org/10.1007/3-540-53832-1_46, doi:10.1007/3-540-53832-1_46.
  * Kahn et al. [1983] Kahn, J., Klawe, M., Kleitman, D., 1983.  Traditional galleries require fewer watchmen.  SIAM J. Algebraic Discrete Methods 4, 194–206.  URL: http://dx.doi.org/10.1137/0604020, doi:10.1137/0604020.
  * O’Rourke [1987] O’Rourke, J., 1987.  Art gallery theorems and algorithms.  International Series of Monographs on Computer Science, The Clarendon Press, Oxford University Press, New York.


# An accreting stellar binary model for active periodic fast radio bursts

Can-Min Deng  GXU-NAOC Center for Astrophysics and Space Sciences, Department
of Physics, Guangxi University, Nanning 530004, China<EMAIL_ADDRESS>CAS
Key Laboratory for Research in Galaxies and Cosmology, Department of
Astronomy, University of Science and Technology of China, Hefei 230026, Anhui,
China  Shu-Qing Zhong  CAS Key Laboratory for Research in Galaxies and
Cosmology, Department of Astronomy, University of Science and Technology of
China, Hefei 230026, Anhui, China  Zi-Gao Dai  CAS Key Laboratory for Research
in Galaxies and Cosmology, Department of Astronomy, University of Science and
Technology of China, Hefei 230026, Anhui, China

###### Abstract

In this work, we propose an accreting stellar binary model for understanding
the active periodic fast radio bursts (FRBs). The system consists of a stellar
compact object (CO) and a donor star (DS) companion in an eccentric orbit,
where the DS fills its own Roche lobe near the periastron. The CO accretes the
material from the DS and then drive relativistic magnetic blobs. The
interaction between the magnetic blobs and the stellar wind of the DS produces
a pair of shocks. We find that both of the reverse shock and the forward shock
are likely to produce FRBs via synchrotron maser mechanism. We show that this
system can in principle sufficiently produce highly active FRBs with a long
lifetime, and also can naturally explain the periodicity and the duty cycle of
the activity as appeared in FRBs 180916 and 121102. The radio nebula excited
by the long-term injection of magnetic blobs into the surrounding environment
may account for the associated persistent radio source. In addiction, we
discuss the possible multi-wavelength counterparts of FRB 180916 in the
context of this model. Finally, we encourage the search for FRBs in the
ultraluminous X-ray sources.

fast radio bursts —stars: black hole—stars: neutron star—radiation mechanisms:
non-thermal

##  1 Introduction

Fast radio bursts (FRBs) are intense radio transients with extremely short
duration, and their physical origin is a mystery (Cordes & Chatterjee, 2019;
Petroff et al., 2019; Zhang, 2020; Xiao et al., 2021). Observationally, some
FRBs showed repeat bursts, but most bursts did not (Spitler et al., 2016;
Fonseca et al., 2020; James et al., 2020). It is also a mystery whether all of
FRBs have the same origin (Palaniswamy et al., 2018; Caleb et al., 2018,
2019).

Chime/Frb Collaboration et al. (2020) found a 16.35-day periodicity in FRB
180916 with a 4.0-day phase window, implying a duty cycle $\rm{D}\simeq 0.24$
of activity. In addiction, Rajwade et al. (2020) reported a possible 157-day
periodicity in the FRB 121102 with a duty cycle $\rm{D}\simeq 0.56$. These are
very important clues for studying the physical origin of the FRBs. For such a
periodicity, it may be explained, either by the orbital period of the binary
sysytem (Zhang, 2020; Lyutikov et al., 2020; Ioka & Zhang, 2020; Gu et al.,
2020; Mottez et al., 2020; Dai & Zhong, 2020), or precession of the emitter
(Yang & Zou, 2020; Levin et al., 2020; Zanazzi & Lai, 2020; Tong et al., 2020;
Katz, 2020).

Recently, CHIME/FRB Collaboration et al. (2020) and Bochenek et al. (2020)
reported a single FRB (FRB 200428) with two pulses in association with an
active Galactic magnetar SGR 1935+2154, which is located at a distance $\sim
9$ kpc (Zhong et al., 2020). Moreover, it is found that an X-ray burst is
almost simultaneous with the FRB (Li et al., 2020; Mereghetti et al., 2020;
Ridnaia et al., 2020; Tavani et al., 2020). But strangely, no more FRBs were
observed during the active phase of this magnetar (Lin et al., 2020). In any
case, this discovery shows that at least a part of the FRBs are produced by
the magnetars (Lyubarsky, 2014; Beloborodov, 2017; Metzger et al., 2019).
However, an important lesson learned from FRB 200428 is that extragalactic
analogues of Galactic magnetars could explain some of the FRB population, but
much more active sources are still required to be invoked to explain the
highly active periodic repeaters like FRBs 121102 and 180916 (CHIME/FRB
Collaboration et al., 2020). If the active repeaters are also powered by
magnetars, they must be produced by a type of rare and active magnetars not
seen in the Milky Way (Mereghetti et al., 2020; Lu et al., 2020).

In addition, the observations on the environment of FRB 180916 found that it
is 250 pc away from the nearest young stellar clump and suggested that its age
may be $\sim$ Myr, which in line with the hypothesis that the high-mass X-ray
binaries or gamma-ray binaries are the progenitors rather than the young
magnetars (Tendulkar et al., 2020). Moreover, Pastor-Marazuela et al. (2020)
rule out the scenario in which companion winds cause FRB periodicity by using
simultaneous Apertif and LOFAR data. Motivated by those observation results
mentioned above, we propose an alternative model for understanding the highly
active repeating FRBs with periodicity in this work. The model consists of a
stellar compact object (CO) and a donor star (DS) with its filled Roche lobe,
in which the CO can be a neutron star (NS) or a black hole (BH). We will show
that this model can explain the actively repeating FRBs themselves and their
periodicity behaviors, as the cases FRBs 180916 and 121102.

Sridhar et al. (2021) also link the periodic FRBs to the accreting binaries.
In Sridhar et al. (2021), the FRBs are produced by the interaction of the
intermittent jets (high luminosity)with the quiescent jet (low luminosity).
However, in this work, we discuss the process by which magnetic blobs interact
with the donor star’s wind to produce FRBs. This is the key difference between
this work and theirs.

##  2 The model

In this section, we propose a binary model for active repeating FRBs. The
binary system consists of a stellar CO and a DS. The CO may be a BH or a NS.
As illustrated in Figure 1, when the DS fills its Roche lobe, significant mass
transfer will occur from the DS to the CO. Then an accretion disc will form
around the CO. As we know, jets are widely present in the accretion systems.
However, in addition to the usual continuous jets, the accretion process may
also produce episodic jets. The energetic, collimating episodic jets had been
observed in active galactic nuclei, stellar binaries, and protostars. For
instance, in the X-ray binaries, episodic jets are usually observed during
their X-ray outbursts and intense radio fares (Fender et al., 2004; Zhang &
Yu, 2015). Practical models and numerical simulation suggested that the
episodic jets may be driven by magnetic instability in the accretion disc
(Yuan et al., 2009; Yuan & Zhang, 2012; Zhao et al., 2020). Because of shear
and turbulent motion of the accretion flow, a flux rope system is expected to
form near the disc. The energy is accumulated and stored in the system until a
threshold is reached, then the system loses its equilibrium and the energy
will be released in a catastrophic way, i.e. ejecting episodic magnetic blobs.
By assuming the accretion flow is advection dominated, the available isotropic
free magnetic energy of one blob is (Yuan & Zhang, 2012)

$E_{\rm{f}}\sim
10^{42}~{}f_{\rm{b,-3}}^{-1}\alpha^{-1}_{-2}\beta_{-1}\left(\frac{{{\dot{M}_{a}}}}{10^{-5}M_{\odot}/\rm{yr}}\right)\left(\frac{{{M}}}{3M_{\odot}}\right)~{}\hat{r}_{\rm{2}}^{1/2}~{}\rm{erg}.$
(1)

Here we consider the magnetic blobs is ejected in a collimated angle, and
$f_{\rm{b}}=(1-\cos\theta)/2$ is the beaming factor, $\theta$ is the jet
opening angle111 In the context of this model, the jets are ultra-
relativistic, as shown in Eq.(6). And the ultra-relativistic jets are usually
collimated. Considering the jets with an opening angle $\theta$ equivalent to
the reciprocal of the Lorentz factor $\Gamma$ i.e. $\theta\sim 1/\Gamma$, we
have $f_{b}\sim 1/\Gamma^{2}\sim O(10^{-4}-10^{-3})$ according to Eq.(6). .
Here, we consider a beaming factor $f_{\rm{b}}\sim 10^{-3}$. $\alpha$ is the
viscous parameter, $\beta$ is the ratio of the magnetic pressure over the
total pressure in the accretion disc. We adopt $\alpha=0.01$ and $\beta=0.1$
as typical values. $\dot{{M_{a}}}$ is the mass accretion rate, $M$ is the mass
of the CO, $\hat{r}$ is the radius, where the magnetic blobs is formed, in
units of $2GM/c^{2}$. Here and hereafter, we employ the short-hand notation
$q_{x}=q/10^{x}$ in cgs units.

On the other hand, the binary system is surrounded by the stellar wind from
the DS. Therefore, we suggest that interaction between the magnetic blobs and
the stellar wind could lead to shock formation, and then this shock process
would produced powerful coherent radiation (FRBs) through the synchrotron
maser mechanism analogy to the flaring magnetar models (Lyubarsky, 2014;
Beloborodov, 2017; Metzger et al., 2019). Taking FRB 180916 as a template, the
typical energy of the bursts is $\sim 10^{37}-10^{38}$ erg (CHIME/FRB
Collaboration et al., 2020). In fact, it turns out that the typical energy of
FRB 121102 and of FRB 180916 are similar, found by recent observations
(Pastor-Marazuela et al., 2020; Li et al., 2021). Also one will see from
Eq.(17), $E_{\rm{f}}=10^{42}$ erg is reasonable to power FRB 180916 and
121102. According to equation (1), a mass accretion rate $\sim
10^{-5}M_{\odot}/\rm{yr}$ is required. Note that this high accretion rate
$\dot{{M_{a}}}\sim 10^{-5}M_{\odot}/\rm{yr}$ can occur in high mass Roche lobe
filling binaries, such as SS433 which is accreting at a rate of $\sim
10^{-4}M_{\odot}/\rm{yr}$ (Fabrika, 2004). Moreover, Wiktorowicz et al. (2015)
showed that the Roche lobe overflow rate can be up to
$10^{-3}M_{\odot}/\rm{yr}$ in if the DS is evolving in the Hertzsprung gap.

Figure 1: Schematic illustration of the model in this work: (a) the DS fills
its Roche lobe when orbiting near the periastron, and mass transfer to the CO
occurs; (b) The transfer of mass leads to the formation of accretion disc
around the CO. Magnetic blobs are ejected from the accretion disc due to
magnetic instability. The magnetic blobs may accelerate to the Lorentz factor
$\Gamma\sim\sigma_{0}$ (Yuan & Zhang, 2012), where $\sigma_{0}$ is the initial
magnetization parameter of the blobs. Then the blobs interact with the stellar
wind, which is driven by the DS and immerses itself around the binary system,
to induce shocks powering FRBs by the synchrotron maser mechanism; (c) The
interactions of the magnetic blobs and the stellar wind produce FRBs. Long
term energy injection into the surrounding medium procduce a nebulae which
powers the persistent raido source associated with the FRB.

The wind emerged from the DS is filled around the CO, and its density
distribution $n_{\rm{w}}$ can be estimated as

$n_{\rm{w}}=\frac{\dot{M}_{\rm{w}}}{4\pi
m_{\rm{p}}R^{2}v_{\rm{w}}},~{}~{}R\simeq\left(r^{2}+a^{2}\right)^{1/2}$ (2)

where $\dot{M}_{\rm{w}}$ is the wind mass loss rate of the DS, $v_{\rm{w}}$ is
the speed of the wind. $a$ a is the semimajor axis of the binary, $r$ is the
distance from the CO. For $r\ll a$, we have

$n_{\rm{w}}\simeq 1.0\times
10^{3}~{}\dot{m}_{\rm{w,-11}}\beta_{\rm{w,-2}}^{-1}a_{13}^{-2}~{}\rm{cm}^{-3}$
(3)

where $\dot{m}_{\rm{w}}=\dot{M}_{\rm{w}}/(M_{\odot}/\rm{yr})$,
$\beta_{\rm{w}}=v_{\rm{w}}/c$, $c$ is the speed of light. We adopt
$\beta_{\rm{w}}=0.01$ as typical values for massive stars, and adopt
$\dot{m}_{\rm{w}}=10^{-11}$ for self-consistent of the working model.
$a=10^{13}$ cm is motivated by the analysis for FRB 180916 in section 3.

Therefore, according to Sari & Piran (1995), the Lorentz factor of the
blastwave during the early reverse shock crossing phase is
$\Gamma=(n_{\mathrm{ej}}\Gamma_{\mathrm{ej}}^{2}/4n_{\mathrm{w}})^{1/4}$,
where $n_{\mathrm{ej}}\simeq E_{\rm{f}}/(4\pi r^{2}m_{\rm{p}}c^{3}\delta
t\Gamma_{\mathrm{ej}}^{2})$ is the co-moving density in the ejecta at a radius
$r$, $\Gamma_{\mathrm{ej}}$ is the initial Lorentz factor of the ejecta,
$\delta t$ is the duration of the central energy activity. Then we have

$\Gamma\left(r<r_{\mathrm{dec}}\right)=\left(\frac{E_{\rm{f}}\beta_{\mathrm{w}}}{4\dot{M}_{\rm{w}}c^{2}\delta
t}\right)^{1/4}\left(\frac{r}{a}\right)^{-1/2},$ (4)

where

$r_{\mathrm{dec}}\simeq 1.1\times
10^{12}E_{\rm{f,42}}^{1/4}\dot{m}_{\mathrm{w,-11}}^{-1/4}\beta_{\mathrm{w,-2}}^{1/4}\delta
t_{-3}^{1/4}a_{13}^{1/2}~{}\mathrm{cm}$ (5)

is the deceleration radius. One sees that it satisfies $r_{\mathrm{dec}}\ll
a$. Therefore, the Lorentz factor at the deceleration radius is

$\Gamma\left(r_{\mathrm{dec}}\right)\simeq
136~{}E_{\rm{f,42}}^{1/8}\dot{m}_{\mathrm{w,-11}}^{-1/8}\beta_{\mathrm{w,-2}}^{1/8}\delta
t_{-3}^{-3/8}a_{13}^{1/4}~{}.$ (6)

On the other hand, we get the co-moving density in the ejecta at
$r_{\mathrm{dec}}$

$n_{\rm{ej}}\simeq 1.4\times
10^{8}~{}\Gamma_{\rm{ej},2}^{-2}E_{\rm{f,42}}^{1/2}\dot{m}_{\mathrm{w,-11}}^{1/2}\beta_{\mathrm{w,-2}}^{-1/2}\delta
t_{-3}^{-3/2}a_{13}^{-1}\mathrm{~{}cm}^{-3}.$ (7)

Combining Eq.(3) with Eq.(7), one gets that the reverse shock will become
relativistic, which is the case considered in this work, if

$\Gamma_{\rm{ej}}\gtrsim
194~{}E_{\rm{f,42}}^{1/8}\dot{m}_{\mathrm{w,-11}}^{-1/8}\beta_{\mathrm{w,-2}}^{1/8}\delta
t_{-3}^{-3/8}a_{13}^{1/4},$ (8)

according to the condition $\Gamma_{\rm{ej}}^{2}>f\equiv
n_{\rm{ej}}/n_{\rm{w}}$ (Sari & Piran, 1995). In the context of this model,
the reverse shock is ultrarelativistic only for $\Gamma_{\rm{ej}}\gg 10^{2}$,
and is mildly relativistic for $\Gamma_{\rm{ej}}\sim 200$ which is the easier
case to achieve. Can accreting stellar-mass compact objects produce ejecta
with $\Gamma_{\rm{ej}}>100$? As argued in Sridhar et al. (2021), it cannot be
excluded that highly super-Eddington systems are capable for brief periods of
generating outflows with such a large $\Gamma_{\rm{ej}}$. Especially for
ejecta with a large initial magnetization $\sigma_{0}\gg 1$, which is the case
in this work, it can be accelerated to a high Lorentz factor
$\Gamma_{\rm{ej}}\sim\sigma_{0}^{3/2}$ (Drenkhahn, 2002).

Therefore, assuming the reverse shock is mildly relativistic, then Eq.(7) is
reduced to

$n_{\rm{ej}}\simeq 3.7\times
10^{7}~{}E_{\rm{f,42}}^{1/4}\dot{m}_{\mathrm{w,-11}}^{3/4}\beta_{\mathrm{w,-2}}^{-3/4}\delta
t_{-3}^{-3/4}a_{13}^{-3/2}\mathrm{~{}cm}^{-3}.$ (9)

How, if the reverse shock is ultrarelativistic, this is the upper limit for
$n_{\rm{ej}}$.

In previous studies that discussed the production of FRBs by magnetized
shocks, both forward and reverse shocks have been involved (Lyubarsky, 2014;
Waxman, 2017; Beloborodov, 2017; Metzger et al., 2019; Beloborodov, 2020). In
this work, we consider the synchrotron maser emission produced by both reverse
shock and forward shock. And the equipartition of energy in the reverse and
forward shock is assumed in this work for simplicity. The theory of the
synchrotron maser instability has been developed both for isotropic (Sagiv &
Waxman, 2002; Gruzinov & Waxman, 2019) and ring-like (Lyubarsky, 2006)
particle distributions in momentum space, also see a review Lyubarsky (2021).
In our scenario, we consider a weakly magnetized ejecta at the deceleration
radius and a stellar wind which is itself also weakly magnetized (Weber &
Davis, 1967; Sakurai, 1985; Ignace et al., 1998; ud-Doula & Owocki, 2002; Puls
et al., 2008; Harvey-Smith et al., 2010) 222In this regard, the discussions in
detail of the magnetization and magnetic field pattern of the ejecta and the
stellar winds from the DS and their contribution to the rotation measure will
be appear in a forthcoming work.. For the weakly magnetized plasma i.e.
$\sigma\ll 1$, the characteristic frequency measured in the rest frame of the
synchrotron maser may be given by (Sagiv & Waxman, 2002; Waxman, 2017;
Gruzinov & Waxman, 2019; Lyubarsky, 2021)

$\nu_{\mathrm{c}}\approx\sigma^{-1/4}\nu_{p},$ (10)

where $\sigma$ is the magnetization parameter of the plasma with magnetic
field of $B$ and number density of $n$,

$\sigma=\frac{B^{2}}{4\pi n\gamma_{p}m_{p}c^{2}}.$ (11)

The magnetization $\sigma$ is a very uncertain and difficult parameter to
know, so it can be regarded as a free parameter in principle in this work. As
an example, in the case of gamma-ray bursts, after the highly magnetized jets
accelerated through magnetic dissipation process, the remaining magnetization
$\sigma_{\rm{ej}}$ may be small $\sim 0.1$ which can naturally account for the
observed high radiative efficiency of most gamma-ray bursts (Zhang & Yan,
2011). The magnetization $\sigma_{\rm{w}}$ of the DS’s wind is more difficult
to determine, but perhaps we can make a very rough estimation. Suppose the DS
have a surface magnetic field strength $B_{\textborn}\sim 10^{2}~{}\rm{G}$, a
radius $R_{\textborn}\sim 10R_{\odot}$, and a mass loss rate
$\dot{m}_{\mathrm{w}}\sim 10^{-10}$ (the range of $\dot{m}_{\mathrm{w}}$
covered in this work is $10^{-9}-10^{-11}$). One gets the magnetization of the
wind, at $r_{\rm{dec}}$, $\sigma_{\rm{w}}\sim 10^{-3}$ (Lamers & Cassinelli,
1999; Harvey-Smith et al., 2010). In addition, it can be seen from Eq.(10)
that the result is only slightly dependent on $\sigma$, so it is not
unreasonable to directly use a rough values of $\sigma$ for orders of
estimation within the range of parameters considered in this model.

Therefore, we adopt $\sigma_{\rm{ej}}=0.1$ for the ejector at
$r_{\mathrm{dec}}$ and $\sigma_{\rm{w}}=10^{-3}$ for the DS’s wind,
respectively. In the context of this work, the material shocked by the reverse
shock and forward shock are both baryon-dominated plasma. Therefore, the
plasma frequency $\nu_{p}$ is determined by (Sagiv & Waxman, 2002)

$\nu_{p}=\left(\frac{n_{e}e^{2}}{\pi\gamma_{e}m_{e}}+\frac{n_{p}e^{2}}{\pi\gamma_{p}m_{p}}\right)^{1/2},$
(12)

where $\gamma_{e}$ and $\gamma_{p}$ are the Lorentz factor of the electrons
and the protons, respectively. Assuming that the electrons are near
equilibrium with the protons with $\gamma_{e}m_{e}\sim\gamma_{p}m_{p}$ in the
downstream, we get the characteristic frequency of the synchrotron maser
produced by the reverse shock and the forward shock, respectively, measured in
the observed frame,

$\nu_{\rm{pk}}\approx\left\\{\begin{array}[]{l}\Gamma\sigma_{\rm{ej}}^{-1/4}\left(\frac{8n_{\rm{ej}}e^{2}}{\pi
m_{p}}\right)^{1/2}\simeq
0.88~{}\sigma_{\rm{ej,-1}}^{-1/4}E_{\rm{f,42}}^{1/4}\dot{m}_{\mathrm{w,-11}}^{1/4}\beta_{\mathrm{w,-2}}^{-1/4}\delta
t_{-3}^{-3/4}a_{13}^{-1/2}~{}\rm{GHz},~{}\mathrm{for~{}reverse~{}shock}\\\ \\\
\Gamma\sigma_{\rm{w}}^{-1/4}\left(\frac{8n_{\rm{w}}e^{2}}{\pi
m_{p}}\right)^{1/2}\simeq
0.01~{}\sigma_{\rm{w,-3}}^{-1/4}E_{\rm{f,42}}^{1/8}\dot{m}_{\mathrm{w,-11}}^{3/8}\beta_{\mathrm{w,-2}}^{-3/8}\delta
t_{-3}^{-3/8}a_{13}^{-3/4}~{}\rm{GHz},~{}\rm{for~{}forward~{}shock}~{}.\end{array}\right.$
(13)

One sees that the maser emission is determined by proton, in contrast to the
case for the pair plasma.

The optical depth due to free–free absorption is estimated as

$\displaystyle\tau_{\mathrm{ff}}(\nu)$
$\displaystyle\sim\frac{4e^{6}}{3k_{\rm{B}}m_{e}c}(\frac{2\pi}{3k_{\rm{B}}m_{e}})^{1/2}\bar{g}_{\mathrm{ff}}r_{\rm{dec}}n_{\rm{w}}^{2}(r_{\rm{dec}})T^{-3/2}\nu^{-2}$
(14) $\displaystyle\sim
10^{-8}~{}\bar{g}_{\mathrm{ff}}E_{\rm{f},42}^{1/4}\dot{m}_{-11}^{7/4}\beta_{\rm{w},-2}^{-7/4}\delta
t_{-3}^{1/4}a_{13}^{-7/2}T_{\rm{w,4}}^{-3/2}\nu_{9}^{-2},$

where $k_{B}$ is the Boltzmann’s constant, $\bar{g}_{\mathrm{ff}}$ is the mean
Gaunt factor, $T_{\rm{w}}=10^{4}$ K is the temperature of the wind of the DS.
For $h\nu/k_{\rm{B}}T_{\rm{w}}\ll
1$,$\bar{g}_{\mathrm{ff}}\simeq(\sqrt{3}/\pi)\ln(2.2k_{\rm{B}}T_{\rm{w}}/h\nu)$,
one has $\bar{g}_{\mathrm{ff}}(\nu_{9},T_{\rm{w},4})\simeq 7$.

The optical depth to Thomson scattering,
$\tau_{\mathrm{T}}\sim\sigma_{\mathrm{T}}r_{\rm{dec}}n_{\rm{w}}(r_{\rm{dec}})\sim
10^{-9}$, is very small. However, due to the extremely high brightness
temperature of FRBs, induced scattering process becomes important (Lyubarsky,
2008; Lyubarsky & Ostrovska, 2016). Because the electrons in downstream of the
shocks are ultrarelativistic, the induce Compton scattering caused by them can
be negligible (Wilson & Rees, 1978). Therefore, the optical depth due to
induced Compton scattering is mainly contributed by the DS’ wind, which is
given by

$\tau_{\rm{IC}}\sim\frac{1}{10}~{}\frac{3\sigma_{T}c}{32\pi
m_{e}}\frac{n_{w}\left(r_{\rm{dec}}\right)E_{\rm{FRB}}(\nu_{\rm{pk}})}{r_{\rm{dec}}^{2}\nu_{\rm{pk}}^{3}}\simeq\left\\{\begin{array}[]{l}77~{}\sigma_{\rm{ej,-1}}^{3/4}\epsilon_{-3}E_{\rm{f},42}^{-1/4}\dot{m}_{\mathrm{w,-11}}^{3/4}\beta_{\mathrm{w,-2}}^{-3/4}\delta
t_{-3}^{7/4}a_{13}^{-3/2},~{}\mathrm{for~{}reverse~{}shock}\\\ \\\
10^{7}~{}\sigma_{\rm{w,-3}}^{3/4}\epsilon_{-3}E_{\rm{f},42}^{1/8}\dot{m}_{\mathrm{w,-11}}^{3/8}\beta_{\mathrm{w,-2}}^{-3/8}\delta
t_{-3}^{5/8}a_{13}^{-3/4},~{}\rm{for~{}forward~{}shock}~{}.\end{array}\right.$
(15)

It can be seen that the the emission at $\nu_{\rm{pk}}$ cannot be transmitted
freely due to the induced Compton scattering. Here, $E_{\rm{FRB}}\sim
10^{39}\epsilon_{-3}E_{\rm{f},42}$ erg is applied, $\epsilon$ is the
efficiency of the synchrotron maser around $\nu=\nu_{\rm{pk}}$. The radiation
efficiency $\epsilon$ of synchron maser is highly uncertain. The PIC
simulations show that the efficiency $\epsilon$ depends on the magnetization
and temperature for pair plasma. Plotnikov & Sironi (2019) found that
$\epsilon\sim 10^{-2}$ for an upstream magnetization $\sigma\sim 0.1$, and it
decreases for $\sigma>1$. When the upstream plasma is non-relativistic, the
$\epsilon$ would be independent of the temperature of the plasma for
$\sigma>1$ (Babul & Sironi, 2020), but it remains unclear for $\sigma\ll 1$.
However, for proton plasma which is the case considered in this work, the
efficiency $\epsilon$ is even less known and has yet to be investigated in
detail (Lyubarsky, 2021). From the point of view of the model’s consistency
with observations, the efficiency should not be too low to account for the
FRBs’ energetics, so we assume the efficiency to be $\epsilon\sim 10^{-3}$ in
this work.

According to equation (15), we have
$\tau_{\rm{IC}}(\nu)=\tau_{\rm{IC}}(\nu_{\rm{pk}})(\nu/\nu_{\rm{pk}})^{-(3+s)}$
if we assume the spectrum as $E_{\rm{FRB}}\propto\nu^{-s}$. As a result, the
observed peak frequency of the radiated spectrum moves to $\nu_{\rm{m}}$ where
$\tau_{\rm{IC}}(\nu_{\rm{m}})=3$,

$\nu_{\rm{m}}\sim\left\\{\begin{array}[]{l}0.88\times
10^{1/(3+s)}\sigma_{\rm{ej,-1}}^{-s/4(3+s)}\epsilon_{-3}^{1/(3+s)}E_{\rm{f,42}}^{(2+s)/4(3+s)}\dot{m}_{\mathrm{w,-11}}^{(6+s)/4(3+s)}\\\
\times\beta_{\mathrm{w,-2}}^{-(6+s)/4(3+s)}\delta
t_{-3}^{-(2+3s)/4(3+s)}a_{13}^{-(6+s)/2(3+s)}~{}\mathrm{GHz},~{}\mathrm{for~{}reverse~{}shock}\\\
\\\ 0.01\times
10^{7/(3+s)}~{}\sigma_{\rm{w,-3}}^{-s/4(3+s)}\epsilon_{-3}^{1/(3+s)}E_{\rm{f,42}}^{(4+s)/4(3+s)}\dot{m}_{\mathrm{w,-11}}^{3(4+s)/8(3+s)}\\\
\times\beta_{\mathrm{w,-2}}^{-3(4+s)/8(3+s)}\delta
t_{-3}^{-(4+3s)/8(3+s)}a_{13}^{-3(4+s)/4(3+s)}~{}\mathrm{GHz},~{}\rm{for~{}forward~{}shock}\end{array}\right.$
(16)

One sees that $\nu_{\rm{m}}$ can account for the emission of FRBs around GHz .
In addiction, during the reverse shock crossing phase $t<\delta t$, this peak
frequency will evolve with the shock decelerates as $\nu_{\mathrm{m}}\propto
t^{-(2+3s)/4(3+s)}$ for the reverse shock, and decelerates as
$\nu_{\mathrm{m}}\propto t^{-(4+3s)/8(3+s)}$ for the forward shock. This
temporally decreasing peak frequency may explain the observed downward
drifting frequency structure in the sub-pulses of some repeating FRBs
(CHIME/FRB Collaboration et al., 2019; Hessels et al., 2019). The drift rate
depends on the specific value of s.

According to the latest observations for FRB 121102, its typical energy also
$\sim 10^{37}-10^{38}$ erg (Li et al., 2021), and $a\sim 10^{13.5}$ cm (see
section 3). If $\dot{m}_{\mathrm{w}}=10^{-9}$, based on Eq.(17), we have
$\nu_{\rm{m}}\simeq
3.83~{}\dot{m}_{\mathrm{w,-9}}^{15/36}a_{13.5}^{-5/6}~{}\mathrm{GHz}$ for the
reverse shock, and $\nu_{\rm{m}}\simeq
1.03~{}\dot{m}_{\mathrm{w,-9}}^{11/16}a_{13.5}^{-11/12}~{}\mathrm{GHz}$ for
the forward shock, by adopting $s=1.5$ (Macquart et al., 2019). This is
consistent with the fact that FRB 121102 has few detection at sub-GHz band
(Houben et al., 2019; Josephy et al., 2019), which may be because the DS in
the case of FRB 121102 has a stronger stellar wind of
$\dot{m}_{\mathrm{w}}\sim 10^{-9}$ than the case of FRB 180916 of
$\dot{m}_{\mathrm{w}}\sim 10^{-11}$.

By definition, the radiation energy around $\nu_{\rm{pk}}$ is
$E_{\rm{FRB}}(\nu_{\rm{pk}})\equiv\epsilon E_{\rm{f}}$, then the radiation
energy around $\nu_{\rm{m}}$ is given by
$E_{\rm{FRB}}(\nu_{\rm{m}})=(\nu_{\rm{m}}/\nu_{\rm{pk}})^{-s}E_{\rm{FRB}}(\nu_{\rm{pk}})$,
namely,

$E_{\rm{FRB},39}(\nu_{\rm{m}})\approx\left\\{\begin{array}[]{l}10^{-s/(3+s)}\sigma_{\rm{ej,-1}}^{-3s/4(3+s)}\epsilon_{-3}^{3/(3+s)}E_{\rm{f,42}}^{s/4(3+s)}\dot{m}_{\mathrm{w,-11}}^{-3s/4(3+s)}\\\
\times\beta_{\mathrm{w,-2}}^{3s/4(3+s)}\delta
t_{-3}^{-7s/4(3+s)}a_{13}^{3s/2(3+s)}~{}\mathrm{erg},~{}\mathrm{for~{}reverse~{}shock}\\\
\\\
10^{-7s/(3+s)}~{}\sigma_{\rm{w,-3}}^{-3s/4(3+s)}\epsilon_{-3}^{3/(3+s)}E_{\rm{f,42}}^{-(3+s)s/8(3+s)}\dot{m}_{\mathrm{w,-11}}^{-3s/8(3+s)}\\\
\times\beta_{\mathrm{w,-2}}^{3s/8(3+s)}\delta
t_{-3}^{-5s/8(3+s)}a_{13}^{3s/4(3+s)}~{}\mathrm{erg},~{}\rm{for~{}forward~{}shock}~{}.\end{array}\right.$
(17)

Since the maser energy is mainly concentrated around $\nu_{\rm{pk}}$ in fact,
the efficiency near the observed frequency may be much lower than $10^{-3}$,
which can be clearly seen from the above equation. That is, the efficiency
near the observed frequency is equal to the $\epsilon$ multiplied by a factor
of less than unity, such as $5^{-s/(3+s)}$ and $10^{-7s/(3+s)}$ for reverse
shock and forward shock, respectively. Then a low radiation efficiency $\sim
10^{-5}~{}(\ll 10^{-3})$ of the radio bursts at the observed frequency band
found in the observations of the galactic burst FRB 200428 (Margalit et al.,
2020) can be understood. Moreover, one sees that the observed energy of the
synchrotron maser from the reverse shock is significantly greater than that
from forward shock. It indicates that the observed energy may exhibit a
bimodal distribution in a single repeating FRB. The energetic bursts come from
reverse shock, while the less energetic bursts come from forward shock. This
may provide an explanation for the bimodal burst energy distribution in FRB
121102 found by FAST recently (Li et al., 2021). A more detailed analysis will
be presented elsewhere.

In this model, according to and Eq. (17), the bursts energy may be adjusted
mainly by the model parameters such as $E_{\rm{f}}$, $\dot{m}_{\mathrm{w}}$
and $a$. For different FRB sources, there may be different model parameters,
which results in different observed energies. Moreover, FRBs may be generated
by both reverse and forward shock and observed by telescopes with different
frequencies and thresholds, so it is very easy to generate diverse observed
distributions of energy. And in order to compare directly with observations
one needs to do detailed modeling, but it is beyond the scope of this work.
One thing needs special attention, Eq. (16) and Eq. (17) are only valid when
$\tau_{\rm{IC}}>3$. And if $\tau_{\rm{IC}}\leq 3$, Eq. (16) and Eq. (17) will
degenerate to $\nu_{\rm{m}}=\nu_{\rm{pk}}$ and $E_{\rm{FRB},39}=1$.

##  3 Constraints from the periodicity and duty cycle

Periodicities has been observed in some X-ray sources, and mechanisms have
been proposed to explain this behavior, mainly including orbital period
modulation(Strohmayer, 2009) and disk/jet precession (Begelman et al., 2006;
Foster et al., 2010), also seen in a review Kaaret et al. (2017).

For periodic FRBs, under the framework of our model, the periodicity might be
explained by the precession of the jets (Katz, 2020, 2021; Sridhar et al.,
2021). However, FRB 180916 shows that the signals is concentrated in a narrow
active window with a duty cycle D $\simeq 0.24$, which is very different from
the cases in the X-ray binaries (Strohmayer, 2009; Foster et al., 2010). As
discussed in the previous section, FRB emission is produced when the DS fills
its own Roche lobe. Therefore, we introduce an eccentric orbit modulation
mechanism to explain the narrow duty cycle. The periodicity may be explained
by periodic orbital motion of the binary and the duty cycle may be explained
by the eccentricity of the orbit. It can be naturally understood by the
picture: the DS fills its Roche lobe when it is near the periastron where the
flaring jets from and the FRB emission is then produced, if the orbit of the
binary is eccentric. After the DS is away from the periastron, the process of
producing FRB emission stops due to significant decrease in accretion rate.

Define the mass ratio $q=M/M_{\rm{x}}$, $M_{\rm{x}}$ is the mass of the CO,
$M$ is the mass of the DS. Then the orbital period of the binary is

$T=2\pi q^{1/2}(1+q)^{-1/2}a^{3/2}(GM)^{-1/2}$ (18)

where $G$ is the gravitational constant, $a$ is the semimajor axis. The
effective radius $R_{\rm{L,0}}$ of the Roche-lobe of the DS at the periastron
can be estimated as (Eggleton, 1983)

$\frac{R_{\mathrm{L,0}}}{a(1-e)}=\frac{0.49q^{2/3}}{0.6q^{2/3}+\ln\left(1+q^{1/3}\right)}\equiv\chi,$
(19)

where $e$ is the orbital eccentricity. With the assumption that the DS is
filled with its Roche lobe, then its average density is

$\bar{\rho}=\frac{3M}{4\pi f_{\rm{RL}}^{3}R_{\rm{L,0}}^{3}},$ (20)

where $f_{\rm{RL}}=R/R_{\rm{L,0}}\gtrsim 1$ is the Roche lobe filling factor,
$R$ is the radiu of the DS. We expect that $f_{\rm{RL}}$ is just slightly
greater than 1, .e., $f_{\rm{RL}}-1\ll 1$. Combining equations (18)-(20), one
gets

$T\simeq(3\pi)^{1/2}f_{q}~{}(1-e)^{-3/2}(G\bar{\rho})^{-1/2},$ (21)

where $f_{q}=q^{1/2}(1+q)^{-1/2}\chi^{-3/2}$. Note that $f_{q}\in(1.4,1.8)$
for $q\gtrsim 0.1$. For simplicity, we take $f_{q}=1.5$ because the parameter
range of interest in this work is $q\gtrsim 0.1$. Thus one can simply deduce
the average density of the DS as

$\bar{\rho}\simeq(1-e)^{-3}\left(\frac{T}{0.21~{}\rm{day}}\right)^{-2}\bar{\rho}_{\odot},$
(22)

where $\bar{\rho}_{\odot}\simeq 1.4~{}\rm{g/cm^{3}}$ is the current average
density of the Sun. It is worth noting that equation (22) is a generalization
of equation (4.10) in Frank et al. (2002), $\bar{\rho}\propto T^{-2}$, namely
generalized from the case of circular orbit to the case of eccentric orbit.
Next, we discuss the constraint on $e$ from the observed duty cycle D.

Without loss of generality, taking the CO as the reference, DS moves on an
elliptic orbit with respect to the CO. The distant from the CO to the DS is
$r(\theta)=a(1-e^{2})/(1+e\cos\theta)$. The DS is at periastron when
$\theta=0$, where $\theta$ is the angle between the vector diameter from the
CO to the DS and the polar axis in the polar coordinate system. For the DS at
different positions, its Roche lobe radius is determined by
$R_{\rm{L,\theta}}=\chi r(\theta)$. Assume that when
$\theta=\pm\alpha~{}(\alpha<\pi)$, the DS can just fill its Roche lobe, i.e.,
$R_{\rm{L,\alpha}}=R$. Then we have

$\frac{1+e}{1+e\cos\alpha}=f_{\rm{RL}}$ (23)

Therefore, according to the Kepler’s second law, the duty cycle of activity
can be calculated as $\rm{D}=\varDelta S/S$, where $\varDelta S$ is the area
swept out by $r(\theta)$ from $-\alpha$ to $\alpha$, and $S$ is the total area
enclosed by the DS’s elliptic orbit. That is

$D=\frac{1}{2\pi}\left(1-e^{2}\right)^{3/2}\int_{-\alpha}^{\alpha}\frac{d\theta}{(1+e\cos\theta)^{2}},$
(24)

where, by letting $\lambda=1-f_{\rm{RL}}^{-1}$,

$\alpha=\left\\{\begin{array}[]{ll}\pi,\quad\lambda(1+e)/(2e)\geqslant 1\\\
\\\
2\arcsin\sqrt{\lambda(1+e)/(2e)},\quad\lambda(1+e)/(2e)<1\end{array}\right.$
(25)

For $\lambda(1+e)/(2e)\geqslant 1$, it means that the DS fills its Roche lobe
throughout the cycle, thus D=1. Therefore, based on the observed duty cycle,
we can discuss the constraint to $e$. Figure 2 shows $e$ as a function of
$\lambda$ for $\rm{D}=0.24$ (FRB 180916) and $\rm{D}=0.56$ (FRB 121102),
respectively. Note that $\lambda=1-f_{\rm{RL}}^{-1}=(R-R_{\rm{L,0}})/R$
describes the degree of the Roche lobe overfilling of the DS at periastron.
One naturally expects $\lambda\ll 1$, otherwise the Roche lobe overflow would
be violent. By adopting $\lambda\leqslant 0.1$, we have $e\leqslant 0.22$ for
FRB 180916 and $e\leqslant 0.08$ for FRB 121102, which are also showed in
figure 2. It can be seen that the required orbital eccentricity is not large.

Figure 2: The orbital eccentricity $e$ as a function of the Roche lobe
overfilling parameter of the DS $\lambda$ for the duty cycle D=0.04 (FRB
180916), D=0.24 (FRB 180916) and D=0.56 (FRB 121102), respectively.

Now we can discuss what kind of DS is needed, in order to explain the
periodicity of FRBs 180916 and 121102. For FRB 180916 $T=16.35$ day and
$e\leqslant 0.22$, one gets $\bar{\rho}\sim\times 10^{-3.5}\bar{\rho}_{\odot}$
according to equation (22). Similarly, for FRB 121102 $T=157$ day and
$e\leqslant 0.08$, one gets $\bar{\rho}\sim 10^{-6}\bar{\rho}_{\odot}$. It
indicates that the DSs might be supergiants. For red supergiants, their
average density can be as low as $10^{-8}\bar{\rho}_{\odot}$. Therefore, we
expect that this model can explain a period up to $T\sim 10^{3}$ day when the
companion is a red supergiant. Note that, however, there is some uncertainty
on the phase window of FRB 180916. It is pointed out in Chime/Frb
Collaboration et al. (2020) that 50% of the CHIME bursts are detected in a
0.6-day phase window, with the event rate dropping rapidly towards the edges
of the active phase, and the duty cycle would be D=0.04 if 0.6 day is the
width of the active phase. Moreover, Pastor-Marazuela et al. (2020) found that
its activity window is narrower at higher frequencies, namely, the full-width
at half-maximum of Apertif bursts is 1.1 day compared to CHIME bursts’ 2.7
day. If one adopts D=0.04, $e\leqslant 0.65$ and the density of the DS for FRB
180916 would be $\bar{\rho}\sim 10^{-2.4}\bar{\rho}_{\odot}$, which is in line
with the massive OB stars.

Moreover, it should be noted that the density obtained according to Eq.(22) is
the average density which means that it is not necessarily the true density of
DS. For example, Be stars, although they themselves are only $\sim
10R_{\odot}$, but their accretion disk radius can be as large as $\sim
100R_{\odot}$ (Rivinius et al., 2013). The CO can accrete material from the
disk of the star, although it does not accrete material from the star itself
directly (Karino, 2021). In this case, for example, for a Be star with a mass
$10M_{\odot}$ and an accretion disk radius $\sim 10-200R_{\odot}$, the
effective average density would be $10^{-2}\bar{\rho}_{\odot}$ to
$10^{-6}\bar{\rho}_{\odot}$. It can be seen that the Be companion is also
consistent with the density requirements in this model.

On the other hand, according to the results in section 2, the model requires a
relatively weak stellar wind environment, specifically $\dot{M_{\rm{w}}}\sim
10^{-11}M_{\odot}/\rm{yr}$ for FRB 180916 and $\dot{M_{\rm{w}}}\sim
10^{-9}M_{\odot}/\rm{yr}$ for FRB 121102 may be appropriate. It is also
strongly constrained by the small DM variations observed in FRB 180916 at the
low frequency bands (Pleunis et al., 2021). Therefore, it is unlikely that the
DSs are supergiants, as they tend to have much stronger wind, unless they
happen to be in periods of cooling and weak wind or if the wind is highly
inhomogeneous/clumpy (Puls et al., 2008; Stairs et al., 2001). As mentioned
above, a cold OB star companion with $\dot{M_{\rm{w}}}\sim
10^{-11}M_{\odot}/\rm{yr}$ may also reasonable for FRB 180916. However, the
DSs are more likely to be Be stars because their polar wind may be relatively
weak (Kervella & Domiciano de Souza, 2006; Kanaan et al., 2008), which could
provide a unified picture for the cases of FRB 180916 and FRB 121102. But then
again, current observations are not enough to tell us exactly what kind of
stars the DSs are, and future observations are needed to provide more clues.
In any case, this model’s requirement for massive stars as DSs is consistent
with the fact that FRB 121102 and FRB 180916 are associated with the star-
forming regions (Chatterjee et al., 2017; Marcote et al., 2020; Tendulkar et
al., 2020).

Given the presence of DS’s wind, one needs to consider its contribution to the
dispersion measure (DM). According to Eq.(3) and Eq.(5), one can roughly
estimate the DM associated with the local wind, ${\rm{DM_{loc}}}\sim
n_{\rm{w}}(r_{\rm{dec}})r_{\rm{dec}}\sim
0.03~{}E_{\rm{f,42}}^{1/4}\dot{m}_{\rm{w,-9}}^{3/4}\beta_{\rm{w,-2}}^{-3/4}\delta
t_{-3}^{1/4}a_{13}^{-3/2}~{}\rm{pc~{}cm^{-3}}$ which is small enough to be
negligible compared to the total DM of FRBs, even if a relatively large wind
rate $\dot{m}_{\rm{w}}\sim 10^{-9}$ is adopted. Therefore, we do not expect
that there is a obvious periodic modulation in the observed DM for FRB 180916B
(Pastor-Marazuela et al., 2020), and of course the same is true for FRB
121102.

Interestingly, the DM of FRB 121102 seems to have a slow growth trend with a
rare of $\sim 0.85~{}\rm{pc~{}cm^{-3}~{}yr^{-1}}$ (Li et al., 2021). Based on
the above analysis, it is clear that the evolution of the DS’s wind is not
sufficient to lead to such an outcome. The DM variation may depend on the
environment in which FRB sources are located. For example, an FRB source in an
expanding SNR around a nearly neutral ambient medium during the deceleration
phases or in a growing H II region can increase DM (Yang & Zhang, 2017). We’re
going to discuss this issue, in the context of this model, in detail
elsewhere.

##  4 Summary and discussions

In this work, we propose a model for understanding the highly active periodic
FRBs. The system consists of a stellar CO and a DS, in which the DS fills with
its own Roche lobe. The CO accretes material from the DS and ejects
relativistic magnetic blobs. The interaction between the magnetic blobs and
the stellar wind of the DS produces a pair of shocks, the reverse shock
traveling through the ejecta and the forward shock traveling to the wind of
the DS. We find that both of these shocks are likely to produce FRBs. The
energy of the FRBs from the reverse shock is greater than that from forward
shock. It indicates that the observed energy in a single repeating FRB may
exhibit a bimodal distribution. This may provide an explanation for the
bimodal burst energy distribution in FRB 121102 found by FAST recently (Li et
al., 2021).

Moreover, such a Roche lobe filling accretion system can in principle
sufficiently powers the highly active periodic FRBs with a long lifetime. The
orbital motion of the binary can explain the periodicity of the FRBs such as
FRBs 180916 and 121102, if the DSs are giants/supergiants or Be stars. To
produce a narrow duty cycle of the activity, such as FRB 180916, the orbit of
the binary needs to be moderately eccentric, with the DS fills the Roche lobe
only near the periastron. It should be noted that for our model to work, it
requires (1) a sufficiently large accretion rate and (2) weak stellar wind
from the DS. If not, if the accretion is too weak, the FRB energy will be too
low to be observed. If the stellar wind is too strong, GHz radiation cannot
pass through freely. And we realize that this is reasonable because FRBs would
have been observed in a large number of binary systems in the Milky Way if it
weren’t for binary systems with the right conditions to produce FRBs. It is
these particular low wind binary systems that produce such rare sources like
FRB 180916 and FRB 121102. Therefore, if this model is correct, it gives us a
great opportunity to study these special binary systems.

Recent observations of FRB 180916 revealed that the bursts activity is
frequency dependent, namely its activity window is both narrower and earlier
at higher frequencies(Pastor-Marazuela et al., 2020; Pleunis et al., 2021).
The causes of this observed phenomenon may be complicated. It may be due to a
combination of the absorption of FRBs by the surrounding invironment and the
instrument selection effects, as show in Li et al. (2021). It may also arise
from the structured and beaming effects of the jet (Sridhar et al., 2021). But
we won’t discuss this issue in this work because it requires detailed modeling
in the contex of this model, and we plan to study it in detail elsewhere.

The more recent observation found subsecond periodicity in FRB 20191221A,
which may indicate that the central engine of this FRB is NS, and the period
corresponds to the rotation period of NS (The CHIME/FRB Collaboration et al.,
2021). However, the duration of this FRB is actually $\sim 3$ seconds, which
is different from any known FRBs, and it has not yet been discovered whether
it repeats, so it may be an entirely new class of FRBs (The CHIME/FRB
Collaboration et al., 2021). Nevertheless, a similar subsecond periodicity is
known to exist in some X-ray binaries, which may result from the rotation of
the accreting NSs (Kaaret et al., 2017; Patruno & Watts, 2021). A similar
periodicity is also expected in gamma-ray bursts (GRBs), although no
unambiguous periodicity has been found in the GRB pulses (Tarnopolski &
Marchenko, 2021, and references therein). In this model, the rotation of the
accreting NS (or the fluctuations in the accretion disc) may also modulate the
accretion process and thus the generation of the jets, and whether it
ultimately results in the production of periodicity in FRB pulses deserves
further study.

It expects that, in the context of this model, the energy injection by the
long-term blobs ejection from the system into the surrounding environment may
excite a radio nebula which can explain the persistent radio source associated
with FRB 121102, inspired by the fact that the Galactic X-ray binaries SS433
does power such a similar radio nebula (Fabrika, 2004). If this model is
correct, the luminosity of the persistent radio source may be estimated as
$L_{\rm{R}}\propto\dot{E}_{\rm{FRB}}^{\gamma}$, where
$\dot{E}_{\rm{FRB}}\equiv~{}{E}_{\rm{FRB}}~{}\Re$, ${E}_{\rm{FRB}}$ is the
typical energy of the FRB, $\Re$ is the repetition rate. Here we adopt
$\gamma=1$ for a rough estimation although the exact valu is expected to be
slightly greater than 1 in the context of synchrotron radiation (Dai et al.,
2017). The typical isotropic energy $\sim 10^{37}$ erg with a repetition rate
$\Re\sim 10^{-1}~{}{\rm{h}}^{-1}$ for FRB 180916 (Pastor-Marazuela et al.,
2020), and a similar isotropic energy but with a much higher repetition rate
$\Re\sim 10^{2}~{}{\rm{h}}^{-1}$ (Li et al., 2021) for FRB 121102, we have
$\dot{E}_{\rm{FRB~{}180916}}/\dot{E}_{\rm{FRB~{}121102}}\sim 10^{-3}$.
Therefore, we predict that the persistent radio emission associated with FRB
180916 would be $\lesssim 10^{35}$ erg/s, which is in line with observational
limit (Marcote et al., 2020).

In addiction, it is expected that the accreting CO will also have persistent
X-ray emission. Assuming solar abundances, the X-ray luminosity of the
accreting accretor is (Shakura & Sunyaev, 1973; Poutanen et al., 2007)

$L_{\rm{X}}\approx 1.3\times
10^{38}\operatorname{erg}/\mathrm{s}\left\\{\begin{array}[]{l}\dot{m}\left(\frac{M_{\rm{x}}}{M_{\odot}}\right),\quad\dot{m}\leqslant
1\\\ (1+\ln\dot{m})\left(\frac{M_{\rm{x}}}{M_{\odot}}\right),\quad
1\leqslant\dot{m}\leqslant 100\end{array}\right.$ (26)

where $\dot{m}=\dot{M}/\dot{M}_{{\rm{Edd}}}$, the super-Eddington accretion
rate $\dot{M}_{{\rm{Edd}}}\simeq 2.3\times
10^{-8}(M_{\rm{x}}/M_{\odot})M_{\odot}/{\rm{yr}}$. Based on the discussions in
section 2, we have $L_{\rm{X}}\sim 10^{38}\operatorname{erg}/\mathrm{s}$ for a
accretion rate $\dot{M}_{a}=10^{-5}M_{\odot}/{\rm{yr}}$, which is below the
detection limit both for FRB 180916 and FRB 121102 (Tavani et al., 2020;
Scholz et al., 2020). However, we expects to detect the X-ray emission from
the accretor for the sources at close distance i.e. a few tens of Mpc. In
addiction, we have confirmed that the prompt gamma-ray emissions radiated by
the thermalized electrons behind the (reverse and forward) shocks associated
with FRB 121102 and FRB 180916 are also expected too dim to be detected by the
current gamma-ray detectors.

Finally, we anticipate that if those active periodic FRBs are observed at
close distances in the future, multiband observations will verify or falsify
our model. Also, we encourage the search for FRBs in the ultraluminous X-ray
sources.

## Acknowledgments

This work is supported by the National Natural Science Foundation of China
(grant No. 12047550), the China Postdoctoral Science Foundation (grant No.
2020M671876) and the Fundamental Research Funds for the Central Universities.
S.Q.Z. is supported by the China Postdoctoral Science Foundation (grant No.
2021TQ0325). ZGD was supported by the National Key Research and Development
Program of China (grant No. 2017YFA0402600), the National SKA Program of China
(grant No. 2020SKA0120300), and the National Natural Science Foundation of
China (grant No. 11833003).

## References

  * Babul & Sironi (2020) Babul, A.-N. & Sironi, L. 2020, MNRAS, 499, 2884.
  * Begelman et al. (2006) Begelman, M. C., King, A. R., & Pringle, J. E. 2006, MNRAS, 370, 399.
  * Beloborodov (2017) Beloborodov, A. M. 2017, ApJ, 843, L26.
  * Beloborodov (2020) Beloborodov, A. M. 2020, ApJ, 896, 142.
  * Bochenek et al. (2020) Bochenek, C. D., Ravi, V., Belov, K. V., et al. 2020, Nature, 587, 59.
  * Caleb et al. (2019) Caleb, M., Stappers, B. W., Rajwade, K., et al. 2019, MNRAS, 484, 5500.
  * Caleb et al. (2018) Caleb, M., Spitler, L. G., & Stappers, B. W. 2018, Nature Astronomy, 2, 839.
  * Chatterjee et al. (2017) Chatterjee, S., Law, C. J., Wharton, R. S., et al. 2017, Nature, 541, 58.
  * Chime/Frb Collaboration et al. (2020) Chime/Frb Collaboration, Amiri, M., Andersen, B. C., et al. 2020, Nature, 582, 351.
  * CHIME/FRB Collaboration et al. (2020) CHIME/FRB Collaboration, Andersen, B. C., Bandura, K. M., et al. 2020, Nature, 587, 54.
  * CHIME/FRB Collaboration et al. (2019) CHIME/FRB Collaboration, Amiri, M., Bandura, K., et al. 2019, Nature, 566, 235.
  * Cordes & Chatterjee (2019) Cordes, J. M. & Chatterjee, S. 2019, ARA&A, 57, 417.
  * Dai & Zhong (2020) Dai, Z. G. & Zhong, S. Q. 2020, ApJ, 895, L1.
  * Dai et al. (2017) Dai, Z. G., Wang, J. S., & Yu, Y. W. 2017, ApJ, 838, L7.
  * Drenkhahn (2002) Drenkhahn, G. 2002, A&A, 387, 714.
  * Eggleton (1983) Eggleton, P. P. 1983, ApJ, 268, 368.
  * Fabrika (2004) Fabrika, S. 2004, Astrophys. Space Phys. Res., 12, 1
  * Fender et al. (2004) Fender, R. P., Belloni, T. M., & Gallo, E. 2004, MNRAS, 355, 1105.
  * Fonseca et al. (2020) Fonseca, E., Andersen, B. C., Bhardwaj, M., et al. 2020, ApJ, 891, L6.
  * Foster et al. (2010) Foster, D. L., Charles, P. A., & Holley-Bockelmann, K. 2010, ApJ, 725, 2480.
  * Frank et al. (2002) Frank, J., King, A., & Raine, D. J. 2002, Accretion Power in Astrophysics, by Juhan Frank and Andrew King and Derek Raine, pp. 398. ISBN 0521620538. Cambridge, UK: Cambridge University Press, February 2002., 398
  * Gruzinov & Waxman (2019) Gruzinov, A. & Waxman, E. 2019, ApJ, 875, 126.
  * Gu et al. (2020) Gu, W.-M., Yi, T., & Liu, T. 2020, MNRAS, 497, 1543.
  * Harvey-Smith et al. (2010) Harvey-Smith, L., Gaensler, B. M., Kothes, R., et al. 2010, ApJ, 712, 1157.
  * Hessels et al. (2019) Hessels, J. W. T., Spitler, L. G., Seymour, A. D., et al. 2019, ApJ, 876, L23.
  * Hjellming & Rupen (1995) Hjellming, R. M. & Rupen, M. P. 1995, Nature, 375, 464.
  * Houben et al. (2019) Houben, L. J. M., Spitler, L. G., ter Veen, S., et al. 2019, A&A, 623, A42.
  * Ignace et al. (1998) Ignace, R., Cassinelli, J. P., & Bjorkman, J. E. 1998, ApJ, 505, 910.
  * Ioka & Zhang (2020) Ioka, K. & Zhang, B. 2020, ApJ, 893, L26.
  * James et al. (2020) James, C. W., Osłowski, S., Flynn, C., et al. 2020, MNRAS, 495, 2416.
  * Josephy et al. (2019) Josephy, A., Chawla, P., Fonseca, E., et al. 2019, ApJ, 882, L18.
  * Kaaret et al. (2017) Kaaret, P., Feng, H., & Roberts, T. P. 2017, ARA&A, 55, 303.
  * Kanaan et al. (2008) Kanaan, S., Meilland, A., Stee, P., et al. 2008, A&A, 486, 785.
  * Karino (2021) Karino, S. 2021, MNRAS, arXiv:2107.11305.
  * Katz (2020) Katz, J. I. 2020, MNRAS, 494, L64. doi:10.1093/mnrasl/slaa038
  * Katz (2021) Katz, J. I. 2021, MNRAS. doi:10.1093/mnras/stab399
  * Kervella & Domiciano de Souza (2006) Kervella, P. & Domiciano de Souza, A. 2006, A&A, 453, 1059.
  * Lamers & Cassinelli (1999) Lamers, H. J. G. L. M. & Cassinelli, J. P. 1999, Introduction to Stellar Winds, by Henny J. G. L. M. Lamers and Joseph P. Cassinelli, pp. 452. ISBN 0521593980. Cambridge, UK: Cambridge University Press, June 1999., 452
  * Levin et al. (2020) Levin, Y., Beloborodov, A. M., & Bransgrove, A. 2020, ApJ, 895, L30.
  * Li et al. (2020) Li, C. K., Lin, L., Xiong, S. L., et al. 2020, arXiv:2005.11071
  * Li et al. (2021) Li, D., Wang, P., Zhu, W. W., et al. 2021, arXiv:2107.08205
  * Li et al. (2021) Li, Q.-C., Yang, Y.-P., Wang, F. Y., et al. 2021, arXiv:2108.00350
  * Lin et al. (2020) Lin, L., Zhang, C. F., Wang, P., et al. 2020, Nature, 587, 63.
  * Lu et al. (2020) Lu, W., Kumar, P., & Zhang, B. 2020, MNRAS, 498, 1397.
  * Lyubarsky (2006) Lyubarsky, Y. 2006, ApJ, 652, 1297.
  * Lyubarsky (2014) Lyubarsky, Y. 2014, MNRAS, 442, L9.
  * Lyubarsky (2008) Lyubarsky, Y. 2008, ApJ, 682, 1443.
  * Lyubarsky & Ostrovska (2016) Lyubarsky, Y. & Ostrovska, S. 2016, ApJ, 818, 74.
  * Lyutikov et al. (2020) Lyutikov, M., Barkov, M. V., & Giannios, D. 2020, ApJ, 893, L39.
  * Lyubarsky (2021) Lyubarsky, Y. 2021, Universe, 7, 56.
  * Macquart et al. (2019) Macquart, J.-P., Shannon, R. M., Bannister, K. W., et al. 2019, ApJ, 872, L19.
  * Marcote et al. (2020) Marcote, B., Nimmo, K., Hessels, J. W. T., et al. 2020, Nature, 577, 190.
  * Margalit et al. (2020) Margalit, B., Beniamini, P., Sridhar, N., et al. 2020, ApJ, 899, L27.
  * Mereghetti et al. (2020) Mereghetti, S., Savchenko, V., Ferrigno, C., et al. 2020, ApJ, 898, L29. doi:10.3847/2041-8213/aba2cf
  * Metzger et al. (2019) Metzger, B. D., Margalit, B., & Sironi, L. 2019, MNRAS, 485, 4091.
  * Mottez et al. (2020) Mottez, F., Zarka, P., & Voisin, G. 2020, A&A, 644, A145.
  * Palaniswamy et al. (2018) Palaniswamy, D., Li, Y., & Zhang, B. 2018, ApJ, 854, L12.
  * Patruno & Watts (2021) Patruno, A. & Watts, A. L. 2021, Astrophysics and Space Science Library, 461, 143.
  * Pastor-Marazuela et al. (2020) Pastor-Marazuela, I., Connor, L., van Leeuwen, J., et al. 2020, arXiv:2012.08348
  * Petroff et al. (2019) Petroff, E., Hessels, J. W. T., & Lorimer, D. R. 2019, A&A Rev., 27, 4.
  * Pleunis et al. (2021) Pleunis, Z., Michilli, D., Bassa, C. G., et al. 2021, ApJ, 911, L3.
  * Plotnikov & Sironi (2019) Plotnikov, I. & Sironi, L. 2019, MNRAS, 485, 3816.
  * Poutanen et al. (2007) Poutanen, J., Lipunova, G., Fabrika, S., et al. 2007, MNRAS, 377, 1187.
  * Puls et al. (2008) Puls, J., Vink, J. S., & Najarro, F. 2008, A&A Rev., 16, 209.
  * Rajwade et al. (2020) Rajwade, K. M., Mickaliger, M. B., Stappers, B. W., et al. 2020, MNRAS, 495, 3551. doi:10.1093/mnras/staa1237
  * Ridnaia et al. (2020) Ridnaia, A., Svinkin, D., Frederiks, D., et al. 2020, arXiv:2005.11178
  * Rivinius et al. (2013) Rivinius, T., Carciofi, A. C., & Martayan, C. 2013, A&A Rev., 21, 69
  * Sagiv & Waxman (2002) Sagiv, A. & Waxman, E. 2002, ApJ, 574, 861.
  * Sakurai (1985) Sakurai, T. 1985, A&A, 152, 121
  * Sari & Piran (1995) Sari, R. & Piran, T. 1995, ApJ, 455, L143. doi:10.1086/309835
  * Scholz et al. (2020) Scholz, P., Cook, A., Cruces, M., et al. 2020, ApJ, 901, 165.
  * Shakura & Sunyaev (1973) Shakura, N. I. & Sunyaev, R. A. 1973, A&A, 500, 33
  * Sironi & Spitkovsky (2011) Sironi, L. & Spitkovsky, A. 2011, ApJ, 726, 75
  * Spitler et al. (2016) Spitler, L. G., Scholz, P., Hessels, J. W. T., et al. 2016, Nature, 531, 202.
  * Sridhar et al. (2021) Sridhar, N., Metzger, B. D., Beniamini, P., et al. 2021, arXiv:2102.06138
  * Stairs et al. (2001) Stairs, I. H., Manchester, R. N., Lyne, A. G., et al. 2001, MNRAS, 325, 979.
  * Strohmayer (2009) Strohmayer, T. E. 2009, ApJ, 706, L210.
  * Tarnopolski & Marchenko (2021) Tarnopolski, M. & Marchenko, V. 2021, ApJ, 911, 20.
  * Tavani et al. (2020) Tavani, M., Casentini, C., Ursi, A., et al. 2020, arXiv:2005.12164
  * Tavani et al. (2020) Tavani, M., Verrecchia, F., Casentini, C., et al. 2020, ApJ, 893, L42.
  * Tendulkar et al. (2020) Tendulkar, S. P., Gil de Paz, A., Kirichenko, A. Y., et al. 2020, arXiv:2011.03257
  * The CHIME/FRB Collaboration et al. (2021) The CHIME/FRB Collaboration, Andersen, B. C., Bandura, K., et al. 2021, arXiv:2107.08463
  * Tong et al. (2020) Tong, H., Wang, W., & Wang, H.-G. 2020, Research in Astronomy and Astrophysics, 20, 142. doi:10.1088/1674-4527/20/9/142
  * ud-Doula & Owocki (2002) ud-Doula, A. & Owocki, S. P. 2002, ApJ, 576, 413.
  * Waxman (2017) Waxman, E. 2017, ApJ, 842, 34.
  * Weber & Davis (1967) Weber, E. J. & Davis, L. 1967, ApJ, 148, 217.
  * Wilson & Rees (1978) Wilson, D. B. & Rees, M. J. 1978, MNRAS, 185, 297.
  * Wiktorowicz et al. (2015) Wiktorowicz, G., Sobolewska, M., Sadowski, A., et al. 2015, ApJ, 810, 20.
  * Xiao et al. (2021) Xiao, D., Wang, F., & Dai, Z. 2021, Science China Physics, Mechanics, and Astronomy, 64, 249501.
  * Yang & Zou (2020) Yang, H. & Zou, Y.-C. 2020, ApJ, 893, L31.
  * Yang & Zhang (2017) Yang, Y.-P. & Zhang, B. 2017, ApJ, 847, 22.
  * Yuan et al. (2009) Yuan, F., Lin, J., Wu, K., et al. 2009, MNRAS, 395, 2183.
  * Yuan & Zhang (2012) Yuan, F. & Zhang, B. 2012, ApJ, 757, 56.
  * Zanazzi & Lai (2020) Zanazzi, J. J. & Lai, D. 2020, ApJ, 892, L15.
  * Zhang (2020) Zhang, B. 2020, ApJ, 890, L24.
  * Zhang (2020) Zhang, B. 2020, Nature, 587, 45.
  * Zhang & Yan (2011) Zhang, B. & Yan, H. 2011, ApJ, 726, 90.
  * Zhang & Yu (2015) Zhang, H. & Yu, W. 2015, MNRAS, 451, 1740.
  * Zhao et al. (2020) Zhao, T.-L., Yuan, Y.-F., & Kumar, R. 2020, MNRAS, 499, 1561.
  * Zhong et al. (2020) Zhong, S.-Q., Dai, Z.-G., Zhang, H.-M., et al. 2020, ApJ, 898, L5.