# VORRT-COLREGs: A Hybrid Velocity Obstacles and RRT Based COLREGs-Compliant
Path Planner for Autonomous Surface Vessels

Rahul Dubey and Sushil J Louis  Computer Science and Engineering, University
of Nevada Reno, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper presents VORRT-COLREGs, a hybrid technique that combines velocity
obstacles (VO) and rapidly-exploring random trees (RRT) to generate safe
trajectories for autonomous surface vessels (ASVs) while following nautical
rules of the road. RRT generates a set of way points and the velocity
obstacles method ensures safe travel between way points. We also ensure that
the actions of ASVs do not violate maritime collision guidelines. Earlier work
has used RRT and VO separately to generate paths for ASVs. However, RRT does
not handle highly dynamic situations well and and VO seems most suitable as a
local path planner. Combining both approaches, VORRT-COLREGs is a global path
planner that uses a joint forward simulation to ensure that generated paths
remain valid and collision free as the situation changes. Experiments were
conducted in different types of collision scenarios and with different numbers
of ASVs. Results show that VORRT-COLREGs generated collision regulations
(COLREGs) complaint paths in open ocean scenarios. Furthermore, VORRT-COLREGs
successfully generated compliant paths within traffic separation schemes.
These results show the applicability of our technique for generating paths for
ASVs in different collision scenarios. To the best of our knowledge, this is
the first work that combines velocity obstacles and RRT to produce safe and
COLREGs complaint path for ASVs.

###### Index Terms:

ASV, COLREGs, RRT, Velocity Obstacles.

##  I Introduction

In recent years, technological advancements have enabled autonomous surface
vessels to operate beside other autonomous and human operated surface vessels
although many challenges still need to be addressed. Safe navigation of ASVs
in dynamic environments is one of many such challenges. In maritime
navigation, each vessel must follow rules from the International Regulations
for Preventing Collision at Sea (commonly known as COLREGs). These rules
prescribe different types of maneuvers that a vessel must perform under
different types of collision scenarios to avoid any unfortunate incidents.
Generating a safe and COLREGs complaint path for an ASV to follow between a
starting and a goal location is a difficult task in dynamic environments
because of changes in the environment. The problem becomes even more complex
when dealing with large numbers and types of vessels in close vicinity where
each vessel follows COLREGs. Changes made in the course and/or speed of any
ASV might create a ripple effect that forces other ASVs to take appropriate
actions and may quickly lead to large changes in the state of environment. In
the past, a variety of approaches have been proposed that obey COLREGs, such
as rapidly random tree [1], velocity obstacles [2], fuzzy logic, model
predictive control (MPC) [3], artificial potential fields (APF) [4]. However,
these approaches do not scale well to large numbers of vessels and multiple
COLREGs rules. Additionally, some of these approaches, such as RTT, have a
high computational complexity.

In this paper, we present a technique, VORRT-COLREGs, that combines RRT and VO
to generate safe and COLREGs complaint paths for ASVs in different types of
collision scenarios. RRT samples a 2D location for an ASV to move to and VO
checks whether moving to the new location is safe and whether the actions of
the ASV will be in accordance with COLREGs. If the newly generated sample is
safe and COLREGs complaint then this location is added to a list of way points
otherwise the location is discarded. Note that due to changes in the
environmental state that includes vessels position, speed, and course, a
previously COLREGs complaint path may becomee invalidated and thus a new path
needs to be found. To avoid this, we employ joint forward simulation (JFS) to
compute the future locations of all vessels assuming that the speed and course
of vessels remains the same. When a path becomes invalid, we compute a new
path. JFS is a popular way of predicting the future locations of autonomous
agents and have been extensively used in robotics.

Earlier work [1] describes COLREGs complaint path generation using virtual
obstacles with RRT in the open ocean. We extend this work and use VORRT-
COLREGs to generates safe and COLREGs complaint paths for many different
collision situations including Traffic Separation Schemes (TSS). To the best
of our knowledge, this is the first work that combines RRT and VO to generate
path for ASVs in multiple different scenarios.

Experiments were conducted with different numbers of ASVs and under different
types of collision scenarios. We started with simple collision situations
between two ASVs: crossing, head-on, and overtaking. Results show that VORRT-
COLREGs generated safe and COLREGs complaint path under each of the three
scenarios. Next, we considered more than two vessels where multiple types of
collision occurs simultaneously and results show that our technique generated
compliant COLREGs paths. Lastly, we considered a TSS where multiple vessels
move within a narrow channel and an ASV crosses the channel. Results show that
VORRT-COLREGs generated paths that safely navigated the ASV from one side to
the other side of the channel.

The remainder of this paper is organized as follows. Section II outlines
related work in the area of autonomous surface vessels navigation. Section III
describes collision regulations. In Section IV we describe our proposed
COLREGs complaint path generation algorithm. Section V presents results and
discussion. Finally, the last section draws conclusions from our results and
discusses future work.

##  II Related Work

Reports indicate that more than $80$ percent of maritime collision accidents
are caused by human error [5]. Autonomous navigation of maritime surface
vessel may help to reduce collision accidents by efficient and collision free
route planning. Generating safe paths that are in compliance with collision
regulations is difficult because of the dynamic nature of the operating
environment. Vessels’ positions, courses, speeds, sizes, and other
geographical restrictions affect path planning. Any mistake made by any vessel
operator may quickly result in scenarios where collision between vessels is
inevitable. For example, a route planned for an ASV may cause other vessels to
alter their course or speed while following COLREG guidelines but they may not
have enough time or space to maneuver to avoid colliding with still other
vessels in a scenario.

We investigate collision free path planning navigation for ASVs in compliance
with collision regulations at sea. Prior work has used techniques based on RRT
[1], velocity obstacles [2], and model predictive control [3] to control the
movement of ASVs while avoiding obstacles and following COLREGs. However,
these approaches may not scale to heavy traffic environments such as those
found in Traffic Separation Schemes (TSS). To the best of our knowledge,
VORRT-COLREGs is the first approach to combine velocity obstacles with RRT to
quickly find a COLREGs complaint collision free path to a destination.

Researchers have used different techniques to generate COLREGs complaint
paths. In [4], artificial potential fields in combination with a line-of-sight
based algorithm was introduced. This does not incorporate the large mass and
inertia of vessels, hence vessels may fail to come to and follow a desired
course in time to avoid collision. In addition, there is no handling of
maintaining a safe minimum distance from other ships. Johansen [6] proposed
model predictive control and used used simulated predictions of trajectories
of obstacles and other vessels. Loe [7] used a dynamic window based method for
ASV navigation. However, in both approaches, other vessels in their test
scenarios are non COLREG complaint and have random or fixed velocities. We
address all these issues using our proposed technique.

Pranay [8] used A* under dynamic environment conditions to generate paths for
ASVs. An iterative A* heuristics was used to find a shortest path while
maintaining adequate distance from colliding vessels on $15$ different
environments where autonomous vehicle moves at speed of $16.8$ m/s and the
target location moves at $1.7$ m/s. In [9] Shah presented an Adaptive Risk and
Contingency-Aware Planner (ARCAP) to generate paths in a lattice. Shen [10]
used a Deep Q Network (DQN) for multi ship collision avoidance while following
rules of the road. Li [11] proposed rolling horizontal optimization approach
to minimize course alteration and time efficiency while maneuvering vessels.
Synchronous Branch and Bounce (SyncBB), Dynamic Programming Optimization
Protocol (DPOP), and Asynchronous Forward Bounding (AFB) was used for multi
ship avoidance in [12]. Kim [13] presented Dynamic Stochastic Search Algorithm
(DSSA) and Chen [14] introduced Alternative Direction Method of Multiplier
(ADMM) for ship control and the room-to-maneuver algorithm, which contains a
safe velocity space for multiple ships, was proposed by Degre [15].

Researchers have also formulated this problem as an optimization problem and
used different optimization techniques to optimize path. Liang in [16],
proposed a multi objective particle swarm optimization based on-line route
planning framework for ASVs that minimizes collision and ensure COLGREGs
compliance. The framework re-plans the route in dynamic environment and scales
with multiple target vessels. Shengke [17] use genetic algorithms to optimize
paths that avoid collisions at open sea. Jun [18] proposed a modified fuzzy
dynamic risk of collision model based on time and space collision risk index
to generate paths and used multi objective genetic algorithm to optimize paths
based on time, economy, COLREGs, and safety. Compared to the above approaches,
VORRT-COLREGs provides fast, safe, near-optimal, physically realizable paths
for ASVs.

##  III COLREGs

Collision regulation guidelines prescribe actions that different vessels must
perform when encountering a potential risk of collision. Figure 1, shows three
different scenarios with potential risk of collision. In this figure (a) is a
crossing scenario where $1$ is the give-way vessel and $2$ is the stand-on
vessel, (b) is an over-taking scenario where $1$ is the stand-on vessel and
$2$ is the give-way vessel, and (c) is a head-on scenario where both vessels
must give-way.

Figure 1: COLREGs guidelines for (a) crossing, (b) over-take, and (c) head-on.

###  III-A Risk of Collision

In this paper, when the distance between our vessel (ownship) and a target
vessel is less than a Minimum Threshold Distance (MTD), we check for potential
risk of collision. If the distance at the Closest point of Approach (CPA) is
below this MTD we assume that there is a potential risk of collision and use
VORRT-COLREGs to generate a path for ownship to follow.

###  III-B Rule-Based Encounter Type Classification

If there is a risk of collision and ownship is the give-way vessel, the
scenario or encounter type is classified according to collision regulation
rules. In this work we consider only rules $13$ to $17$ which dictate the
actions of power driven vessels to avoid collision. These rules define five
different types of collision situations: head-on, starboard crossing, port
crossing, overtaking, and being overtaken. In case of head-on and crossing
from starboard, the give way vessel must change course to starboard. When
being overtaken or when you are the stand on vessel in a crossing situation,
you should maintain speed and course. Finally, when overtaking, ownship can
overtake on the port or starboard sides of the target. Here are pertinent
rules from COLREGs that VORRT-COLREGs follows:

  * •

Overtaking (Rule 13(b)): A vessel is coming up with another vessel from a
direction more than 22.5 degrees abaft her beam.

  * •

Head-on (Rule 14(a)): Two power-driven vessels are meeting on reciprocal or
nearly reciprocal courses so as to involve risk of collision.

  * •

Crossing (Rule 15): Two power-driven vessels are crossing so as to involve
risk of collision.

  * •

Action by give-way vessel (Rule 16): Every vessel which is directed to keep
out of another vessel shall, so far as possible, take early and substantial
action to keep well clear.

  * •

Action by stand-on vessel (Rule 17(a)(i)): Where one of two vessels is to keep
out of the way the other shall keep her course and speed.

##  IV Methodology

We propose a hybrid of VO and RRT to generate COLREGs compliance paths for
ASVs. We start by describing velocity obstacles followed by RRT. Later, we
combine VO and RRT and describe VORRT-COLREGs to generate COLREGs complaint
paths for ASVs.

###  IV-A Velocity Obstacle

Velocity obstacles [19] was proposed in 2008 as a new concept for real-time
multi agent navigation. Let $A$ and $B$ be two vessels positioned at $P_{a}$
and $P_{b}$ and moving in the direction of their arrows with velocities of
$V_{a}$ and $V_{b}$ as shown in Figure 2. We assume that $A$ is an ASV and $B$
is a human controlled vessel. The velocity obstacle $VO_{b}^{a}(\vec{V_{b}})$
of vessel $B$ to the ASV is the set consisting of all those velocities $V_{a}$
for ASV that will result in a collision at some moment in time with vessel $B$
moving at velocity $V_{b}$. Figure 2 shows the velocity obstacle
$VO_{b}^{a}(\vec{V_{b}})$ of a disc-shaped vessel $B$ to a disc-shaped ASV.
For simplicity we consider disc-shaped vessels where the radius of the
enclosing disc is the length of the vessel. In order to avoid collision, two
vessels’ representative discs must not touch each other at any given time. Let
$A\oplus B$ denote the Minkowski sum of vessels $A$ and $B$ and let$-A$ denote
the vessel $A$ reflected in its reference point.

$A\oplus B=\\{a+b|a\in A,b\in B\\},-A=\\{-a|a\in A\\}$

$\lambda(\vec{P},\vec{V})$ denotes a ray staring at $P$ and heading in the
direction of $V$ as shown in equation 1. If the ray starts at $P_{a}$, heading
in the direction of the relative velocity of $A$ and $B$ and intersects the
Minkowski sum of $B$ and $-A$ centered at $P_{b}$, then the velocity $V_{a}$
is in the velocity obstacle of $B$. Equation 2 calculates velocity obstacle
$VO_{b}^{a}(\vec{V_{b}})$ of vessel $B$ to the ASV $A$.

Figure 2: Velocity obstacle cone of A and B.

Figure 2 shows a cone that represents $VO_{b}^{a}(\vec{V_{b}})$ and the
relative velocity ($V_{a}-V_{b}$) lies inside this cone. This means that if
the ASV keeps its heading and speed (velocity), there will be a future
collision. As per rule $15$, this is a crossing scenario where the ASV
(ownship) is the give way vessel and the other vessel is the stand on vessel.
Rule $15$ also says that if the circumstances of the case admit, avoid
crossing ahead of the other vessel. Thus, the ASV needs to change its course
to starboard to avoid collision in accordance with the nautical rules of the
road. Furthermore, in the open ocean, vessels may try to keep miles away from
each other. The minimum distance between two moving vessels is the distance at
closest point of approach (CPA). Equation 3 computes time to CPA and equation
4 computes the distance at CPA between the ASV and other vessels.

$\lambda(\vec{P},\vec{V})=\\{\vec{P}+t\vec{V}|t\geq 0\\}$ (1)

$VO_{b}^{a}(\vec{V_{b}})=\vec{V_{a}}|\lambda(\vec{P_{a}},\vec{V_{a}}-\vec{V_{b}})$
(2)
$t_{cpa}=\begin{cases}\frac{(\vec{P_{a}}-\vec{P_{b}}).(\vec{V_{a}}-\vec{V_{b}})}{\lVert(\vec{V_{a}}-\vec{V_{b}})\rVert^{2}}&\text{if
$\lVert(\vec{V_{a}}-\vec{V_{b}})\rVert>0$}\\\ 0&\text{otherwise}\end{cases}$
(3)
$d_{cpa}=\lVert(\vec{P_{a}}+t_{cpa}*\vec{V_{a}})-(\vec{P_{b}}+t_{cpa}*\vec{V_{b}})\rVert$
(4)

We thus want the ASV to change course to not only avoid collision but to keep
at-least a minimum distance from the other vessel as well. In Figure 2 VO
provides a safe region for the ASV, rule $15$ prescribes turning to starboard,
and the minimum CPA distance constraint further restricts part of the safe
region on the starboard side provided by VO. We describe the RRT algorithm and
how we utilize this information and constraints during the RRT tree growth
phase.

###  IV-B Rapidly Exploring Random Tree (RRT)

RRT [20] was introduced by LaValle in $1998$ as a path planning algorithm. In
$2018$, Chiang [1] introduced COLREG-RRT that generated paths for ASV in
various collision situations and with different numbers of vessels and our
work is closely related to this paper. COLREG-RRT generates different virtual
obstacles in different types of collision scenarios and grows RRT trees while
avoiding virtual obstacles. However, COLREG-RRT does not guarantee that
generated paths will always follow rules of the road, does not explicitly
handle overtaking situations, and there is no minimum distance constraint to
ensure that vessels do not come dangerously close to each other.

1

Input : $\mathcal{S}=(s_{a},s_{1},s_{2},...,s_{m})$

Output : $\mathcal{P}$

2 $\mathcal{N}$ = [];

3 RootNode = Initialize RRT$(s_{a},s_{1},s_{2},...,s_{m})$;

4 $\mathcal{N}.append(RootNode,0)$;

5 $\mathcal{N}$, Goal = VORRTTree($\mathcal{N}$, Goal=1, itr, $\mathcal{S}$);

6 if  _!Goal_ then

7 $\mathcal{N}$, Goal = VORRTTree($\mathcal{N}$, Goal=0, itr, $\mathcal{S}$);

8

9 end if

10$\mathcal{P}$ = getPath($\mathcal{N}$);

11 return($\mathcal{P}$);

Algorithm 1 VORRT-COLREG

###  IV-C VORRT-COLREGs

We present a hybrid of VO and RRT that generates safe paths in compliance with
COLREGs. VORRT-COLREGs works in all types of collision situations and is given
by algorithm 1. The algorithm takes the environmental states,
$\mathcal{S}=(s_{a},s_{1},s_{2},...,s_{m})$ and returns a path, $\mathcal{P}$,
for ASVs to follow. Here $s_{a}$ refers to the current state of an ASV that
includes ASV’s position, heading, and speed. $s_{1},...,s_{m}$ refer to the
states of other vessels. The algorithm begins with an empty list of node
$\mathcal{N}$. RRT initializes a root node where the node contains state
information of all vessels with timestamp. Since RRT generates new nodes
randomly, it may take a longer time to find a path between the current
location of the ASV and its goal location. Thus, we introduce a bias by
setting a parameter to generating new nodes in the direction of the goal
location from ASV’s current location. VORRTTree in algorithm 1 grows the tree
and takes four parameters; $\mathcal{N}$, moving towards goal (true/false),
maximum number of iterations, and the environmental state. VORRTTree grows the
tree for $200$ steps and if it can reach the goal location with $200$ steps,
extracts and returns the path from the list of nodes ($\mathcal{N}$). If the
goal was not reached then the tree grows for another $200$ steps without bias
towards goal but following the nautical rules of the road. At the end of this
second $200$ steps, if the goal was reached, the algorithm extract and returns
the path from the list of nodes. If goal was not reached then we run VORRT-
COLREGs again or conclude that no safe path exists.

1

Input : $\mathcal{N}$, Goal, itr, $\mathcal{S}$

Output : $\mathcal{N}$, Goal

2

3while  _i $\leq$ itr_ do

4 if  _$Goal$_ then

5 $pos=getGoal()$;

6 else

7 $pos=randomSampling()$;

8 end if

9 $node_{selected}=getClosestNode(\mathcal{N},pos)$;

10 $pos_{new},\mathcal{S^{\prime}}=JFS(node_{selected},pos)$;

11 inCollision = $VOCollision$($pos_{new}$, $\mathcal{S^{\prime}}$);

12 if  _inCollision_ then

13 $/*Discard*/$;

14

15 else

16 $node_{new}=getNode(pos_{new},\mathcal{S^{\prime}})$;

17 $\mathcal{N}.append(node_{new},node_{selected})$;

18 i++;

19

20 end if

21

22 end while

23Goal = reachedGoal($node_{new}$)

return $\mathcal{N}$, Goal

Algorithm 2 VORRTTree Growth

The VORRTTree growth algorithm is given by Algorithm 2. The algorithm works in
a similar fashion to vanilla RRT and the only difference is that when a
position/location is sampled in two dimensional space, we use a joint forward
simulation to compute future states of our ASV and other vessels. The JFS
takes the closest node ($node_{selected}$) from this sampled position and
computes future states of each vessel. Remember each node contains each
vessel’s state information (position, speed, and heading) at a given time and
thus an ASV with position, speed, and heading identified by $node_{selected}$
moves in the direction of the RRT sampled position for a distance of
$d^{\prime}$ meters. In this paper, $d^{\prime}=100$ meters as this works well
for our vessel speeds and sizes. Other vessels move in the direction of their
respective goal locations with constant speed and heading. After travelling
$d^{\prime}$ distance each vessel reaches different locations (state,
$\mathcal{S^{\prime}}$) and we check whether our ASV is at a safe (non VO-
colliding) location using velocity obstacles. If the new ASV location is not
safe then we discard this new location and RRT sample a new point/location.

Velocity obstacle based collision checking is shown by Algorithm 3. The
algorithm iterates over each vessel
($\mathcal{S^{\prime}}={s_{a},s_{1},..,s_{m}}$) and computes CPA distance
between the ASV and other vessels. It also computes whether ASV position
($pos_{new}$) lies in the velocity cone between the ASV and other vessels. If
$pos_{new}$ lies inside velocity cone or CPA distance is less than a threshold
distance ($d_{th}$) then either there is a risk of collision or collision has
occurred. Moving to $pos_{new}$ is not safe and must be discarded.

1

Input : $pos_{new}$, $n_{selected}$, $\mathcal{S^{\prime}}$

Output : collision

2 collision = false

3 $\vec{P_{a}}=s_{a}.pos$

4 $\vec{V_{a}}=s_{a}.vel$

5 for  _s in $\mathcal{S^{\prime}}$_ do

6 $\vec{P_{v}}=s.pos$

7 $\vec{V_{v}}=s.vel$

8 $d_{CPA}=findCPADistance(\vec{P_{a}},\vec{P_{v}},\vec{V_{a}},\vec{V_{v}}$)

9 if  _$pos_{new}$ in
$\vec{V_{a}}|\lambda(\vec{P_{a}},\vec{V_{a}}-\vec{V_{v}}$) $||d_{th}\leq
d_{CPA}$ _ then

10 if  _$\vec{P_{a}}==\vec{P_{v}}$_ then

11 Do nothing (vessel is the ASV)

12

13 else

14 collision = true

15

16 end if

17

18 end if

19

20 end for

21return collision;

Algorithm 3 Velocity Obstacle Collision Checking

###  IV-D Joint Forward Simulator (JFS)

In order to generate safe and COLREGs complaint path, we use a joint forward
simulator to check whether each node generated during VORRT tree growth is
safe. Each node in the VORRT tree keeps position, speed, and heading of each
vessel. Using these information JFS computes the potential for collision
between the ASV and other vessels for each newly generated node in the VORRT
tree. If for the given node, a collision is detected then that node will be
not be added to the VORRT tree. Otherwise the node will be added in the tree
and JFS will compute the position, speed, and heading for each vessel for the
last added node in the tree. JFS repeats these computations at each time step.
It should be noted that modern ocean-going ships are required to be equipped
with an automatic identification system which broadcasts the current course,
speed and destination [21]. Therefore, we assume this information is available
to the JFS. In this preliminary work we only consider rules $13$ to $17$ in
[22]. We are specifically interested in situations where ownship is the give
way vessel.

Figure 3:  Crossing situation where the ASV is the give way and target vessel
is a stand on vessel. The red line show the path generated by VORRT-COLREGs
algorithm that avoids collision while following rules.

(a) Overtaking

(b) Head-on

Figure 4: Distance between the ASV and the target vessel at different time
steps. (a) ASV is overtaking the target vessel, (b) when both vessels are
head-on.

(a) Four Vessels

(b) Locations of vessels Vessels

(c) CPA Distances

Figure 5: Multi vessel collision situation. (a) starting location of four
vessels moving in the direction of arrow, (b) shows patg travelled by vessels,
and (c) Distance between the ASV and three target vessels at different time
steps.

(a) A complete path crossing TSS

(b) TSS entrance, $d_{min}=135$ meters

(c) Inside TSS, $d_{min}=350$ meters

(d) Leaving TSS, $d_{min}=319$ meters

Figure 6: VORRT-COLREGs generated a safe path for ownship to cross a TSS.
Traffic in the TSS is moving from right to left where TSS is one nautical mile
in width. In figures (b), (c), and (d) $d_{min}$ is cpa distance and brown
boxes are the closest points of approach.

##  V Results and Discussion

We conducted experiments with single vessel and multiple vessels under
different collision scenarios.

###  V-A Single Vessel Collision

We conducted experiments on three baseline test collision scenarios with two
vessel. Figure 3 shows two vessels; ownship (OV)/ASV that is controlled by
VORRT-COLREGs and a target vessel in a crossing situation. In this scenario as
per rules, ownship is the give way vessel, the target vessel is the stand on
vessel, and ownship must turn to starboard to avoid collision. In the figure,
black boxes represent starting locations of vessels, brown boxes represent the
location of vessels at an intermediate time step, and green boxes represent
goal locations of vessels. The figure shows that ownship plots and follows a
smooth, physically realizable, COLREGs compliant, collision avoiding path to
the goal.

Figure 4(a) shows the distance between the ASV and the target vessel at
different time steps in the simulation, where the ASV is overtaking the target
vessel. The minimum distance, that is, distance at closest point of approach
between the two vessels is $1365$ meters as shown by the black line.
Similarly, Figure 4(b) shows distance between the ASV and the target vessel
when both vessels are head-on to each other at different time steps. Here, the
CPA distance was found to be $470$ meters. For the experiments, we set minimum
CPA distance threshold to $200$ meters. This minimum CPA distance threshold is
a parameter to VORRT-COLREGs and can be easily changed to reflect a Captain’s
preference or to reflect the scenarios. For example, the minimum CPA distance
threshold may need to be set much lower inside a traffic separation scheme
where even large vessels may routinely come within several hundred yards of
each other.

###  V-B Multi Vessel Collision

These results on the above simple test scenarios indicate that VORRT-COLREGs
generates viable paths for collision scenarios with two vessels. To increase
the complexity of the problem we considered a scenario where there is
potential risk of collision with multiple vessels. Figure 5(a) shows the
starting location of an ASV and three target vessels moving in the direction
of the arrows. The ASV controlled by VORRT-COLREGs is the give way vessel in
both a crossing situation and a head-on situation. VORRT-COLREGs generated a
path for the ASV that resulted in safe navigation and the minimum CPA distance
is $300$ meters with the target vessel two ($TS2$) and greater for the other
vessels.

###  V-C Traffic Separation Scheme

We also conducted experiments in scenarios where an ASV/ownship crosses a
traffic separation scheme as shown in Figure 6. We created a one nautical mile
wide channel where normal traffic is moving from right to left and an ASV aims
to cross the channel while following nautical rules of the road. Figure 6(a)
shows a complete path generated by VORRT-COLREGs. Zooming in at different time
steps we observe the positions of the ASV, other vessels in the TSS and
distance between vessels.

Figure 6(b), (c), and (d) show locations of vessels zoomed in at different
time steps. The minimum CPA distance between ASV and all target vessels is
$135$ meters. Since, the width is small and vessels do not have a large space
to maneuver, we reduced the safe distance between vessels from $200$ to $100$
meters. Note that the COLREG-RRT algorithm in [1] would have been unable to
generate viable paths for an ASV to cross this TSS because of the continuous
traffic movement in the channel. To generate COLREGs complaint paths, COLREG-
RRT assumes a virtual obstacle where one end of the obstacle is in front of
colliding vessel and the other end is far away in the direction of vessel
movement. Since traffic is always moving in the TSS, this results in the
creation of virtual objects placed in the channel at all times. This does not
allow COLREG-RRT to successfully generate paths in a TSS.

We have shown that VORRT-COLREGs generates collision avoiding paths in
accordance with COLREGs for baseline two-vessel and heavy traffic TSS
scenarios. We believe that this provides preliminary evidence for the
potential of our approach for safe autonomous ship driving in accordance with
the nautical rules of the road.

##  VI Conclusions

In this paper, we presented VORRT-COLREGs to generate safe and COLREGs
complaint paths for ASVs. We combine rapidly epxloring random trees and
velocity obstacles to generate paths where RRT generate samples in the space
and velocity obstacle check whether moving in the direction of the newly
generated sample is safe and in accordance with COLREGs. Experiments on
different scenarios, with different numbers of vessels have shown that our
technique successfully generated viable safe paths. Results on baseline two
vessel and multiple vessel scenarios show the effectiveness of our technique.
We also conducted experiments in a traffic separation scheme with $15$\+
vessels and show that VORRT-COLREGs generates safe paths. To the best of
authors knowledge this is the first work that combines VO and RRT to generate
COLREGs complaint paths for ASVs.

In this future, we plan to extend this work by creating an automated scenario
generator and testing the algorithm on hundreds of generated scenarios with
differing numbers and densities of vessels in the open ocean and in traffic
separation schemes. This will enable scaling of the approach and
characterization of the limits of the approach.

## Acknowledgments

This work was supported by grant number N00014-17- 1-2558 from the Office of
Naval Research. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and do not necessarily
reflect the views of the Office of Naval Research. This work was also
supported in part by the U.S. Department of Transportation, Office of the
Assistant Secretary for Research and Technology (USDOT/OST-R) under Grant No.
69A3551747126 through INSPIRE University Transportation Center
(http://inspire-utc.mst.edu) at Missouri University of Science and Technology.
The views, opinions, findings and conclusions reflected in this publication
are solely those of the authors and do not represent the official policy or
position of the USDOT/OST-R, or any State or other entity.

## References

  * [1] H. L. Chiang and L. Tapia.  Colreg-rrt: An rrt-based colregs-compliant motion planner for surface vehicle navigation.  IEEE Robotics and Automation Letters, 3(3):2024–2031, 2018.
  * [2] Yoshiaki Kuwata, Michael T Wolf, Dimitri Zarzhitsky, and Terrance L Huntsberger.  Safe maritime autonomous navigation with colregs, using velocity obstacles.  IEEE Journal of Oceanic Engineering, 39(1):110–119, 2013.
  * [3] Tor Arne Johansen, Tristan Perez, and Andrea Cristofaro.  Ship collision avoidance and colregs compliance using simulation-based control behavior selection with predictive hazard assessment.  IEEE transactions on intelligent transportation systems, 17(12):3407–3422, 2016.
  * [4] Y Xue, BS Lee, and D Han.  Automatic collision avoidance of ships.  Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment, 223(1):33–46, 2009.
  * [5] Y. Xue, B. Lee, and D. Han.  Automatic collision avoidance of ships.  Journal of Engineering for the Maritime Environment, 223:33–46, 2009.
  * [6] Tor Arne Johansen, Tristan Perez, and Andrea Cristofaro.  Ship collision avoidance and colregs compliance using simulation-based control behavior selection with predictive hazard assessment.  IEEE transactions on intelligent transportation systems, 17(12):3407–3422, 2016.
  * [7] Øivind Aleksander G Loe.  Collision avoidance for unmanned surface vehicles.  Master’s thesis, Institutt for teknisk kybernetikk, 2008.
  * [8] Pranay Agrawal and John M Dolan.  Colregs-compliant target following for an unmanned surface vehicle in dynamic environments.  In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1065–1070. IEEE, 2015.
  * [9] Brual C Shah, Petr Švec, Ivan R Bertaska, Armando J Sinisterra, Wilhelm Klinger, Karl von Ellenrieder, Manhar Dhanak, and Satyandra K Gupta.  Resolution-adaptive risk-aware trajectory planning for surface vehicles operating in congested civilian traffic.  Autonomous Robots, 40(7):1139–1163, 2016.
  * [10] Haiqing Shen, Hirotada Hashimoto, Akihiko Matsuda, Yuuki Taniguchi, Daisuke Terada, and Chen Guo.  Automatic collision avoidance of multiple ships based on deep q-learning.  Applied Ocean Research, 86:268–288, 2019.
  * [11] Shijie Li, Jialun Liu, Rudy R Negenborn, and Feng Ma.  Optimizing the joint collision avoidance operations of multiple ships from an overall perspective.  Ocean Engineering, 191:106511, 2019.
  * [12] Shijie Li, Jialun Liu, and Rudy R Negenborn.  Distributed coordination for collision avoidance of multiple ships considering ship maneuverability.  Ocean Engineering, 181:212–226, 2019.
  * [13] Donggyun Kim, Katsutoshi Hirayama, and Tenda Okimoto.  Distributed stochastic search algorithm for multi-ship encounter situations.  The Journal of Navigation, 70(4):699–718, 2017.
  * [14] Linying Chen, Hans Hopman, and Rudy R Negenborn.  Distributed model predictive control for vessel train formations of cooperative multi-vessel systems.  Transportation Research Part C: Emerging Technologies, 92:101–118, 2018.
  * [15] T Degre and X Lefevre.  A collision avoidance system.  The Journal of Navigation, 34(2):294–302, 1981.
  * [16] Liang Hu, Wasif Naeem, Eshan Rajabally, Graham Watson, Terry Mills, Zakirul Bhuiyan, and Ivor Salter.  Colregs-compliant path planning for autonomous surface vehicles: A multiobjective optimization approach.  IFAC-PapersOnLine, 50(1):13662–13667, 2017.
  * [17] Shengke Ni, Zhengjiang Liu, Yao Cai, and Xin Wang.  Modelling of ship’s trajectory planning in collision situations by hybrid genetic algorithm.  Polish Maritime Research, 2018.
  * [18] Jun Ning, Hanmin Chen, Tieshan Li, Wei Li, and Chunze Li.  Colregs-compliant unmanned surface vehicles collision avoidance based on multi-objective genetic algorithm.  IEEE Access, 8:190367–190377, 2020.
  * [19] Jur Van den Berg, Ming Lin, and Dinesh Manocha.  Reciprocal velocity obstacles for real-time multi-agent navigation.  In 2008 IEEE International Conference on Robotics and Automation, pages 1928–1935. IEEE, 2008.
  * [20] Steven M LaValle.  Rapidly-exploring random trees: A new tool for path planning.  1998\.
  * [21] S Campbell, Wasif Naeem, and George W Irwin.  A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres.  Annual Reviews in Control, 36(2):267–283, 2012.
  * [22] US Coast Guard et al.  Navigation Rules.  Eigal Meirovich, 2012.


# On the growth rate inequality for self-maps of the sphere

Héctor Barge  E.T.S. Ingenieros Informáticos, Universidad Politécnica de
Madrid, 28660 Madrid, España<EMAIL_ADDRESS>and  Luis Hernández-Corbato
Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid, 28040
Madrid, España<EMAIL_ADDRESS>
###### Abstract.

Let $S^{m}=\\{x_{0}^{2}+x_{1}^{2}+\cdots+x_{m}^{2}=1\\}$ and
$P=\\{x_{0}=x_{1}=0\\}\cap S^{m}$. Suppose that $f$ is a self–map of $S^{m}$
such that $f^{-1}(P)=P$ and $|\mathrm{deg}(f_{|P})|<|\mathrm{deg}(f)|$. Then,
the number of fixed points of $f^{n}$ grows at least exponentially with base
$|d|>1$, where $d=\mathrm{deg}(f)/\mathrm{deg}(f_{|P})\in\mathbb{Z}$.

###### Key words and phrases:

Growth rate inequality, periodic point, topological degree

###### 2020 Mathematics Subject Classification:

Primary 37C25, 37E99; Secondary 55M20

The authors are partially supported by the Spanish Ministerio de Ciencia e
Innovación (grants PGC2018-098321-B-I00 and PID2021-126124NB-I00)

##  1\. Introduction

In [13], Shub raised the question on whether algebraic intersections numbers
bound assymptotically from below geometrical intersection numbers for $C^{1}$
maps. For a self-map $f\colon M\to M$ on a manifold, a particular case of the
previous question comes down to whether the number $\\#\mathrm{Fix}(f^{n})$ of
points fixed by $f^{n}$ and the Lefschetz numbers $L(f^{n})$ satisfy

$\limsup\frac{1}{n}\log(\\#\mathrm{Fix}(f^{n}))\geq\limsup\frac{1}{n}\log\,|L(f^{n})|$

This inequality is known as the _growth rate inequality_ and bounds from below
the base of the exponential growth rate of periodic points. If the sequence of
Lefschetz numbers $L(f^{n})$ is unbounded, Lefschetz-Dold theorem together
with a result of Shub and Sullivan [15] (that states that the index sequence
of a fixed point for a $C^{1}$ map is bounded) imply that there are infinitely
many periodic points. The growth rate inequality appeared again as an open
problem in the Proceedings of the ICM 2006 [14]. It is wide open in dimensions
greater than 1.

The Lefschetz number of a self-map on a sphere can be computed from the
topological degree as $L(f)=1\pm\mathrm{deg}(f)$, so the growth rate
inequality for self-maps of the sphere can be rewritten in terms of the degree
as follows:

(1)
$\limsup_{n\to+\infty}\frac{1}{n}\log(\\#\mathrm{Fix}(f^{n}))\geq\log\,|\mathrm{deg}(f)|$

Shub’s original paper [13] proved (1) for rational maps on $S^{2}$. However,
even for a $C^{1}$ map of degree 2 on $S^{2}$, it is not known whether the
growth rate inequality holds. Note that the $C^{1}$ assumption is crucial, a
degree-2 north-south map on $S^{2}$ has only 2 fixed points and no other
periodic point.

Recently, the growth rate inequality has been proved in several instances for
maps on the sphere. In dimension 2, the sharp bound of
$\log\,|\mathrm{deg}(f)|$ was obtained when $f$ preserves some singular
foliations [12, 10, 4] or under hypothesis of dynamical nature [5, 7, 6, 8].
In higher dimensions the results are scarce. Weaker bounds for the growth rate
of periodic points when the map preserves some foliation and some mild
hypotheses is satisfied were obtained in [2, 3].

In this article we prove a weak form of the growth rate inequality for maps on
$S^{m}=\\{x_{0}^{2}+x_{1}^{2}+\cdots+x_{m}^{2}=1\\}\subset\mathbb{R}^{m+1}$.
Suppose $f\colon S^{m}\to S^{m}$ leaves the codimension–2 sphere
$P=\\{x_{0}=x_{1}=0\\}$ completely invariant, that is, $f^{-1}(P)=P$. Then,
the degree of $f$ is equal to the product of two factors: the degree of the
restriction of $f$ to $P$ and a “transversal” degree denoted $d\in\mathbb{Z}$.
The latter can be interpreted in terms of the action induced by $f$ on the
homology group or the fundamental group of $S^{m}-P$.

######  Theorem 1.

Let $f\colon S^{m}\to S^{m}$ be a map such that $f^{-1}(P)=P$ and
$\mathrm{deg}(f)\neq 0$ and let $d=\mathrm{deg}(f)/\mathrm{deg}(f_{|P})$.
Then, $\\#\mathrm{Fix}(f^{n})+\\#\mathrm{Fix}(f^{n}_{|P})\geq|d^{n}-1|$. In
particular,

$\liminf_{n\to+\infty}\frac{1}{n}\log(\\#\mathrm{Fix}(f^{n}))\geq\log|d|$

In dimension $m=2$, $P$ is a 0–sphere and $\mathrm{deg}(f_{|P})$ can only take
the values $-1,0,1$. We deduce the following corollary from Theorem 1, that
was previously stated in [6].

######  Corollary 2.

Suppose $f\colon S^{2}\to S^{2}$ and there are two points $\\{p,p^{\prime}\\}$
such that $f^{-1}(\\{p,p^{\prime}\\})=\\{p,p^{\prime}\\}$. Then,

$\liminf_{n\to+\infty}\frac{1}{n}\log(\\#\mathrm{Fix}(f^{n}))\geq\log\,|\mathrm{deg}(f)|$

In higher dimensions we obtain a weak bound for the growth rate:

######  Corollary 3.

Under the hypothesis of Theorem 1, if $m=3$ or, more generally, if the growth
rate inequality holds in $S^{m-2}$ then

$\liminf_{n\to+\infty}\frac{1}{n}\\#\mathrm{Fix}(f^{n})\geq\frac{1}{2}\log\,|\mathrm{deg}(f)|$

The result follows from the first inequality in Theorem 1 and the fact that
$\mathrm{max}\\{|d|,|\mathrm{deg}(f_{|P})|\\}\geq\sqrt{|\mathrm{deg}(f)|}$.

Theorem 1 is deduced from Theorem 5, which is stated in the ensuing section.
The proof is contained in the last section of the article. It requires a
detailed local analysis of the map in the normal direction to $P$, presented
in Section 4, and uses an argument from topological degree theory, which is
quickly reviewed in Section 3.

##  2\. Setting

Let $S=S^{m}=\\{(x_{0},\ldots,x_{m}):x_{0}^{2}+\cdots+x_{m}^{2}=1\\}$ be the
standard $m$–sphere in $\mathbb{R}^{m+1}$ and $P=\\{x_{0}=x_{1}=0\\}\cap S$ be
an $m-2$–dimensional sphere which we will refer to as the _polar sphere_. The
complement $S-P$ is diffeomorphic to $S^{1}\times D^{m-1}$, where $D^{m-1}$
denotes the $(m-1)$–dimensional open unit disk, via the map

(2)
$(x_{0},\ldots,x_{m})\longmapsto\left(\displaystyle\frac{(x_{0},x_{1})}{||(x_{0},x_{1})||},(x_{2},\ldots,x_{m})\right)$

On the other hand, $P^{\prime}=\\{x_{2}=\cdots=x_{m}=0\\}\cap S$ is a
$1$–sphere such that $S$ is the join of $P$ and $P^{\prime}$. The set
$S-P^{\prime}$ is diffeomorphic to $D^{2}\times S^{m-2}$ by

(3)
$(x_{0},\ldots,x_{m})\longmapsto\left((x_{0},x_{1}),\displaystyle\frac{(x_{2},\ldots,x_{m})}{||(x_{2},\ldots,x_{m})||}\right)$

Equations (2) and (3) define coordinate charts for $S-P$ and $S-P^{\prime}$,
respectively. If we replace $(x_{2},\ldots,x_{m})$ by
$(0,0,x_{2},\ldots,x_{m})$ in (3), we obtain a diffeomorphism between
$S-P^{\prime}$ and $D^{2}\times P$. This description will be used extensively
throughout this note, as it provides a product structure for the system of
neighborhoods of $P$ defined by the inequalities $x_{0}^{2}+x_{1}^{2}<r$ for
$0<r<1$: they are diffeomorphic to $D^{2}(r)\times P$.

Similarly, the inequalities $x_{0}^{2}+x_{1}^{2}>1-r^{\prime}$,
$0<r^{\prime}<1$, define neighborhoods of $P^{\prime}$ in $S-P$ diffeomorphic
by (2) to $S^{1}\times D^{m-1}(r^{\prime})$. Note that the radial coordinates
of $D^{2}$ and $D^{m-1}$ are related by $r+r^{\prime}=1$. For any $0<r<1$,

(4) $S\enskip\cong\enskip D^{2}(r)\times P\enskip\sqcup\enskip
S^{1}\times\overline{D}^{m-1}(1-r)$

Evidently, the fundamental group of $S-P$ is isomorphic to $\mathbb{Z}$. Using
the coordinates from (3), for any $r\in(0,1)$ and $p\in P$, it is easy to see
that $\pi_{1}(S-P)$ is generated by a loop $\gamma$ that makes a positive turn
around the origin in the 2-disk $D^{2}(r)\times\\{p\\}$. Let us consider the
lift of $S-P$ that trivializes $[\gamma]$,
$\mathrm{pr}\colon\widetilde{S-P}\to S-P$.

In our results, $f$ is a self–map of $S$ for which $P$ is completely
invariant, $f^{-1}(P)=P$. Since $S-P$ is invariant under $f$, $f$ can be
lifted to $\widetilde{S-P}$. Let $\tau$ be a generator of the group of deck
transformations of the cover. Any lift $F$ of $f$ satisfies

(5) $F\,\tau=\tau^{d}\,F$

where $d\in\mathbb{Z}$ is the _transversal degree_ defined by
$f_{*}[\gamma]=d\cdot[\gamma]$ in $\pi_{1}(S-P)$ (see (12) later). As we will
prove in Subsection 3.1, $\mathrm{deg}(f)=d\cdot\mathrm{deg}(f_{|P})$.

A fixed point of $F$ projects onto a fixed point of $f$ in $S-P$. The
following lemma is a consequence of (5) and establishes a relation between
fixed points of different lifts. It is standard in Nielsen theory (cf. [9,
Lemma 4.1.10]).

######  Lemma 4.

If two different lifts $F,G=\tau^{m}F$ of $f$ satisfy
$\mathrm{pr}(\mathrm{Fix}(F))\cap\mathrm{pr}(\mathrm{Fix}(G))\neq\emptyset$,
then $d\neq 1$ and $|d-1|$ divides $m$.

By the previous lemma, we can bound from below
$\\#\\{\mathrm{Fix}(f)\cap(S-P)\\}$ by the number of lifts of $f$ among
$\\{F,\tau F,\ldots,\tau^{|d-1|-1}F\\}$ that have fixed points.

######  Theorem 5.

Suppose that $d\neq 0,1$. There are at most $2\,\\#\mathrm{Fix}(f_{|P})$ fixed
point free maps among $\\{F,\tau F,\ldots,\tau^{|d-1|-1}F\\}$.

Theorem 5 and Lemma 4 immediately imply that

$\\#\\{\mathrm{Fix}(f)\cap(S-P)\\}\geq|d-1|-2\,\\#\\{\mathrm{Fix}(f_{|P})\\}$

Replace $f$ by $f^{n}$ in this inequality to deduce Theorem 1. Note that the
transversal degree associated to $f^{n}$ is $d^{n}$.

##  3\. Topological degree

The topological degree of a map $g\colon M\to L$ between closed connected and
oriented manifolds of dimension $n\geq 1$ roughly counts with multiplicity the
number of preimages of a point. For a complete account on degree theory we
refer to [11]. We give below a precise definition of the degree in algebraic
topological terms. Recall that the orientation of a closed connected manifold
$M$ is given by a fundamental class $[M]$, i.e. a generator of the reduced
homology group $\widetilde{H}_{n}(M)$. Reduced and unreduced homology groups
only differ at dimension 0, the reason to choose here the reduced groups shall
become clear later. The image $[M]_{x}$ of the fundamental class $[M]$ under
the projection $\widetilde{H}_{n}(M)\to H_{n}(M,M-\\{x\\})$ is the local
orientation at $x\in M$, and it is a generator of $H_{n}(M,M-\\{x\\})$.

######  Definition 6.

Let $g\colon M\to L$ be a map between $n$–dimensional closed orientable
manifolds such that
$\widetilde{H}_{n}(M)\cong\widetilde{H}_{n}(L)\cong\mathbb{Z}$ and $[M],[L]$
be fundamental classes of $M,L$, respectively. The degree of $g$, denoted
$\mathrm{deg}(g)$, is the integer that satisfies

(6) $g_{*}([M])=\mathrm{deg}(g)\cdot[L],$

The reason to choose the hypothesis $\widetilde{H}_{n}(M)\cong\mathbb{Z}$ in
the definition is that it is satisfied by closed connected oriented manifolds
of dimension $n\geq 1$ (spaces that appear in the standard definition of
topological degree) and also by 0–spheres (such as the polar sphere in
$S^{2}$, that is relevant in this paper). Incidentally, note that the degree
of a map between 0–spheres can only take the values $-1,0,1$.

By duality, the degree can be alternatively defined using reduced cohomology
groups. If $\omega_{M},\omega_{L}$ are generators of the reduced $n$-th
cohomology group of $M,L$, we have that
$g^{*}(\omega_{L})=\mathrm{deg}(g)\,\omega_{M}$.

###  3.1. Decomposition of the degree

Suppose now that $f\colon M\to M$ is a self-map and $N$ is a completely
invariant submanifold (i.e. $f^{-1}(N)=N$). Under some topological hypothesis,
the degree of $f$ is equal to the product of two factors: the degree of the
restriction of $f$ to $N$ and an integer $d$ that accounts for the winding
around $N$ in the transversal direction, which we call _transversal_ degree.

(7) $\mathrm{deg}(f)=d\cdot\mathrm{deg}(f_{|N})$

######  Lemma 7.

Let $M$ be a closed connected and orientable $n$-dimensional manifold and
$f:M\rightarrow M$ a continuous map with $\mathrm{deg}(f)\neq 0$. Suppose that
$N\subset M$ is a closed orientable submanifold of codimension $k\geq 2$ that
is completely invariant, i.e. $f^{-1}(N)=N$, and
$\widetilde{H}^{n-k}(N)\cong\mathbb{Z}$. Then $\mathrm{deg}(f_{|N})$ divides
$\mathrm{deg}(f)$. Moreover, if $H_{k}(M)\cong 0$ or if $k=n$ there is a non
trivial class $\beta\in H_{k-1}(M-N)$ such that $f_{*}(\beta)=d\cdot\beta$,
where $d=\mathrm{deg}(f)\,/\,\mathrm{deg}(f_{|N})$.

###### Proof.

Observe that, since $N$ is completely invariant, the map $f$ can be considered
as a map of pairs $f:(M,M-N)\rightarrow(M,M-N)$. Let $[M]\in H_{n}(M)$ a
fundamental class in $M$. The homomorphism

(8) $\frown[M]:H^{n-k}(N)\rightarrow H_{k}(M,M-N)$

consisting in capping each (unreduced) cohomology class in $H^{n-k}(N)$ with
the fundamental class $[M]$ is an isomorphism (see [1, Theorem 8.3, pg. 351]).

Let $\omega$ be a generator of the reduced cohomology group
$\widetilde{H}^{n-k}(N)$ (note that $\omega$ also generates $H^{n-k}(N)$
unless $k=n$). Then, by naturality of the cap product [1, Theorem 5.2, pg.
336] it follows

(9) $f_{*}(f_{|N}^{*}(\omega)\frown[M])=\omega\frown f_{*}([M]).$

If we examine the left-hand side of (9) we get

(10)
$f_{*}(f_{|N}^{*}(\omega)\frown[M])=f_{*}((\mathrm{deg}(f_{|N})\cdot\omega)\frown[M])=\mathrm{deg}(f_{|N})\cdot
f_{*}(\omega\frown[M]).$

On the other hand,

(11) $\omega\frown
f_{*}([M])=\omega\frown(\mathrm{deg}(f)\cdot[M])=\mathrm{deg}(f)\cdot(\omega\frown[M]).$

Hence, from (9), (10) and (11) it follows that
$\mathrm{deg}(f_{|N})\mid\mathrm{deg}(f)$ and the quotient is an integer $d$
that satisfies $f_{*}(\omega\frown[M])=d\cdot(\omega\frown[M])$ in
$H_{k}(M,M-N)$.

The second statement follows immediately from the naturality of the long exact
sequence of homology of $(M,M-N)$ in the case $H_{k}(M)$ is trivial. We can
take $\beta$ to be the image of $\omega\frown[M]$ by the boundary morphism
$H_{k}(M,M-N)\to H_{k-1}(M-N)$. In fact, by exactness the existence of $\beta$
is guaranteed as long as $\omega\frown[M]$ does not belong to the image of
$p\colon H_{k}(M)\to H_{k}(M,M-N)$. In the case $k=n$, $N=\\{x,y\\}$ is a
0–sphere, $H_{k}(M)$ is generated by the fundamental class $[M]$ and
$p([M])=[M]_{x}+[M]_{y}$. Then, the preimage of $p([M])$ under the duality
isomorphism (8) is the (unreduced) 0–cohomology class represented by the
constant map on $N$ equal to 1 and, in particular, is different from $\omega$.
Then, $\omega\frown[M]\notin\mathrm{im}(p)$ and the result follows.

∎

Heuristically, the transversal degree $d$ counts how many times the image of
the boundary of a small neighborhood of $N$ wraps around $N$. The
interpretation is much clearer in the case $M=S=S^{m}$ and $N=P$, the polar
sphere of codimension $k=2$. Note that $H_{2}(S)$ is trivial for all $m>2$ and
if $m=2=k$, $P$ is a 0–sphere and the lemma still applies. From (2) we get
that $H_{1}(S-P)\cong\mathbb{Z}$ and we deduce that

$(f_{|S-P})_{*}\colon H_{1}(S-P)\to H_{1}(S-P)$

is conjugate to the multiplication by $d$ in $\mathbb{Z}$. Evidently, the same
description applies to the action induced in the fundamental group of $S-P$ as
well: if $\gamma$ is a loop that generates $\pi_{1}(S-P)$ then

(12) $f_{*}[\gamma]=d\cdot[\gamma].$

###  3.2. Vector fields and fixed points

The final step in the proof of Theorem 5 uses an argument from topological
degree theory. In order to keep the article self-contained, we formulate and
prove the elementary results which are needed.

Let $U$ be an open subset of $\mathbb{R}^{m}$ and $B\subset U$ be
diffeomorphic to $\overline{D}^{m}$. Any non-singular vector field $v$ on
$\partial B$ defines a map $j\colon\partial B\to S^{m-1}$ by
$j_{v}(x)=v(x)/||v(x)||$.

######  Lemma 8.

  * (i)

If $v$ points inwards $B$ then $j_{v}$ is not nulhomotopic (i.e., not
homotopic to the constant map).

  * (ii)

If $v,w$ never point to the same direction (that is, $j_{v}(x)\neq j_{w}(x)$
for all $x$) and $j_{v}$ is not nulhomotopic then $j_{w}$ is not nulhomotopic.

Further, suppose that $\partial B$ is decomposed as the union of two
hemispheres $E_{+},E_{-}$, that is $(E_{+},E_{-})$ is diffeomorphic to
$(H_{+},H_{-})$, where $H_{+}$ and $H_{-}$ denote the uppper and lower
hemisphere of $S^{m-1}$.

  * (iii)

If $v$ points inwards on $E_{+}\cap E_{-}$, $j_{v}(E_{+})\subset H_{+}$ and
$j_{v}(E_{-})\subset H_{-}$ then $j_{v}$ is not nulhomotopic.

###### Proof.

(i) Clearly, $j_{v}$ is conjugate to a self-map of $S^{m-1}$ that is homotopic
to the antipodal map. The conclusion follows from the fact that the antipodal
map on $S^{m-1}$ is not nulhomotopic (otherwise, we could construct an
homotopy from the identity map to a constant map by composing with the
antipodal map).

(ii) $j_{w}$ is homotopic to $j_{-v}$. We can now use an argument as in (i) to
conclude.

(iii) If $\sigma$ is the reflection through the equator on $S^{m-1}$,
$\sigma\circ j_{v}$ is conjugate to the antipodal map. Again, we conclude that
it is not nulhomotopic. ∎

Given a map $h\colon U\to\mathbb{R}^{m}$, we define a vector field
$v_{h}(x)=h(x)-x$. Singularities of $v_{h}$ correspond to fixed points of $h$,
so when we work with $j_{v_{h}}$ we tacitly assume $h$ has no fixed points on
the boundary of $B$. One of the central ideas of topological degree theory is
that it is possible to detect fixed points of $h$ inside $B$ just by studying
$v_{h}$ on $\partial B$ or, more precisely, the homotopy class of $j_{v_{h}}$.
Indeed, if $\mathrm{Fix}(h)\cap B=\emptyset$ then $v_{h}$ has no singularities
in $B$ and, using a foliation of $B$ by spheres that converge to an interior
point, it is possible to construct an homotopy from $j_{v_{h}}$ to a constant
map. In other words,

######  Lemma 9.

If $j_{v_{h}}$ is not nulhomotopic, there exists a fixed point of $h$ in $B$.

Let us point out that one of the first results in topological degree theory is
that the reverse implication is true up to homotopy. If $j_{v_{h}}$ is
nulhomotopic, it is possible to construct an homotopy between $h$ and
$h^{\prime}$ relative to $\partial B$ such that $h^{\prime}$ has no fixed
points in $B$.

##  4\. Local analysis at fixed points in $P$

Recall the setting from Section 2. $P$ has a basis of neighborhoods
diffeomorphic by (3) to $D^{2}(r)\times S^{m-2}$. The map $f$ induces, by
projection onto the first factor, a dynamics in the 2-dimensional normal
direction around $P$. We obtain a family of $C^{1}$ maps $f_{p}\colon
D^{2}(s)\to D^{2}$, $p\in P$, for some fixed small $s>0$.

The smoothness of $f$ poses a restriction on the behavior of $f_{p}$ for a
fixed point $p\in P$ because of the following reason: a $C^{1}$ map is
injective in a neighborhood of a repelling fixed point. This fact follows from
the inverse function theorem and the fact that the repelling condition implies
that the eigenvalues of the jacobian matrix at the fixed point lie outside the
unit disk and, in particular, away from zero. We shall prove later that if any
$f_{p}$ is injective then the transversal degree satisfies $|d|\leq 1$ and
Theorem 1 becomes trivial. Accordingly, we focus on the case $|d|>1$ in which
$f_{p}$ is not injective for any $p\in P$ and, in particular, the Jacobian
matrix $A_{p}$ of $f_{p}$ at the origin in the 2–dimensional normal direction
is singular. Therefore, there are only two dynamically different cases stated
in terms of the spectral radius of $A_{p}$, either it is smaller than 1 and
the origin is an attractor for $f_{p}$ or it is greater or equal than 1 and
there is an attracting cone region.

We proceed now to study the dynamics of planar maps such as $f_{p}$. Later, we
apply the local picture to describe the behavior of $f$ in the normal
direction to $P$.

###  4.1. Planar results

Suppose $g\in\mathbb{R}^{2}\to\mathbb{R}^{2}$ is a $C^{1}$ map that fixes the
origin, $g(0)=0$. Denote by $A$ the Jacobian matrix of $g$ at $0$. By the
definition of differentiability at the origin, for every $\epsilon>0$ there
exists $\delta>0$ such that

(13) $\displaystyle\frac{||g(u)-Au||}{||u||}<\epsilon,\quad\quad\text{for
all}\enskip u\enskip\text{such that}\enskip 0<||u||<\delta$

where we have used the identification $T_{0}\mathbb{R}^{2}\cong\mathbb{R}^{2}$
and $||\cdot||$ is a norm in $\mathbb{R}^{2}$. Recall that all the norms in a
finite dimensional vector space are equivalent. The spectral radius of $A$,
$\rho(A)$, largely determines the behavior of $g$ in a neighborhood of $0$.

######  Lemma 10.

For every $c>\rho(A)$ there exists a norm $||\cdot||$ in $\mathbb{R}^{2}$ such
that

$||Au||<c\,||u||$ for every $u\in\mathbb{R}^{2}-\\{0\\}$.

###### Proof.

If $A$ is diagonalizable over $\mathbb{R}$, we can take the $\ell^{1}$–norm
associated to a basis $\mathcal{B}$ composed of eigenvectors, that is,
$||u||=||(u_{1},u_{2})_{\mathcal{B}}||:=|u_{1}|+|u_{2}|$. If the eigenvalues
of $A$ are not real, the $\ell^{2}$–norm associated to an orthogonal basis
satisfies the conclusion. Finally, if the eigenvalues of $A$ are equal but $A$
is not diagonalizable, let $e_{0}$ be an eigenvector and $e_{1}\neq 0$ not
collinear to $e_{0}$. Then, we can take the $\ell^{1}$–norm associated to the
basis $\\{Ke_{0},e_{1}\\}$ for large enough $K>0$. ∎

An immediate consequence of the previous lemma and (13) is that if $\rho(A)<1$
then the origin is a local attractor for $g$.

######  Corollary 11.

Suppose $\rho(A)<1$ and let $\epsilon\in(0,1-\rho(A))$, then there exists
$\delta>0$ and a norm in $\mathbb{R}^{2}$ such that
$||g(u)||<(1-\epsilon)||u||$ whenever $0<||u||<\delta$.

In the case there is an eigenvalue $\lambda$ with $|\lambda|\geq 1$, we can
locate the region where the inequality $||g(u)||<||u||$ does not hold.

######  Lemma 12.

Suppose the eigenvalues of $A$ are $\\{0,\lambda\\}$ with $|\lambda|\geq 1$.
Denote $\mathcal{B}=\\{e_{0},e_{\lambda}\\}$ a basis composed of eigenvectors,
$||\cdot||$ the $\ell^{1}$–norm associated to $\mathcal{B}$ and

$C(\alpha)=\\{u=(u_{0},u_{\lambda})_{\mathcal{B}}\in\mathbb{R}^{2}-\\{0\\}:|u_{0}/u_{\lambda}|<\alpha\\}.$

For every $\epsilon\in(0,1/2)$ there exists $\delta>0$ such that if
$0<||u||<\delta$ and

  * (i)

if $u\notin C\left(\frac{|\lambda|+2\epsilon-1}{1-2\epsilon}\right)$ then
$||g(u)||<(1-\epsilon)||u||$.

  * (ii)

if $u\in C\left(\frac{|\lambda|-3\epsilon}{3\epsilon}\right)$ then
$|(g(u))_{\lambda}|>\epsilon||u||$ and, in particular, $g(u)\notin\langle
e_{0}\rangle$. ($\langle v\rangle$ denotes the subspace spanned by $v$)

###### Proof.

Apply (13) to $||\cdot||$ and $\epsilon$. For (i), if
$u=(u_{0},u_{\lambda})_{\mathcal{B}}$ with $||u||<\delta$

$(1-\epsilon)||u||=(1-\epsilon)|u_{0}|+(1-\epsilon)|u_{\lambda}|\geq\epsilon|u_{0}|+(|\lambda|+\epsilon)|u_{\lambda}|=||Au||+\epsilon||u||>||g(u)||$

To deduce (ii) we use that $||g(u)||+\epsilon||u||\geq||Au||$:

$|(g(u))_{\lambda}|=||g(u)||-|(g(u))_{0}|\geq|\lambda||u_{\lambda}|-2\epsilon||u||=(|\lambda|-2\epsilon)|u_{\lambda}|-2\epsilon|u_{0}|>\epsilon||u||>0.$

∎

###  4.2. Analysis in the normal direction

Since $f(P)=P$, $f$ restricts to a continuous map

$f\colon D^{2}(s)\times P\longrightarrow D^{2}\times P$

for some $s>0$, where we extensively use the coordinates introduced in (3).
The Jacobian matrix of $f$ in a point $p\in P$ has the following form:

$Jf_{p}=\begin{pmatrix}A_{p}&0\\\ \ast&(Jf_{|P})_{p}\\\ \end{pmatrix}$

where the basis for the tangent space at $p$ is ordered according to the local
product structure around $P$: first the (2-dimensional) normal space to $P$
and then the ($(m-2)$–dimensional) tangent space to $P$. Alternatively,
$A_{p}$ can be defined as the Jacobian at $0$ of the following composition

(14) $\displaystyle f_{p}\colon D^{2}(s)\to
D^{2}(s)\times\\{p\\}\hookrightarrow D^{2}(s)\times
P\xrightarrow{\phantom{a}f\phantom{a}}D^{2}\times
P\xrightarrow{\mathrm{proj}}D^{2}$

######  Lemma 13.

If $|d|>1$ then $A_{p}$ is singular for every $p\in P$.

###### Proof.

Suppose that $A_{p}$ is regular. Then, $f_{p}$ restricts to a diffeomorphism
between $D^{2}(r)$ and $V=f_{p}(D^{2}(r))$, for small $r>0$. In particular, if
$\gamma$ is a generator of $\pi_{1}(D^{2}(r)-\\{0\\})$, then $f_{p}(\gamma)$
is a generator of $\pi_{1}(V-\\{0\\})$. Think of $\gamma$ as a loop in
$(D^{2}(r)-\\{0\\})\times\\{p\\}$ and choose it small so that
$f(\gamma)\subset D^{2}\times U_{f(p)}$, where $U_{f(p)}$ is contractible in
$P$. It follows that both $\gamma$ and $f(\gamma)$ generate $\pi_{1}(S-P)$
and, by (12), we deduce that $d=\pm 1$, a contradiction. ∎

Therefore, either Corollary 11 or Lemma 12 apply to $f_{p}$ when $|d|>1$. For
a given $p\in P$, we extend the results by continuity to $f_{q}$ for $q$ close
to $p$.

######  Proposition 14.

Suppose that $|d|>1$. For every $p\in P$, there exists a neighborhood
$D^{2}(\delta)\times U_{p}$ of $p$ in $S$ and a norm $||\cdot||$ in
$\mathbb{R}^{2}$ such that:

  * (i)

If $\rho(A_{p})<1$, for all $q\in U_{p}$ and all $u\in D^{2}(\delta)$,

$||f_{q}(u)||\leq||u||$.

  * (ii)

Otherwise, there is a basis $\\{e_{0},e_{1}\\}$ of $\mathbb{R}^{2}$ and
$\alpha\in\mathbb{R}^{+}$ such that for every $q\in U_{p}$

    * –

if $u\notin C(\alpha)$ and $u\in D^{2}(\delta)$ then $||f_{q}(u)||\leq||u||$.

    * –

$f_{q}(C(\alpha)\cap D^{2}(\delta))\cap\langle e_{0}\rangle=\emptyset$.

###### Proof.

Let $||\cdot||$ be the norm from Corollary 11 or Lemma 12 depending on which
alternative, (i) or (ii), applies.

For (i), apply Corollary 11 to any $\epsilon\in(0,1-\rho(A))$ to obtain
$||\cdot||$ and $\delta$ such that $||f_{p}(u)||\leq(1-\epsilon)||u||$ holds
whenever $||u||<\delta$. In order to extend the conclusion to $f_{q}$, for $q$
close to $p$, we use the smoothness of $f$.

Since $f_{q}(u)=\left(\int_{0}^{1}Df_{q}|_{tu}\,dt\right)u$, we have that

(15)
$||f_{q}(u)-f_{p}(u)||\leq\left(\int_{0}^{1}||Df_{q}|_{tu}-Df_{p}|_{tu}||\,dt\right)||u||<\gamma_{q}||u||$

where $\gamma_{q}=\mathrm{max}_{v\in
D^{2}(\delta)}||Df_{q}|_{v}-Df_{p}|_{v}||$. Since $f$ is $C^{1}$,
$\gamma_{q}\to 0$ as $q\to p$. Let $U_{p}$ be a neighborhood of $p$ in $P$
such that $|\gamma_{q}|<\epsilon$ for all $q\in U_{p}$. Then we conclude that
$||f_{q}(u)||\leq||u||$ for all $q\in U_{p}$ and $||u||<\delta$.

For (ii), denote $\lambda$ be the non–zero eigenvalue of $A_{p}$. Firstly,
take $\epsilon>0$ small enough so that

$\frac{|\lambda|+2\epsilon-1}{1-2\epsilon}<\frac{|\lambda|-3\epsilon}{3\epsilon}$

and set $\alpha=\frac{|\lambda|+2\epsilon-1}{1-2\epsilon}$. Apply Lemma 12 to
obtain $||\cdot||$, $\delta$ and $\\{e_{0},e_{1}\\}$. The conclusions for
$q=p$ follow immediately from the lemma. To extend the results to a
neighborhood $U_{p}$ of $p$ we use (15) and proceed exactly as in (i). The
argument above can be used verbatim to prove the first item. For the second
item, $|(f_{q}(u))_{\lambda}|\geq|(f_{p}(u))_{\lambda}|-\epsilon||u||>0$.
Finally, note that the norm from Lemma 12 may not be the $\ell^{2}$-norm so we
might need to shrink $\delta$ to $\delta^{\prime}$ so that the standard 2-disk
$D^{2}(\delta^{\prime})$ fits inside the disk defined by $||u||<\delta$. ∎

Below, in the proof of Theorem 5, only the fixed points $p$ of $P$ for which
the second alternative in Proposition 14 applies require special attention.
The local description obtained above provides a cone $C(\alpha)$ above each
$q$ close to $p$ that contains the repelling sector (if any) and whose image
misses the attracting direction spanned by $e_{0}$.

##  5\. Proof of Theorem 5

Recall (see (2)) that $S-P$ is diffeomorphic to $S^{1}\times D^{m-1}$.
Consider the cover

(16) $\widetilde{S-P}\cong\mathbb{R}\times D^{m-1}\longrightarrow S^{1}\times
D^{m-1}\cong S-P$

defined as the standard cover $\mathbb{R}\to S^{1}$, $t\mapsto e^{2\pi it}$ in
the first factor and as the identity in the second factor.

Our aim is to prove that except for a few cases, every lift of $f$ to
$\widetilde{S-P}$ has a fixed point in $B_{M}=[-M,M]\times D^{m-1}(1-\delta)$
for large $M$ and small $\delta>0$. The argument is based on topological
degree theory. The key observation is that, for most of the lifts $F$, the
vector field $v_{F}(x)=F(x)-x$ in $\mathbb{R}\times D^{m-1}$ never points to
the same direction as the coordinate vector field $\partial/\partial r(x)$,
whose definition will be recalled next, on the boundary of $\mathbb{R}\times
D^{m-1}(1-\delta)$. Then, we can apply Lemmas 8 and 9 to conclude that $F$ has
a fixed point inside $B_{M}$ for large $M>0$.

From (3), we deduce that $S-P-P^{\prime}$ is diffeomorphic to $D^{2}_{0}\times
P$, where the subscript in $D_{0}^{2}$ indicates that the disk is punctured at
the origin. The lift of $S-P-P^{\prime}$ to the cover (16) is therefore
diffeomorphic to $\mathbb{R}\times(0,1)\times P$, where the second factor,
$(0,1)$, corresponds to the radial coordinate $r$ of $D^{2}_{0}$ and also to
$1-r^{\prime}$, where $r^{\prime}$ is the radial coordinate of $D^{m-1}$ in
(16) (cf. the discussion before (4)). The coordinate $r$ and, more precisely,
the vector field $\partial/\partial r$ that it defines in the cover play a
central role in the discussion. On the lateral face of the cylinder $B_{M}$,
$\partial/\partial r$ points inwards. Note that, alternatively, if we use the
coordinates from (2) instead of those of (3), we see that the lift of
$S-P-P^{\prime}$ is diffeomorphic to $\mathbb{R}\times D^{m-1}_{0}$.

The lift of the partition (4) of $S-P$ for $r=\delta$ still displays a product
structure:

$\widetilde{S-P}=\mathbb{R}\times(0,\delta)\times P\sqcup\mathbb{R}\times
D^{m-1}(1-\delta)$

The factor $\mathbb{R}$ corresponds to the angular coordinate in the normal
bundle of $P$ in the first term and to the lift of $S^{1}$ (that parametrizes
$P^{\prime}$) in the second instance. The projection onto the first factor
$\mathrm{pr}\colon\widetilde{S-P}\to\mathbb{R}$ conjugates a generator $\tau$
of the group of deck transformations of the cover and the translation by 1 in
$\mathbb{R}$.

Recall from the statement of Theorem 5 that $d\neq 0,1$. For an arbitrary lift
$F$ of $f$, by (5) we have that $F\tau=\tau^{d}F$ so

$\mathrm{pr}(x)=\mathrm{pr}(y)+1\quad\Rightarrow\quad\mathrm{pr}(F(x))=\mathrm{pr}(F(y))+d$.

for all $x,y\in\widetilde{S-P}$. Therefore, for a fixed $\delta>0$, if $M$ is
sufficiently large and if $d>1$ then

(17) $\displaystyle\begin{split}\mathrm{pr}(F(x))&\leq-M-1\quad\text{for every
}x\in\\{-M\\}\times D^{m-1}(1-\delta)\text{ and}\\\ \mathrm{pr}(F(x))&\geq
M+1\quad\text{for every }x\in\\{M\\}\times D^{m-1}(1-\delta)\end{split}$

whereas if $d\leq-1$ then

(18) $\displaystyle\begin{split}\mathrm{pr}(F(x))&\geq-M+1\quad\text{for every
}x\in\\{-M\\}\times D^{m-1}(1-\delta)\text{ and}\\\ \mathrm{pr}(F(x))&\leq
M-1\quad\text{for every }x\in\\{M\\}\times D^{m-1}(1-\delta)\end{split}$

These inequalities imply that on the left and right faces (as in Figure 1) of
the solid cylinder $B_{M}$ the vector field $v_{F}$ points outwards when $d>1$
and inwards when $d\leq-1$.

Let us focus now on the lateral face of $B_{M}$ and suppose further that
$d\neq-1$. Let $p\in\mathrm{Fix}(f|_{P})$ and consider the neighborhood
$D^{2}(\delta)\times U_{p}$ of $p$ and the norm $||\cdot||$ from Proposition
14. Denote $V_{p}$ the lift of $D^{2}_{0}(\delta)\times U_{p}$ to the cover
(note that the disk is punctured) and suppose $v_{F}$ and $\partial/\partial
r$ point to the same direction at $x\in V_{p}$. This implies that the
projection of $x$ and $F(x)$ to $D^{2}\times P$, have the form $(u,q)$ and
$(au,q)$ for some $a>1$ and $q\in U_{p}$. In particular, $f_{q}(u)=au$, which
automatically implies $||f_{q}(u)||>||u||$. Thus, the second alternative of
Proposition 14 applies to $p$, so there exists a basis $\\{e_{0},e_{1}\\}$ and
$\alpha\in\mathbb{R}^{+}$ such that $u\in C(\alpha)\cap D^{2}(\delta)$ and
$f_{q}(C(\alpha)\cap D^{2}(\delta))\cap\langle e_{0}\rangle=\emptyset$ for
every $q\in U_{p}$. The last property can be stated equivalently as

(19) $f((C(\alpha)\cap D^{2}(\delta))\times U_{p})\cap(\langle
e_{0}\rangle\times U_{p})=\emptyset$

We now lift these elements to the cover. The cone region $C(\alpha)\times
U_{p}$ lifts to a sequence of domains $O_{n}=(I+\frac{n}{2})\times(0,1)\times
U_{p}$, indexed by $n\in\mathbb{Z}$, where we are now employing the
coordinates of $\mathbb{R}\times(0,1)\times P$, the lift of $D_{0}^{2}\times
P$, and $I$ is an interval in $\mathbb{R}$ of length $<1/2$. See Figure 1.
Similarly, the strip $\langle e_{0}\rangle\times U_{p}$ lifts to a sequence of
strips $E_{n}=\\{\widetilde{e}_{0}+\frac{n}{2}\\}\times(0,1)\times U_{p}$ for
some $\widetilde{e}_{0}\in\mathbb{R}$. Restricted to $V_{p}$, the strips
$E_{n}$ and the domains $O_{n}$ are pairwise disjoint and are placed
alternately. Evidently, $\tau(E_{n})=E_{n+2}$ and $\tau(O_{n})=O_{n+2}$.

Denote $O_{n}^{\delta}=O_{n}\cap(\mathbb{R}\times(0,\delta)\times U_{p})$, the
subset of $O_{n}$ defined by $0<r<\delta$. The condition (19) implies that
$F(O_{n}^{\delta})$ does not meet $E_{m}$ for any $m\in\mathbb{Z}$. This
imposes a serious restriction on the number of lifts for which the image of
$O_{n}^{\delta}$ intersects itself.

######  Lemma 15.

There are at most two elements $G$ of $\\{F,\tau F,\ldots,\tau^{|d-1|-1}F\\}$
such that

$G(O_{n}^{\delta})\cap O_{n}\neq\emptyset$ for some $n\in\mathbb{Z}$.

###### Proof.

Recall that for any lift $G$, $G(O_{n+2})=G\tau(O_{n})=\tau^{d}G(O_{n})$ so if
$G(O_{n}^{\delta})$ lies in between $E_{k}$ and $E_{k+1}$ then
$G(O_{n+2}^{\delta})$ lies in between $E_{k+2d}$ and $E_{k+2d+1}$. Suppose
that $G,G^{\prime}=\tau^{m}G$ are two lifts of $f$ such that
$G(O_{n}^{\delta})\cap O_{n}\neq\emptyset$ and
$G^{\prime}(O_{n+2s}^{\delta})\cap O_{n+2s}\neq\emptyset$ for some $s\neq 0$.
It follows that $n+2s=m+n+2sd$, so $|d-1|$ divides $m$.

In sum, there is at most one lift in $\\{F,\tau F,\ldots,\tau^{|d-1|-1}F\\}$
such that the intersection in the statement is non-empty for some even $n$ and
at most one lift such that the intersection is non-empty for some odd $n$. ∎

Figure 1.  Picture of a piece of $B_{M}$ for $d=2$. The darker pieces and
thicker segments in the horizontal strip are the intersection of the domains
$O_{n}$ and the strips $E_{n}$ with the lateral face of $B_{M}$, defined by
$r=\delta$. Arrows illustrate $v_{F}$ at $\tau^{-1}x,x,\tau x$.

Incidentally, note that the previous lemma trivially holds when $d=-1$. As a
consequence of the discussion above we deduce:

######  Lemma 16.

Let $p\in\mathrm{Fix}(f_{|P})$ and $d\neq 0,1$. There exists $\delta_{p}>0$,
$U_{p}$ neighborhood of $p$ in $P$ such that there are at most two lifts $G$
among $\\{F,\tau F,\ldots,\tau^{|d-1|-1}F\\}$ for which the vector field
$v_{G}(x)=G(x)-x$ points to the same direction as $\partial/\partial r$ at
some point of $V_{p}$.

In the second part of the proof, we show that the lifts for which $v_{G}$ and
$\partial/\partial r$ do not point to the same direction at $V_{p}$, for any
$p\in\mathrm{Fix}(f_{|P})$, always have a fixed point on $B_{M}$. In view of
the previous corollary this assertion concludes the proof.

We have already described what happens in a neighborhood $\cup U_{p}$ of the
set of fixed points in $P$. Since $f_{|P}$ has no fixed point on $P-\cup
U_{p}$, by continuity, there exists $\delta_{1}$ such that every point in
$D^{2}(\delta_{1})\times(P-\cup U_{p})$ is displaced tangentially to $P$ by
$f$, that is, if $f((v,q))=(f_{q}(v),q^{\prime})$ then $q\neq q^{\prime}$. As
a consequence, for any lift $G$ of $f$, $v_{G}$ and $\partial/\partial r$ do
not point to the same direction on
$\mathbb{R}\times(0,\delta_{1})\times(P-\cup U_{p})$.

Take $\delta>0$ smaller than all $\delta_{p}$ and $\delta_{1}$. The results
from the previous paragraph and Lemma 16 imply that there are at least
$|d-1|-2\\#\mathrm{Fix}(f_{|P})$ lifts among $\\{F,\tau
F,\ldots,\tau^{|d-1|-1}F\\}$ such that $v_{G}$ and $\partial/\partial r$ do
not point to the same direction on the region
$\\{r=\delta\\}=\mathbb{R}\times\\{\delta\\}\times P$. Say $G$ is one of them.

Take $M$ large enough so that (17) holds for $G$ and $\delta$. Smooth out a
small neighborhood of the edges of the cylinder $B_{M}$ to obtain a convex
domain $B^{\prime}_{M}$ diffeomorphic to a closed ball. We now define a vector
field $w$ on $\partial B^{\prime}_{M}$ to apply the results from Section 3.

Case $d>1$. Let $w$ be the normal unitary vector on $\partial B^{\prime}_{M}$
that point inwards. Note that $w$ coincides with $\partial/\partial r$ on the
lateral face of $B^{\prime}_{M}$. In the rest of $\partial B^{\prime}_{M}$ the
inequalities (17) hold provided the smoothing region is small enough. By the
choice of $G$ we conclude that $w$ never points to the same direction as
$v_{G}$.

Since $B^{\prime}_{M}$ is diffeomorphic to a ball and $w$ points inwards on
its boundary, we can apply Lemma 8 (i) and (ii) to deduce that $j_{v_{G}}$ is
not nulhomotopic. Then, Lemma 9 concludes that $G$ has a fixed point inside
$B^{\prime}_{M}$, as desired.

Case $d\leq-1$. Define $w$ as the unitary vector that points inwards on the
lateral face of $B^{\prime}_{M}$ and as the unitary vector that points
outwards on the pieces of $\partial B^{\prime}_{M}$ that are part of the left
and right faces of $B_{M}$. Complete the definition of $w$ on $\partial
B^{\prime}_{M}$ by an interpolation that guarantees that in the smoothing
region and close to the left face, $\\{-M\\}\times D^{m-1}(1-\delta)$, $w$
never points in the positive direction (increasing first coordinate), while
close to the right face, $\\{M\\}\times D^{m-1}(1-\delta)$, $w$ never points
in the negative direction (decreasing first coordinate). Again, by the choice
of $G$, $w$ and $v_{G}$ never point to the same direction and, by Lemma 8
(iii) and (ii) and Lemma 9 we conclude that $G$ has a fixed point in
$B^{\prime}_{M}$.

## References

  * [1] G.E. Bredon.  Topology and geometry, volume 139 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1993.
  * [2] G. Graff, M. Misiurewicz, and P. Nowak-Przygodzki.  Periodic points of latitudinal maps of the $m$-dimensional sphere.  Discrete Contin. Dyn. Syst., 36(11):6187–6199, 2016.
  * [3] G. Graff, M. Misiurewicz, and P. Nowak-Przygodzki.  Shub’s conjecture for smooth longitudinal maps of $S^{m}$.  J. Difference Equ. Appl., 24(7):1044–1054, 2018.
  * [4] G. Graff, M. Misiurewicz, and P. Nowak-Przygodzki.  Periodic points for sphere maps preserving monopole foliations.  Qual. Theory Dyn. Syst., 18(2):533–546, 2019.
  * [5] L. Hernández-Corbato and F. R. Ruiz del Portal.  Fixed point indices of planar continuous maps.  Discrete Contin. Dyn. Syst., 35(7):2979–2995, 2015.
  * [6] G. Honorato, J. Iglesias, A. Portela, A. Rovella, F. Valenzuela, and J. Xavier.  On the growth rate inequality for periodic points in the two sphere.  J. Difference Equ. Appl., 25(2):219–232, 2019.
  * [7] J. Iglesias, A. Portela, A. Rovella, and J. Xavier.  Dynamics of annulus maps III: periodic points and completeness.  Nonlinearity, 29(9):2641–2656, 2016.
  * [8] J. Iglesias, A. Portela, A. Rovella, and J. Xavier.  Sphere branched coverings and the growth rate inequality.  Nonlinearity, 33(9):4613–4626, 2020.
  * [9] J. Jezierski and W. Marzantowicz.  Homotopy methods in topological fixed and periodic points theory, volume 3 of Topological Fixed Point Theory and Its Applications.  Springer, Dordrecht, 2006.
  * [10] M. Misiurewicz.  Periodic points of latitudinal sphere maps.  J. Fixed Point Theory Appl., 16(1-2):149–158, 2014.
  * [11] E. Outerelo and J. M. Ruiz.  Mapping degree theory, volume 108 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI; Real Sociedad Matemática Española, Madrid, 2009.
  * [12] C. Pugh and M. Shub.  Periodic points on the 2-sphere.  Discrete Contin. Dyn. Syst., 34(3):1171–1182, 2014.
  * [13] M. Shub.  Alexander cocycles and dynamics.  In Dynamical systems, Vol. III—Warsaw, Astérisque, No. 51, pages 395–413. Soc. Math. France, Paris, 1978.
  * [14] M. Shub.  All, most, some differentiable dynamical systems.  In International Congress of Mathematicians. Vol. III, pages 99–120. Eur. Math. Soc., Zürich, 2006.
  * [15] M. Shub and D. Sullivan.  A remark on the Lefschetz fixed point formula for differentiable maps.  Topology, 13:189–191, 1974.