# Systematic Evaluation of Applying Space-Filling Curves to Automotive
Maneuver Detection

Christian Berger1, Beatriz Cabrero-Daniel1, M. Cagri Kaya2, Maryam Esmaeili
Darestani1, Hannah Shiels1
1University of Gothenburg and 2Chalmers University of Technology
Gothenburg, Sweden
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Identifying driving maneuvers plays an essential role on-board vehicles to
monitor driving and driver states, as well as off-board to train and evaluate
machine learning algorithms for automated driving for example. Maneuvers can
be characterized by vehicle kinematics or data from its surroundings including
other traffic participants. Extracting relevant maneuvers therefore requires
analyzing time-series of (i) structured, multi-dimensional kinematic data, and
(ii) unstructured, large data samples for video, radar, or LiDAR sensors.
However, such data analysis requires scalable and computationally efficient
approaches, especially for non-annotated data. In this paper, we are
presenting a maneuver detection approach based on two variants of space-
filling curves (Z-order and Hilbert) to detect maneuvers when passing
roundabouts that do not use GPS data. We systematically evaluate their
respective performance by including permutations of selections of kinematic
signals at varying frequencies and compare them with two alternative
baselines: All manually identified roundabouts, and roundabouts that are
marked by geofences. We find that encoding just longitudinal and lateral
accelerations sampled at 10 Hz using a Hilbert space-filling curve is already
successfully identifying roundabout maneuvers, which allows to avoid the use
of potentially sensitive signals such as GPS locations to comply with data
protection and privacy regulations like GDPR.

###### Index Terms:

space-filling curve, manoeuvre detection, Z-order curve, Hilbert curve, Morton
codes, roundabout

##  I Introduction

The development and evaluation of Advanced Driver Assistance Systems (ADAS)
and Automated Driving Systems (ADS) is a data-driven process that covers
systematic and reproducible validation & verification (V&V) using closed-loop
simulations, controlled experimentation at confined test sites using
prototypical vehicles, and field data collections with larger vehicle fleets
for open-loop replay or scenario reconstruction. While virtual environments
provide systematic and cost-effective annotations by design, the degree of
fidelity in tests using real sensors in real scenarios is still higher, as
subtle effects that may not be part of the models used for the virtual sensors
or the environment model can be captured. In addition, a much broader variety
of situations can be potentially recorded that would require too much effort
to be modeled manually in virtual test environments.

Large-scale field data collections apparently have a greater value during the
system development and for V&V because of the representativeness of the
captured scenarios and because of the data originates from the real sensor
configuration. Furthermore, such field data can grow quickly by equipping
hundreds of vehicles with data loggers that stream their data to a centralized
storage, where it can be analyzed further. While the data collection itself
can be conducted rather cost-effectively, the actual data processing
afterwards to make use of the value of such data is becoming a growing
challenge: Firstly, field data is usually non-annotated right after collection
and relevant labels need to be added and verified (semi-)automatically before
queries for maneuvers are possible; secondly, data privacy and protection
regulations such as General Data Protection Regulation (GDPR) may not only
require the anonymization of video data (for instance, blurring faces or
license plates) but also potentially the removal of signal types such as GPS
locations of the vehicle that collected the data to prevent the identification
of individuals later.

The removal of certain signal types, though, may render the implementation and
use of some maneuver detection and querying approaches infeasible. For
instance, finding maneuvers when a vehicle is passing through a roundabout by
defining geofences and checking when a vehicle is entering such geofences of
interest would require potentially GDPR-sensitive information. Alternatively,
adding labels for entering/leaving roundabouts at the time of collecting data
would require the existence of a taxonomy of scenarios to label upfront, and
added elements in such a taxonomy would then only be applicable to newly
collected data but not to existing data from the past.

Motivation: There is a need for an approach to detect maneuvers and events
that (a) does not require the definition and maintenance of an annotation
taxonomy before data is collected, (b) does not depend on (semi-)automatically
added labels, and (c) is scalable to cope with growing amounts of data.

Berger and Birkemeyer (cf. [1]) introduced using a Z-order Space-Filling Curve
(SFC) as a novel approach to explore automotive data in a computationally
efficient way for event detection. In this paper, we are conducting a
qualitative experiment with two different types of SFCs, namely Z-order and
Hilbert curves, to answer the following research questions:

RQ-1: To what extent can Z-order and Hilbert SFC be exploited to identify
automotive maneuvers in an efficient way without relying on GDPR-sensitive
data? RQ-2: How do different experiment configurations (e.g., used signals,
sampling frequency, etc.) compare to manual annotations of automotive
maneuvers?

We limit our systematic experiment on the detection of driving through
roundabouts with a passenger vehicle (Volvo XC90). While the parametrization
is adjusted for the experimental vehicle, the fundamental concept is
transferable to other vehicles and scenarios. However, the best-performing
combination of kinematic signals, though, may be affected by the chosen
automotive maneuver in our experiments and may differ for other maneuvers
and/or geographic regions with different lane layouts.

The remainder of the paper is structured as follows: In Sec. II, we introduce
the ideas behind SFCs and describe related works. We describe the methodology
for our study in Sec. III and present the results in Sec. IV. We discuss and
analyze our results in Sec. V and conclude our work in Sec. VI.

##  II Related Work

One fundamental issue with event detection based on kinematic signals
originates from their multi-dimensionality, which is posing a computational
challenge at scale. Brute-force-based approaches like the one suggested by
Perez et al. [2] are on the one hand traceable and allow to understand
contributing factors for a positive hit, but they scale proportionally with a
data set’s size on the other hand and hence, are not practical for large data
sets.

Alternative approaches that explicitly address multi-dimensionality are based
on SFCs. An SFC enables a single-dimensional representation of multi-
dimensional data (cf. Bader, [3]) and hence, effectively allows for
dimensionality reduction. Intuitively, an SFC passes through each data point
from a multi-dimensional space in a recursive or repetitive manner. Certain
types of SFCs even preserve locality properties, ie., data points that are
close to each other in the multi-dimensional data space will be located near
to each after being mapped onto an SFC. This property in turn can be exploited
for efficient data retrieval as operations on an SFC are usually faster and
computationally cheaper on single dimensions than on multiple dimensions
simultaneously. SFCs have been explored by Hulbert et al. [4] for example who
evaluated the performance of SFCs on large data. Similarly, Dai et al. [5]
compared both, Z-order and Hilbert curves applied to two-dimensional data, and
Moon et al. [6] investigated the Hilbert SFC for indexing multi-dimensional
data that can be used for data queries.

There are also complementary studies that employ SFCs for event detection
across diverse application fields. For instance, Safia et al. [7] propose an
algorithm to detect environmental events like air pollution that can be used
for monitoring by sensor networks. Liu et al. [8] suggest a method called HGST
that uses Hilbert curves to improve the efficiency of spatiotemporal range
queries. The method was tested on a real taxi trajectory data set. Nair et al.
[9] present their study on dynamic planning of evasive maneuvers in an
environment, which represents obstacles and holes by using Hilbert curves.

(a) Traversing a two dimensional space using a Z-order curve; for the
technical implementation, multi-dimensional values are encoded into so called
Morton codes (cf. Morton, [10]).

(b) Traversing a two dimensional space using a Hilbert curve.

Figure 1: Illustrations for recursive construction of Z-order (a) and Hilbert
(b) curves to traverse a two dimensional space

(a) OpenStreetMap overlay of the trip used for experiments.

Locations of roundabouts:

| latitude | longitude
---|---|---
RA1 | $57.70974$ | $11.91848$
RA2 | $57.70207$ | $11.91152$
RA3 | $57.70655$ | $11.92202$
RA4 | $57.70998$ | $11.92721$
RA5 | $57.71007$ | $11.93112$
RA6 | $57.70771$ | $11.93477$
RA7 | $57.71113$ | $11.94337$

(b) Locations of the roundabouts.

Figure 2: Overview of the trip in an inner-city area in Gothenburg, Sweden.
The length of the trip is about $14\text{\,}\mathrm{k}\mathrm{m}$ and took ca.
$56\text{\,}\mathrm{m}\mathrm{i}\mathrm{n}$. During the trip, 7 different
roundabouts (denoted as $\text{RA}x$) were visited and some thereof even
multiple times.

We introduced the novel pattern detection approach named Z-order Curve-based
Event Retrieval Approach (ZEBRA) based on Z-order curves that we exploited for
computationally efficient event detection in the automotive context (cf.
Berger and Birkemeyer, [1]). We leveraged a Z-order SFC to reduce multi-
dimensional data into their corresponding single-dimensional representations
(vertical stripes) resulting in Characteristic Stripe Patterns (CSPs) as shown
in Fig. 3(b). We showed that the temporal occurrence, distribution, and spread
of such stripes correlate with certain maneuvers in the multi-dimensional
space. The locality preservation property of SFCs in combination with
operating just on a single dimension allowed us to design computationally
efficient operations to detect maneuvers. We showed in [1] that maneuver
detection can be conducted orders of magnitude faster in comparison to
directly processing time-series data in the original data space. The key idea
behind this performance gain is motivated by the fact that the application
context restricts the value range of the underlying SFC, on which operations
like inserting or looking up entries can be realized efficiently as a
consequence.

In this study, we are using two types of SFCs, namely Z-order and Hilbert
curves: A Z-order curve is exhibiting a Z-like pattern when repetitively
traversing a multi-dimensional space as shown in Fig. 1(a); we chose the
Z-order curve as the mapping from the multi-dimensional space to the single-
dimensional representation can be computed efficiently. A Hilbert curve is a
recursive traversal through a multi-dimensional data space and its pattern is
depicted in Fig. 1(b); we selected the Hilbert curve as it exhibits even
better locality preservation (cf. Bader, [3]) for data points that are in
close proximity to each other.

##  III Methodology

signal | $5\text{\,}\mathrm{Hz}$ | $10\text{\,}\mathrm{Hz}$ | $20\text{\,}\mathrm{Hz}$ | $50\text{\,}\mathrm{Hz}$ | $100\text{\,}\mathrm{Hz}$
---|---|---|---|---|---
GPS position | - | - | $\bullet$ | - | -
heading, $\sigma,[\text{rad}]$ | $\bullet$ | $\bullet$ | $\bullet$ | - | -
$v,[m/s]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
steering wheel angle, $\delta_{S},[\text{rad}]$ | $\bullet$ | $\bullet$ | - | $\bullet$ | -
lateral acceleration, $a_{x},[m/s^{2}]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
longitudinal acceleration, $a_{y},[m/s^{2}]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
vertical acceleration, $a_{z},[m/s^{2}]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
yaw rate, $\dot{\Psi},[\text{rad}/s]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
pitch rate, $\dot{\Theta},[\text{rad}/s]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
roll rate, $\dot{\Phi},[\text{rad}/s]$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
Table I: Signals and their respective frequencies, captured at their highest
available frequency on the Volvo XC90 experimental platform and down-sampled
for the experiments.

The goal of the study is to compare the performance (in terms of precision,
accuracy, and recall) of maneuver detectors to find potential passing
maneuvers when driving through a roundabout by exploiting multi-dimensional
kinematic signals as input for the SFCs. We use a Volvo XC90 from the vehicle
laboratory Chalmers Revere that has been instrumented with an Applanix GPS/IMU
system to obtain a baseline reference. In addition, on-board vehicle data as
listed in Tab. I is accessible via CAN for data logging. The vehicle was used
for a manual data collection of about
$56\text{\,}\mathrm{m}\mathrm{i}\mathrm{n}$ for a trip of
$14\text{\,}\mathrm{k}\mathrm{m}$ in an urban area within Gothenburg, Sweden
as shown in Fig. 2. The trip covered in total 17 roundabout scenarios by
visiting 7 different roundabouts on the route. The baseline for the
experiments as described in the following is defined two-fold: (a) manual
annotations were added to extract the time-points when entering a roundabout,
information about roundabout layout (ie., number of exits and chosen exit),
and the time-points when leaving the roundabout, and (b) by defining geofences
around all possible roundabouts along the trip as marked in Fig. 2.

(a) Lateral and longitudinal
accelerations over time.

(b) Corresponding Z-order curve stripes (lightgray), broken down to their
corresponding occurrence over time (black dots).

Figure 3: Lateral and longitudinal accelerations for passing through reference
roundabout $RA_{1}$, which is used to design the SFC-curves based maneuver
detector (left) and the corresponding stripes after mapping to a Z-order curve
based on Morton codes (right). The light-gray stripes denote the presence of a
SFC-value mapped from a multi-dimensional data tuple ($a_{x}$, $a_{y}$) with
$1$, and $0$ otherwise (left Y-axis); the black dots on top of the light-gray
stripes denote their respective occurrence over time (right Y-axis).

The geofences serve as input for an automatic GPS position-based maneuver
detector that encodes the GDPR-sensitive vehicle location onto an SFC curve as
follows: The two dimensions (latitude, longitude) were converted to single-
dimensional Morton codes (cf. Morton, [10] and Bader, [3]) resulting in a
positive integer number. This number was then used as sorted index to the
corresponding time $t$ of a GPS location resulting in a tuple
$(\text{\emph{Morton}}(\text{latitude}_{\text{pos}},\text{longitude}_{\text{pos}}),t)$.

The maneuver look-up is then a range query where the bottom/left and top/right
GPS location of a geofence are the lower and upper limits
($\text{\emph{Morton}}(\text{latitude}_{\text{BL}},\text{longitude}_{\text{BL}})$,
$\text{\emph{Morton}}(\text{latitude}_{\text{TR}},\text{longitude}_{\text{TR}})$)
on the single-dimensional space. All Morton indices between such lower and
upper limits correspond to potential candidate locations where the vehicle
potentially was passing through a roundabout. Finally, all such potential
pairs $(x,t_{x})$, with $x$ between the lower/upper limits as returned from
the range query, are converted back to the original tuple (latitude,
longitude) and filtered subsequently using a point-in-polygon test for the
corresponding geofence to compensate for potential false-positive Morton
candidates resulting from sudden “jumps” in the traversal of the Z-order curve
through the multi-dimensional space (see Fig. 1(a), right).

In contrast to the aforementioned maneuver detector, which is using a signal
that can be considered potentially being GDPR-sensitive, we setup a systematic
experiment for different maneuver detectors based on the two variants (a)
Z-order curve-based SFC using Morton codes (abbreviated as _M_ in Fig. 4), and
(b) Hilbert curve (abbreviated as _H_ in Fig. 4) to answer both research
questions. Both variants of SFCs convert multi-dimensional data samples into
their respective single-dimensional representations similar to the
aforementioned description for the geofence-based detector. Specific CSP as
shown in Fig. 3(b), in which the stripes occur in dedicated ranges over time,
correlate with specific automotive maneuvers in the original multi-dimensional
space. We use a CSP from a known reference maneuver when passing through a
roundabout ($\text{RA}_{1}$) to obtain the distribution of SFC values as shown
in Fig. 3. To detect subsequent passing maneuvers through roundabouts, a
dataset’s SFC values are traversed to check whether respective CSP ranges and
value distributions in the stripes are within the thresholds extracted from
the reference passing maneuver that we used for calibrating the maneuver
detector.

We systematically created permutations as listed in Fig. 4 for our
experimentation using the following configuration parameters to evaluate the
respective performance in finding drive-through maneuvers at roundabouts:

  1. 1.

Select Morton or Hilbert for SFC conversion.

  2. 2.

Select sampling frequency between 5 and $100\text{\,}\mathrm{Hz}$.

  3. 3.

Select combinations of minimum two signals from the set:
$\\{a_{x},a_{y},\delta_{S},\dot{\Psi}\\}$.

The motivation for the first option is to systematically evaluate what SFC
variant is showing a superior performance for detecting a passing maneuver.
The second option is to evaluate how much data is essential for a successful
maneuver detection; the motivation here is that data minimization is not only
reducing processing time and storage usage, but also obeying the data
minimization principle according to GDPR. Finally, systematic combinations of
various signals is evaluating to what degree certain kinematic parameters are
influencing a successful maneuver detection.

##  IV Results

$\text{Ex}_{1}$:$\text{Ex}_{2}$:$\text{Ex}_{3}$: Figure 4: Results from the
conducted experiments ordered by F1-score that is computed based on
overlapping time windows between the manually annotated ground truth and the
results obtained from the particular experiments as listed in the first
column; the values in the parenthesis denote the number of correctly
identified, distinct passes through roundabouts (TPs) followed by the number
of correctly identified passes (including duplicates) over total guesses
(including FPs). The width of the red and green bars show the returned
durations, respectively. The results for the last three experiments contain
very short durations that cannot be displayed clearly. As column headers, we
denote the time when a passing maneuver at a certain roundabout happened
including the roundabout’s configuration and what exit was chosen; for
example, 3/4 means that the roundabout had 4 exits and the third exit was
taken.

The results from our systematic experiments are aggregated and presented in
Fig. 4. The first column lists the specific configuration for a single
experiment, characterized by the chosen parameters: An SFC method for encoding
the multi-dimensional values, a combination of kinematic signals from the
multi-dimensional space, and a data sampling frequency. Other columns depict
each roundabout pass-through in the order of occurrence. Therefore, the x-axis
shows the temporal dimension: the length of each box refers to the event’s
duration. The top two rows show both baselines: The manually annotated
roundabout events and the results obtained from the geofence-based maneuver
detector. All subsequent rows show the results from a specific configuration
of an SFC-based maneuver detector.

The green boxes represent correctly identified passes through a roundabout
(true-positive, TP) and the red boxes indicate when a maneuver detector
returned time ranges from a maneuver that it believed was a passing maneuver
through a roundabout but it was not (false-positive, FP). The color was
assigned to each box by conducting a binary test whether the time range
returned by a detector is partially overlapping with the manual annotations.
Thus, green indicates an overlap, and red no overlap. In our experiments, we
consider a minimal overlap being sufficient for a TP hit. We determine such
overlapping time ranges by calculating the _intersection-over-union_ (IoU) of
the manually annotated ground truth with the returned time ranges of an
experiment. Each finding is set to green (a TP) if it has an IoU value greater
than $0$. In this setting, a 1-second-long overlap with a passing maneuver, a
100% overlap with a passing maneuver, or even ten different short detections
that overlap with a passing maneuver are all considered TPs, which we refer to
as Boolean-identified passes.

Alternatively, successful passes can also be defined as the amount of
intersecting seconds, FPs are then defined as the detected seconds without the
intersecting seconds, false-negative (FN) is defined as the ground truth time
windows without the intersections, and true-negative (TN) is the remaining
time (neither passing in the ground truth nor according to a detector). Fig. 4
is ordered using these time-based definitions by the F1-score of the
respective experiment because we prefer configurations for maneuver detectors
that find as many TPs as possible without being penalized by too many FPs;
intuitively speaking, we want as many green ranges for the costs of the least
red ranges as possible. This is also reflected by having the manual
annotations at the top (only TPs with no FPs), followed by the geofence-based
detector that is using GDPR-sensitive signals. It can be noted, though, that
while this detector correctly identifies all passing maneuvers as expected,
the dimensioning of the geofences may unintentionally reach into nearby
streets resulting in FPs (two in our experiment).

Based on the analysis of the results, we choose three exemplary experiment
configurations with different success rates and discuss their strengths: (i)
Hilbert with $\\{a_{x},a_{y},$10\text{\,}\mathrm{Hz}$\\}$, to which we will
refer as experiment $\text{Ex}_{1}$ from now on; (ii) Morton with
$\\{a_{x},a_{y},\delta_{S},\dot{\Psi},$5\text{\,}\mathrm{Hz}$\\}$, here forth
$\text{Ex}_{2}$; and (iii) Morton with
$\\{a_{x},a_{y},\dot{\Psi},$5\text{\,}\mathrm{Hz}$\\}$, here forth
$\text{Ex}_{3}$. The first two configurations use normalized data.

Out of the three selected experiments, $\text{Ex}_{1}$ has the greater F1
score, which we consider to indicate a good balance between finding the
maximum number of roundabout maneuvers (TPs) and minimizing false detections
(FPs). Nevertheless, $\text{Ex}_{1}$ only detects 6 out of the 17 manually
annotated passes and two of the roundabouts (RA1 and RA2) are never detected
with it. On the other hand, $\text{Ex}_{3}$ is able to detect 14 of the passes
at the expense of a higher number of false detections (54). In fact,
$\text{Ex}_{2}$ is one of the 31% of experiments to detect pass 2.
$\text{Ex}_{2}$ is also able to detect most of the passes and only missing 5.
However, unlike $\text{Ex}_{3}$, most of the predictions (63%) using
$\text{Ex}_{2}$ overlap with the manually annotated events.

Out of the 17 passes as depicted in Tab. II, 5 correspond to roundabout
maneuvers where the first exit was taken, and 5 to maneuvers where the second
exit was taken. These passes are only detected by 15% and 32% of the
experiment configurations, respectively. In contrast, maneuvers where the
third exit was taken are detected by 60% of the experiment configurations.
This shows that the longer an actual passing maneuver through a roundabout
takes, the higher is the maximum accuracy from all experiments as well as more
detector configurations will spot such a maneuver. However, as depicted in
Fig. 4, the exit taken does not necessarily affect the length of the maneuver,
yet maneuvers that consist of a full turn (or more) are detected by more than
94% of the experiment configurations, including $\text{Ex}_{1}$,
$\text{Ex}_{2}$, and $\text{Ex}_{3}$.

Another aspect to consider are multiple detections of a single roundabout.
This can be seen in Fig. 4 as multiple green boxes overlapping with the same
pass in the manually annotated data. For instance, pass 15 was detected twice,
and pass 17 was detected three times using $\text{Ex}_{1}$; and when using
$\text{Ex}_{2}$ and $\text{Ex}_{3}$, each of the 4 passes that went through
RA5 was detected twice. This raises the question as discussed in Sec. V about
whether a part of the roundabout in SFC space is enough to claim that a
roundabout maneuver was successfully detected. Moreover, experiment
configurations that break down single maneuvers into multiple detections also
have a higher number of false predictions as can be seen for $\text{Ex}_{3}$
in Fig. 4.

Pass | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Roundabout | RA1 | RA2 | RA3 | RA3 | RA4 | RA5 | RA4 | RA5 | RA6 | RA6 | RA7 | RA7 | RA7 | RA5 | RA4 | RA5 | RA6
Exit taken | 3/4 | 2/4 | 6/5 | 2/5 | 2/4 | 4/4 | 1/4 | 2/4 | 1/4 | 1/4 | 1/4 | 4/4 | 1/4 | 2/4 | 8/4 | 5/4 | 14/4
Hits (over all) | 60% | 31% | 96% | - | 40% | 81% | 15% | 46% | 38% | - | - | 85% | 25% | 42% | 94% | 96% | 98%
Max. overlap (%) | 83% | 83% | 86% | - | 82% | 86% | 69% | 83% | 82% | - | - | 86% | 83% | 83% | 86% | 86% | 86%

Table II: Boolean hits and maximum percentage of overlap across all
experiments (omitting the geofence-based detector).

The selected experiments described before therefore trigger three important
discussions for Sec. V: (i) the balance of metrics such as precision and
recall to determine success, (ii) the trade-off between the data inputs and
the amount of correctly identified passes, and (iii) whether fractions of a
roundabout (small time-window), can be considered a TP as indicated above.

##  V Analysis & Discussion

As expected, the automatic geofence-based detector, which exploits the GPS
location to detect roundabouts, is scoring perfect results in terms of both
precision and recall. However, as discussed before, GPS information may be
considered as a GDPR-sensitive information. An alternative detection strategy
that does not rely on such information is therefore preferred.

Answering RQ-1, all experiment configurations were able to detect at least one
roundabout passing maneuver, relying on non-GDPR-sensitive data only. However,
three passes were not detected by any of the experiment configurations.

According to the ordering as shown in Fig. 4, the most successful performing
configuration is Morton using $\\{a_{x},a_{y},\delta_{S},\dot{\Psi}\\}$ at
$5\text{\,}\mathrm{Hz}$ (marked as $\text{Ex}_{3}$ in Fig. 4) returning 14 out
of 17 maneuvers. Nevertheless, this high detection rate often comes at the
expense of a low precision due to an increasing number of FPs. Moreover, the
length in time of the detections is shorter than the manually annotated passes
as the green ranges that are overlapping between the manual annotations and
the experiment’s results become smaller. Hence, in order to decide what
experiment can be considered more successful over others is requiring a
definition of a correctly identified passing maneuver (TP). The first option
is Boolean detection, ie., caring about how many intersections with the ground
truth are present. Therefore, the actual width of the green ranges is of
secondary interest but rather the amount of distinct yet correct TPs is
preferred. The second option is caring about which percentage of the manually
annotated time windows corresponding to roundabout passes is detected by each
of the experiments.

Answering RQ-2, we discussed a number of experiment configurations that are
able to detect roundabout passing maneuvers successfully. However, metrics for
“success” might depend on the application of the proposed technique.

It is important to note that three passing maneuvers are not detected by any
of the configurations listed Fig. 4: Passes 4, 10, and 11 as described in Tab.
II. These passes may be particularly challenging: In the former, the second
exit was taken, which may be appearing an evasive maneuver; while in the
latter the first exit was taken, making it similar to a simple right turn
maneuver.

Experiment configurations that do not use steering wheel angle information
like $\text{Ex}_{1}$ and $\text{Ex}_{3}$ detect on average a higher percentage
of the manually annotated maneuvers. At the same time, configurations that do
not use steering wheel angle information were only able to detect a maximum of
9 out of the 17 passes. Similarly, configurations that do not use the yaw rate
to detect roundabout events also ranked higher yet none of them was able to
detect passes 2, 4, 10, or 11. Interestingly, the passes which benefitted the
most from not using steering wheel angle or yaw rate, were maneuvers when the
roundabout was passed for at least one complete round.

In order to decide what experiment was more successful, the relative
importance of TPs, FPs and FNs needs to be determined independently on whether
we use Boolean or continuous definitions for correctly identified passes. In
the context of Advanced Driver Assistance System / Automated Driving
(ADAS/AD), FPs are typically less problematic than FNs, so we ordered the
experiments in Fig. 4 based on the F1-score computed based on overlapping time
windows. It is therefore important before using our technique to automatically
detect maneuvers without relying on GDPR-sensitive data to decide what is
preferable: A small intersection with the ground truth might be enough to
trigger a roundabout-specific ADAS/AD behavior, ie., making the Boolean
approach useful depending on such detections shall be post-processed. In a
similar way, a different balance between TP, FP, and FN might be needed
depending on the application context otherwise.

We report threats to validity following Feldt and Magazinius [11]. The data
used in the experiments detailed in Section 4 correspond to a limited data
collection and showcase a selected number of events corresponding to
roundabout pass-through maneuvers, which may pose an internal threat to
validity. Even though the discussed input signals as reported in Tab. I are
typically used for maneuver identification, we cannot claim generalizability
of these results over alternative selections of signals or newly collected
data at other locations; for example, many roundabouts along the trip included
also a road bump to reduce speed, which on the one hand would even allow to
improve the identification due to this particularity visible in $a_{z}$;
however, this aspect is on the other not necessarily standard in other
locations or countries and hence, we excluded this parameter.

##  VI Conclusion and Future Work

We are presenting a systematic evaluation of SFC to be used for automotive
maneuver detection on the example of finding maneuvers for passing a
roundabout. SFCs allow for mapping multi-dimensional data into their single-
dimensional representations and hence, such data can be processed
computationally efficiently. This becomes important when working with ever-
growing data lakes collected from large vehicle fleets, or when using
automatic maneuver detectors that shall be used in real-time on the vehicle.

Uniquely for our study is that we are interested in the performance of the
maneuver detectors when dropping signals that may be GDPR-sensitive such as
GPS locations. Changing the sampling rate or the SFC encoding can improve the
number of true-positives but at an expense of finding more FPs as well,
rendering such detectors impractical. In order to make decisions on which
experiment configuration is more successful, application domain details need
to be considered as discussed in Sec. IV using three examples with different
time overlap and number of detections.

Future work may refine the design of the maneuver detectors further to lower
the false-positive rates. In addition, the particularly challenging maneuver
when leaving a roundabout already at the first exit in comparison to a plain
turning right maneuver needs to be addressed further to better separate
different automotive maneuvers when using non-GDPR-sensitive signals. As we
conducted our experiments with data from Gothenburg, Sweden, also the
transferability of our findings needs to be explored further when looking at
data from other regions.

## References

  * [1] C. Berger and L. Birkemeyer, “ZEBRA: Z-order Curve-based Event Retrieval Approach to Efficiently Explore Automotive Data,” in _2023 IEEE Intelligent Vehicles Symposium (IV)_ , 2023, pp. 1–7. [Online]. Available: https://ieeexplore.ieee.org/document/10186770
  * [2] M. A. Perez, J. D. Sudweeks, E. Sears, J. Antin, S. Lee, J. M. Hankey, and T. A. Dingus, “Performance of basic kinematic thresholds in the identification of crash and near-crash events within naturalistic driving data,” _Accident Analysis & Prevention_, vol. 103, pp. 10–19, 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0001457517301033
  * [3] M. Bader, _Space-Filling Curves_. Springer Berlin, Heidelberg, 2013. [Online]. Available: https://link.springer.com/book/10.1007/978-3-642-31046-1
  * [4] A. Hulbert, T. Kunicki, J. N. Hughes, A. D. Fox, and C. N. Eichelberger, “An experimental study of big spatial data systems,” in _2016 IEEE International Conference on Big Data (Big Data)_. Washington, DC, USA: IEEE, 2016, pp. 2664–2671. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/7840909
  * [5] H. Dai and H.-C. Su, “Clustering Analyses of Two-Dimensional Space-Filling Curves: Hilbert and z-Order Curves,” _SpringerNature Computer Science_ , vol. 4, no. 1, p. 8, 2022. [Online]. Available: https://link.springer.com/article/10.1007/s42979-022-01320-9
  * [6] B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz, “Analysis of the clustering properties of the Hilbert space-filling curve,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 13, no. 1, pp. 124–141, 2001. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/908985
  * [7] A. A. Safia, Z. A. Aghbari, and I. Kamel, “Distributed Environmental Event Monitoring using Mobile Wireless Sensor Network,” _Procedia Computer Science_ , vol. 155, pp. 335–342, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1877050919309627
  * [8] H. Liu, J. Yan, J. Wang, B. Chen, M. Chen, and X. Huang, “HGST: A Hilbert-GeoSOT Spatio-Temporal Meshing and Coding Method for Efficient Spatio-Temporal Range Query on Massive Trajectory Data,” _ISPRS International Journal of Geo-Information_ , vol. 12, no. 3, 2023. [Online]. Available: https://www.mdpi.com/2220-9964/12/3/113
  * [9] S. H. Nair, A. Sinha, and L. Vachhani, “Hilbert’s space-filling curve for regions with holes,” in _2017 IEEE 56th Annual Conference on Decision and Control (CDC)_ , 2017, pp. 313–319. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/8263684
  * [10] G. M. Morton, “A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing,” 1966. [Online]. Available: https://dominoweb.draco.res.ibm.com/reports/Morton1966.pdf
  * [11] R. Feldt and A. Magazinius, “Validity Threats in Empirical Software Engineering Research - An Initial Survey,” in _SEKE_ , 2010. [Online]. Available: https://www.cse.chalmers.se/~feldt/publications/feldt_2010_validity_threats_in_ese_initial_survey.pdf


# ON PERIODIC DECOMPOSITIONS AND NONEXPANSIVE LINES

Cleber Fernando Colle  Rio de Janeiro State University, Rio de Janeiro, Brazil
<EMAIL_ADDRESS>
###### Abstract.

In his Ph.D. thesis, Michal Szabados conjectured that for a not fully periodic
configuration with a minimal periodic decomposition the nonexpansive lines are
exactly the lines that contain a period for some periodic configuration in
such decomposition. In this paper, we study Szabados’s conjecture. First, we
show that we may consider a minimal periodic decomposition where each periodic
configuration is defined on a finite alphabet. Then we prove that Szabados’s
conjecture holds for a wide class of configurations, which includes all not
fully periodic low convex pattern complexity configurations.

###### Key words and phrases:

$\mathbb{Z}^{2}$-subshifts, Nonexpansive subdynamics, Periodic decompositions.

##  1\. Introduction

In his Ph.D. thesis [12], with an algebraic viewpoint on symbolic
configurations, Michal Szabados showed that every low pattern complexity
configuration can be decomposed into a finite sum of periodic configurations.
Such a periodic decomposition theorem is the heart of new recent results
related to Nivat’s conjecture and other topics [8, 11, 5, 6, 9, 7, 2]. If we
consider a not fully periodic configuration with a minimal periodic
decomposition, i.e., a periodic decomposition with the smallest possible
number of periodic configurations, a nonexpansive line contains a period of
some periodic configuration. Michal Szabados conjectured that the conversely
also holds.

To make the statements precise we need to introduce some terminologies.

###  1.1. Symbolic dynamics

Let $\mathcal{A}$ be an alphabet with at least two elements. The elements of
$\mathcal{A}^{\mathbb{Z}^{2}}$, called _configurations_ , have the form
$\eta=(\eta_{g})_{g\in\mathbb{Z}^{2}}$, where $\eta_{g}\in\mathcal{A}$ for all
$g\in\mathbb{Z}^{2}$. For each $u\in\mathbb{Z}^{2}$, the _shift application_
$T^{u}:\mathcal{A}^{\mathbb{Z}^{2}}\longrightarrow\mathcal{A}^{\mathbb{Z}^{2}}$
is defined by $(T^{u}\eta)_{g}=\eta_{g-u}$ for all $g\in\mathbb{Z}^{2}$ and
all $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$. A configuration
$\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ is said to be _periodic_ if there exists
a non-zero vector $h\in\mathbb{Z}^{2}$, called _period_ of $\eta$, such that
$T^{h}\eta=\eta$. If $\eta$ has two periods linearly independents over
$\mathbb{R}^{2}$, we say that $\eta$ is _fully periodic_.

Let $Orb\,(\eta)=\\{T^{u}\eta:u\in\mathbb{Z}^{2}\\}$ denotes the
_$\mathbb{Z}^{2}$ -orbit of $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$_. If
$\mathcal{A}$ is a finite alphabet endowed with the discrete topology, then
$\mathcal{A}^{\mathbb{Z}^{2}}$ equipped with the product topology is a
metrizable compact space. In particular, for all
$\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, the set $\overline{Orb\,(\eta)}$, where
the bar denotes the closure, is a compact _subshift_ , i.e., a closed subset
invariant by the $\mathbb{Z}^{2}$-action $T^{u}$, $u\in\mathbb{Z}^{2}$.

If $\mathcal{A}$ is finite, we say that a configuration
$\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ has _low pattern complexity_ if
$|\\{T^{u}\eta{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{S}$}:u\in\mathbb{Z}^{2}\\}|\leq|\mathcal{S}|$
holds for some non-empty, finite set $\mathcal{S}\subset\mathbb{Z}^{2}$, where
$\cdot{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{S}$}$ means the restriction
to the set $\mathcal{S}$. If in addition $\mathcal{S}$ is _convex_ , i.e., a
subset of $\mathbb{Z}^{2}$ whose convex hull in $\mathbb{R}^{2}$, denoted by
$\operatorname{Conv}(\mathcal{S})$, is closed and
$\mathcal{S}=\operatorname{Conv}(\mathcal{S})\cap\mathbb{Z}^{2}$, we say that
$\eta$ has _low convex pattern complexity_.

From now on, we will assume that $\mathcal{A}$ is a finite alphabet endowed
with the dis- crete topology.

###  1.2. Nonexpansive lines

Let $\ell\subset\mathbb{R}^{2}$ be a line through the origin. Given $t>0$, the
$t$-neighbourhood of $\ell$ is defined as

$\ell^{t}=\\{g\in\mathbb{Z}^{2}:\operatorname{Dist}(g,\ell)\leq t\\}.$

Following Boyle and Lind [1], we say that $\ell$ is an _expansive_ line on
$\overline{Orb\,(\eta)}$ if there exists $t>0$ such that

$\forall\ x,y\in\overline{Orb\,(\eta)},\quad
x{\mathbin{|}}\raise-1.72218pt\hbox{$\ell^{t}$}=y{\mathbin{|}}\raise-1.72218pt\hbox{$\ell^{t}$}\implies
x=y.$

Otherwise, $\ell$ is called a _nonexpansive_ line on $\overline{Orb\,(\eta)}$.

For a configuration $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, we use
$\operatorname{NEL}(\eta)$ to denote the set formed by the nonexpansive lines
on $\overline{Orb\,(\eta)}$. A particular case of Boyle-Lind Theorem [1,
Theorem 3.7] implies that $\operatorname{NEL}(\eta)$ has at least one element
if the subshift $\overline{Orb\,(\eta)}$ is infinite. An immediate application
of Boyle-Lind Theorem allows us to state the following result:

######  Theorem 1.1.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ be a configuration. Then
$\operatorname{NEL}(\eta)=\emptyset$ if and only if $\eta$ is fully periodic.

When $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ is a periodic configuration, but
not fully periodic, it is easy to see that the unique line
$\ell\in\operatorname{NEL}(\eta)$, which exists due to Boyle-Lind Theorem,
contains any period for $\eta$. Hence, any configuration
$\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ where $\operatorname{NEL}(\eta)$ has at
least two lines can not be periodic.

###  1.3. The algebraic viewpoint

In [9], Kari and Szabados introduced an algebraic viewpoint on symbolic
configurations. To follow their approach, we consider $R=\mathbb{Z}$ or some
finite field, and we represent any configuration $\eta\in R^{\mathbb{Z}^{2}}$
as a formal power series over two variable $x_{1}$ and $x_{2}$ with
coefficients $\eta_{g}\in R$, i.e., as an element of

$R[[X^{\pm 1}]]=\left\\{\sum_{g\in\mathbb{Z}^{2}}a_{g}X^{g}:a_{g}\in
R\right\\},$

where $g=(g_{1},g_{2})$ and $X^{g}$ is a shorthand for
$x_{1}^{g_{1}}x_{2}^{g_{2}}$. Let $R[X^{\pm 1}]\subset R[[X^{\pm 1}]]$ denote
the set of Laurent polynomials with coefficients in $R$. Given a Laurent
polynomial $\varphi(X)=a_{1}X^{u_{1}}+\cdots+a_{n}X^{u_{n}}$, with $a_{i}\in
R$ and $u_{i}\in\mathbb{Z}^{2}$, and a configuration $\eta\in R[[X^{\pm 1}]]$,
we may consider the configuration $\varphi\eta\in R[[X^{\pm 1}]]$, where

$(\varphi\eta)_{g}=a_{1}\eta_{g-u_{1}}+\cdots+a_{n}\eta_{g-u_{n}}\quad\forall
g\in\mathbb{Z}^{2}.$ (1.1)

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, be a
configuration. A Laurent polynomial $\varphi\in R[X^{\pm 1}]$ _annihilates
$\eta$_ if and only if $\varphi\eta=0$, where by $0$ we mean the zero
configuration. The set of Laurent polynomials $\varphi\in R[X^{\pm 1}]$ that
annihilates $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ is denoted by
$\operatorname{Ann}_{R}(\eta)$. In this algebraic setting, $\eta\in R[[X^{\pm
1}]]$ is periodic of period $h\in\mathbb{Z}^{2}$ if and only if
$(X^{h}-1)\eta=0$.

We remark that the operations in (1.1) are the binary operations of
$(R,+,\cdot)$. The multiplicative and additive identities on $R$ are denoted
by $1$ and $0$, respectively, and, for any $x,y\in R$, $x-y:=x+(-y)$, where
$-y\in R$ denotes the inverse additive of $y$. In the most part of this work,
we will consider $R=\mathbb{Z}_{p}$ for some prime number
$p\in\mathbb{N}$111We use $\mathbb{N}=\\{1,2,\ldots\\}$ and
$\mathbb{Z}_{+}=\mathbb{N}\cup\\{0\\}$..

######  Theorem 1.2 (Kari and Szabados [9]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}$, be a low pattern complexity configuration.
Then there exist periodic configurations
$\eta_{1},\ldots,\eta_{m}\in\mathbb{Z}[[X^{\pm 1}]]$ such that
$\eta=\eta_{1}+\cdots+\eta_{m}$.

The configurations $\eta_{i}\in\mathbb{Z}[[X^{\pm 1}]]$ in the Theorem 1.2 may
be defined on infinite alphabets (see [9, Example 17]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, and
suppose $\eta_{1},\ldots,\eta_{m}\in R[[X^{\pm 1}]]$ are periodic
configurations such that $\eta=\eta_{1}+\cdots+\eta_{m}$. We call
$\eta=\eta_{1}+\cdots+\eta_{m}$ a _$R$ -periodic decomposition_. If $m\leq n$
for every $R$-periodic decomposition
$\eta=\eta^{\prime}_{1}+\cdots+\eta^{\prime}_{n}$, we call
$\eta=\eta_{1}+\cdots+\eta_{m}$ a _$R$ -minimal periodic decomposition_ and
the number $m$ is called the _$R$ -order of $\eta$_.

######  Remark 1.3.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, and
suppose $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $R$-minimal periodic
decomposition.

  1. (i)

If $\eta$ has $R$-order $m\geq 2$, then any two periods for $\eta_{i}$ and
$\eta_{j}$, with $i\neq j$, are in distinct directions;

  2. (ii)

If $\eta$ has $R$-order $m=1$, then either $\eta$ periodic or $\eta$ is fully
periodic,

######  Remark 1.4.

If $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}_{p}$-minimal periodic
decomposition, then each configuration $\eta_{i}\in\mathbb{Z}_{p}[[X^{\pm
1}]]$, with $1\leq i\leq m$, is defined on a finite alphabet.

If $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}$-minimal periodic
decomposition, it is easy to see that every nonexpansive line on
$\overline{Orb\,(\eta)}$ contains a period of some $\eta_{i}$, with $1\leq
i\leq m$ (see Remark 2.6). In his Ph.D. thesis [12], Michal Szabados
conjectured that the conversely also holds:

######  Conjecture 1.5 (Szabados).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}$, be a configuration. If $\eta$ is not fully
periodic and $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}$-minimal
periodic decomposition, then, for each $1\leq i\leq m$, a line
$\ell\subset\mathbb{R}^{2}$ contains a period for $\eta_{i}$ if and only if
$\ell\in\operatorname{NEL}(\eta)$.

Szabados’s conjecture is a very recent open problem in symbolic dynamics and
for the best we know there are not many works toward a proof for the
conjecture.

Thanks to Proposition 2.7, we know that Szabados’s conjecture holds for any
not fully periodic configuration with $\mathbb{Z}$-order $2$. In [2], the
author showed that Szabados’s conjecture holds for a not fully periodic low
convex pattern complexity configuration $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$,
with $\mathcal{A}\subset\mathbb{Z}$, such that all non-periodic configurations
in $\overline{Orb\,(\eta)}$ have the same $\mathbb{Z}$-order. As a corollary,
the author got that Szabados’s conjecture holds for any not fully periodic low
convex pattern complexity configuration with $\mathbb{Z}$-order $3$.

In this paper, as a corollary of our main result we get that Szabados’s
conjecture holds for any not fully periodic low convex pattern complexity
configuration.

###  1.4. Our contributions

We believe that the difficulty in approaching Szabados’s conjecture remains
mostly on the fact that the periodic configurations in a periodic
decomposition may not be defined on finite alphabets. Our first result allows
us to get around this difficulty.

Given $n\in\mathbb{N}$, let us denote $[[n]]=\\{0,1,2,\ldots,n-1\\}$.

######  Theorem 1.6.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}_{+}$, be a configuration. If
$\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}$-minimal periodic
decomposition, then, for some prime number $p\in\mathbb{N}$, with
$\mathcal{A}\subset[[p]]$,
$\overline{\eta}=\overline{\eta}_{1}+\cdots+\overline{\eta}_{m}$ is a
$\mathbb{Z}_{p}$-minimal periodic decomposition, where the bar denotes the
congruence modulo $p$.

By using Theorem 1.6, we get the following result:

######  Theorem 1.7.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}$, be a not fully periodic configuration and
suppose $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}$-minimal periodic
decomposition. If for any configuration $x\in\overline{Orb\,(\eta)}$ the
subshift $\overline{Orb\,(x)}$ has a periodic configuration, then, for each
$1\leq i\leq m$, a line $\ell\subset\mathbb{R}^{2}$ contains a period for
$\eta_{i}$ if and only if $\ell\in\operatorname{NEL}(\eta)$.

As an application of Theorem 1.7, we get the following result:

######  Corollary 1.8.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}$, be a not fully periodic low convex
patterncomplexity configuration and suppose $\eta=\eta_{1}+\cdots+\eta_{m}$ is
a $\mathbb{Z}$-minimal periodic decomposition. Then, for each $1\leq i\leq m$,
a line $\ell\subset\mathbb{R}^{2}$ contains a period for $\eta_{i}$ if and
only if $\ell\in\operatorname{NEL}(\eta)$.

###### Proof.

Theorem 1.14 of [2] and standard results from [3, 9] imply that for any con-
figuration $x\in\overline{Orb\,(\eta)}$ the subshift $\overline{Orb\,(x)}$ has
a periodic configuration (see Propositions 2.10 and 2.12 of [2] for detailed
statements). Therefore, the corollary follows by Theorem 1.7. ∎

##  2\. Background

In this section, we will revisit terminologies, known results or immediate
applications of known results.

###  2.1. One-sided nonexpansive directions

In the sequel, we will revisit a more refined version of expansiveness called
one-sided nonexpansiveness and introduced by Cyr and Kra in [3]. We recall
that two vectors are parallel if they have the same direction and antiparallel
if they have opposite directions. Two oriented objects in $\mathbb{R}^{2}$ are
said to be _(anti)parallel_ if the adjacent vectors to their respective
orientations are (anti)parallel, where by object we mean an oriented line, an
oriented line segment or a vector. In a slight abuse of notation, we will view
an oriented line also as a subset of $\mathbb{R}^{2}$.

Given a line $\ell\subset\mathbb{R}^{2}$, we use $\boldsymbol{\ell}$ to denote
the line $\ell$ endowed of a given orientation. Let
$\boldsymbol{\ell}\subset\mathbb{R}^{2}$ be an oriented line. The half plane
determined by $\boldsymbol{\ell}$ is defined as

$\mathcal{H}(\boldsymbol{\ell}):=\\{(g_{1},g_{2})\in\mathbb{Z}^{2}:u_{1}g_{2}-u_{2}g_{1}\geq
0\\},$

where $(u_{1},u_{2})\in\mathbb{R}^{2}$ is a non-zero vector parallel to
$\boldsymbol{\ell}$. Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ be a
configuration. An oriented line $\boldsymbol{\ell}\subset\mathbb{R}^{2}$
through the origin is called a _one-sided expansive direction on
$\overline{Orb\,(\eta)}$_ if

$\forall\ x,y\in\overline{Orb\,(\eta)},\quad
x{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{H}(\boldsymbol{\ell})$}=y{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{H}(\boldsymbol{\ell})$}\
\Longrightarrow\ x=y.$

Otherwise, $\boldsymbol{\ell}$ is called a _one-sided nonexpansive direction
on $\overline{Orb\,(\eta)}$_.

For a configuration $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, we use
$\operatorname{ONED}(\eta)$ to denote the set formed by the one-sided
nonexpansive directions on $\overline{Orb\,(\eta)}$. By the compactness of
$\overline{Orb\,(\eta)}$, a line $\ell\in\operatorname{NEL}(\eta)$ if and only
if, for some orientation, $\boldsymbol{\ell}\in\operatorname{ONED}(\eta)$ (see
[3] for more details). As highlighted in [3], lines in
$\operatorname{NEL}(\eta)$ or oriented lines in $\operatorname{ONED}(\eta)$
are rational, where by _rational_ we mean a line or an oriented line in
$\mathbb{R}^{2}$ with a rational slope.

###  2.2. Geometric notations

Let $\boldsymbol{\ell}\subset\mathbb{R}^{2}$ be an oriented line and suppose
$\mathcal{S}\subset\mathbb{Z}^{2}$ is a non-empty, convex set such that
$\mathcal{S}+u\subset\mathcal{H}(\boldsymbol{\ell})$ for some
$u\in\mathbb{Z}^{2}$. The _support line of $\mathcal{S}$_ determined by
$\boldsymbol{\ell}$, denoted by $\boldsymbol{\ell}_{\mathcal{S}}$, is defined
as the oriented line $\boldsymbol{\ell}^{\prime}$ parallel to
$\boldsymbol{\ell}$ such that
$\mathcal{S}\subset\mathcal{H}(\boldsymbol{\ell}^{\prime})$ and
$\boldsymbol{\ell}^{\prime}\cap\mathcal{S}\neq\emptyset$. Of course, if
$\mathcal{S}\subset\mathbb{Z}^{2}$ is a non-empty, finite, convex set, then
$\boldsymbol{\ell}_{\mathcal{S}}$ is defined.

Let $\mathcal{S}\subset\mathbb{Z}^{2}$ be a non-empty, convex set. If
$\mathcal{S}$ has at least two points and
$|\mathcal{S}\cap\boldsymbol{\ell}^{\prime}_{\mathcal{S}}|=1$ holds for some
oriented line $\boldsymbol{\ell}^{\prime}\subset\mathbb{R}^{2}$, we call
$\mathcal{S}\cap\boldsymbol{\ell}^{\prime}_{\mathcal{S}}$ a _vertex_ of
$\mathcal{S}$. If $\operatorname{Conv}(\mathcal{S})$ has positive area and
$|\mathcal{S}\cap\boldsymbol{\ell}^{\prime}_{\mathcal{S}}|>1$ holds for some
oriented line $\boldsymbol{\ell}^{\prime}\subset\mathbb{R}^{2}$, we call
$\operatorname{Conv}(\mathcal{S}\cap\boldsymbol{\ell}^{\prime}_{\mathcal{S}})$
an _edge_ of $\mathcal{S}$. We use $E(\mathcal{S})$ to denote the set of edges
of $\mathcal{S}$.

If $\mathcal{S}\subset\mathbb{Z}^{2}$ is a convex set (possibly infinite) such
that $\operatorname{Conv}(\mathcal{S})$ has positive area, our standard
convention is that the boundary of $\operatorname{Conv}(\mathcal{S})$ is
positively oriented. With this convention, every edge $w\in E(\mathcal{S})$
inherits a natural orientation from the boundary of
$\operatorname{Conv}(\mathcal{S})$. Moreover, if
$w=\operatorname{Conv}(\mathcal{S}\cap\boldsymbol{\ell}^{\prime}_{\mathcal{S}})$,
then $w$ and $\boldsymbol{\ell}^{\prime}$ are parallels.

###  2.3. Generating sets

The notion of generating set was developed in [3] and studied in a more
general setting on [4].

######  Definition 2.1.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ be a configuration and suppose
$\mathcal{S}\subset\mathbb{Z}^{2}$ is a finite set. A point $g\in\mathcal{S}$
is said to be _$\eta$ -generated by $\mathcal{S}$_ if
$P_{\eta}(\mathcal{S})=P_{\eta}(\mathcal{S}\backslash\\{g\\})$. A non-empty,
finite, convex subset of $\mathbb{Z}^{2}$ for which each vertex is
$\eta$-generated is called an _$\eta$ -generating set_.

A point $u_{0}\in\mathcal{S}$ is $\eta$-generated by $\mathcal{S}$ if and only
if, for each $g\in\mathbb{Z}^{2}$, $\eta_{g-u}$ for $u\in\mathcal{S}$, with
$u\neq u_{0}$, determines $\eta_{g-u_{0}}$.

Let $\mathcal{S}\subset\mathbb{Z}^{2}$ be an $\eta$-generating set. Only
oriented lines parallels to some edge of $\mathcal{S}$ may be one-sided
nonexpansive directions on $\overline{Orb\,(\eta)}$:

######  Lemma 2.2 (Cyr and Kra [3]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ and suppose
$\boldsymbol{\ell}\subset\mathbb{R}^{2}$ is an oriented line through the
origin and $\mathcal{S}\subset\mathbb{Z}^{2}$ is a finite, convex set such
that $\mathcal{S}\cap\boldsymbol{\ell}_{\mathcal{S}}=\\{g_{0}\\}$ is
$\eta$-generated by $\mathcal{S}$. Then
$\boldsymbol{\ell}\not\in\operatorname{ONED}(\eta)$.

Let $\varphi(X)=\sum_{i}a_{i}X^{u_{i}}$, with $a_{i}\in R$ and
$u_{i}\in\mathbb{Z}^{2}$, be a Laurent polynomial. The _support_ of $\varphi$
is defined as

$\operatorname{Supp}(\varphi):=\\{u_{i}\in\mathbb{Z}^{2}:a_{i}\neq 0\\}.$

The _reflected convex support of $\varphi$_ is defined as
$\mathcal{S}_{\varphi}:=\operatorname{Conv}(-\operatorname{Supp}(\varphi))\cap\mathbb{Z}^{2}$.

######  Remark 2.3.

For $\varphi(X)=(X^{h_{1}}-1)\cdots(X^{h_{m}}-1)$, with
$h_{1},\ldots,h_{m}\in(\mathbb{Z}^{2})^{*}$, it is easy to see that

$\operatorname{Supp}(\varphi)=\\{(0,0)\\}\cup\\{h_{i_{1}}+\cdots+h_{i_{r}}:1\leq
i_{1}<\cdots<i_{r}\leq m,\ 1\leq r\leq m\\}.$

Suppose that $\operatorname{Conv}(\mathcal{S}_{\varphi})$ has positive area.
Then every edge of $\mathcal{S}_{\varphi}$ is either parallel or antiparallel
to some vector $h_{i}$, with $1\leq i\leq m$. If we suppose in addition that
the vectors $h_{1},\ldots,h_{m}$ are in pairwise distinct directions, then,
for each $1\leq i\leq m$, there exist edges $-w_{i},w_{i}\in
E(\mathcal{S}_{\varphi})$ such that $-w_{i}$ is parallel to $-h_{i}$ and
$w_{i}$ is parallel to $h_{i}$.

######  Lemma 2.4 (Szabados [11]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, be a
configuration. If $\varphi\in\operatorname{Ann}_{R}(\eta)$, then
$\mathcal{S}_{\varphi}$ is an $\eta$-generating set.

###### Proof.

Let $\varphi(X)=\sum_{i}a_{i}X^{u_{i}}$, with $a_{i}\in R$ and
$u_{i}\in\mathbb{Z}^{2}$. Given $g\in\mathbb{Z}^{2}$ and
$u_{0}\in\operatorname{Supp}(\varphi)$, the values $\eta_{g-u}$ for
$u\in\operatorname{Supp}(\varphi)$, with $u\neq u_{0}$, determines
$\eta_{g-u_{0}}$ by applying equation
$a_{1}\eta_{g-u_{1}}+\cdots+a_{n}\eta_{g-u_{n}}=0$. This means that
$-u_{0}\in-\operatorname{Supp}(\varphi)$ is $\eta$-generated by
$-\operatorname{Supp}(\varphi)$. ∎

As an immediate application of the previous two lemmas, we have the following
remark:

######  Remark 2.5 (Szabados [11]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, be a
configuration. Suppose that
$\varphi(X)=(X^{h_{1}}-1)\cdots(X^{h_{m}}-1)\in\operatorname{Ann}_{R}(\eta)$,
with $h_{1},\ldots,h_{m}\in(\mathbb{Z}^{2})^{*}$, and that
$\operatorname{Conv}(\mathcal{S}_{\varphi})$ has positive area. In particular,
$\mathcal{S}_{\varphi}$ is an $\eta$-generating set. If
$\boldsymbol{\ell}\in\operatorname{ONED}(\eta)$, then, thanks to Lemma 2.2,
$\boldsymbol{\ell}$ is parallel to some edge of $\mathcal{S}_{\varphi}$.
Hence, according to Remark 2.3, $\boldsymbol{\ell}$ is either parallel or
antiparallel to some vector $h_{i}$, with $1\leq i\leq m$.

The previous remark allows us to show that the conversely of Szabados’s
conjecture holds:

######  Remark 2.6.

If $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $R$-minimal periodic decomposition and
$\ell\in\operatorname{NEL}(\eta)$, then $\ell$ contains a period of some
$\eta_{i}$, with $1\leq i\leq m$. Indeed, if $m=1$, then there is nothing to
argue. Otherwise, let $h_{i}\in\mathbb{Z}^{2}$ be a period for $\eta_{i}$,
with $1\leq i\leq m$, and consider the Laurent polynomial
$\varphi(X)=(X^{h_{1}}-1)\cdots(X^{h_{m}}-1)$. Since the vectors
$h_{1},\ldots,h_{m}$ are in pairwise distinct directions, then
$\operatorname{Conv}(\mathcal{S}_{\varphi})$ has positive area. Since
$\varphi\in\operatorname{Ann}_{R}(\eta)$ and, for some orientation,
$\boldsymbol{\ell}\in\operatorname{ONED}(\eta)$, by the previous remark it
follows that $\boldsymbol{\ell}$ is either parallel or antiparallel to some
vector $h_{i}$, with $1\leq i\leq m$, which means that $\ell$ contains a
period of some $\eta_{i}$, with $1\leq i\leq m$.

The next result is a rewrite of a particular case of [4, Lemma 5.10], a well-
known result.

######  Proposition 2.7 (Franks and Kra [4]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, be a
configur- ation. Suppose
$\varphi(X)=(X^{h_{1}}-1)(X^{h_{2}}-1)\in\operatorname{Ann}_{R}(\eta)$ and
$h_{1},h_{2}\in\mathbb{Z}^{2}$ are vectors in distinct directions. If
$\boldsymbol{\ell}\subset\mathbb{R}^{2}$ is an oriented line through the
origin parallel to an edge of $\mathcal{S}_{\mathcal{\varphi}}$ and
$\boldsymbol{\ell}\not\in\operatorname{ONED}(\eta)$, then $\eta$ is periodic.

As an immediate application of Proposition 2.7, we get that Szabados’s
conjecture holds for not fully periodic configurations with $\mathbb{Z}$-order
$2$.

To conclude this section, we will state Proposition 2.9, which will be
essential in both cases $R=\mathbb{Z}$ and $R=\mathbb{Z}_{p}$. The case where
$R=\mathbb{Z}$ is an immediate consequence of Corollary 24 of [9]. To provide
a proof for the case where $R=\mathbb{Z}_{p}$ we need first to prove the
following lemma:

######  Lemma 2.8 (Kari and Szabados [8]).

Let $\theta\in R[[X^{\pm 1}]]$ be a periodic configuration of period
$u\in\mathbb{Z}^{2}$. Then, for a vector $v\in\mathbb{Z}^{2}$ linearly
independent to $u$ over $\mathbb{R}^{2}$, there exists a periodic
configuration $\vartheta\in R[[X^{\pm 1}]]$ of period $u$ such that
$(X^{v}-1)\vartheta=\theta$.

###### Proof.

Recall that $(X^{v}-1)\vartheta=\theta$ means that
$\vartheta_{g-v}-\vartheta_{g}=\theta_{g}$ for all $g\in\mathbb{Z}^{2}$. Let
$\boldsymbol{\ell}_{0}\subset\mathbb{R}^{2}$ be an oriented line through the
origin parallel to the vector $v$. For
$g_{0}\in\boldsymbol{\ell}_{0}\cap\mathbb{Z}^{2}$, let
$g_{1},\ldots,g_{l}\in\boldsymbol{\ell}_{0}\cap\mathbb{Z}^{2}$ be the points
of $\mathbb{Z}^{2}$ between $g_{0}$ and $g_{0}+v$, but different from $g_{0}$
and $g_{0}+v$. For each $0\leq i\leq l$, we define
$\vartheta_{g_{i}+tv}:=\sum_{k=1}^{|t|}\theta_{g_{i}-(k-1)v}$ for $t<0$,
$\vartheta_{g_{i}}:=0$ and
$\vartheta_{g_{i}+tv}:=-\sum_{k=1}^{t}\theta_{g_{i}+kv}$ for $t>0$.

Let $\boldsymbol{\ell}_{1},\ldots,\boldsymbol{\ell}_{n}\subset\mathbb{R}^{2}$
be the oriented lines parallels to $v$ between $\boldsymbol{\ell}_{0}$ and
$\boldsymbol{\ell}_{0}+u$, but different from $\boldsymbol{\ell}_{0}$ and
$\boldsymbol{\ell}_{0}+u$, that contain a point of $\mathbb{Z}^{2}$.
Proceeding as before, we define $\vartheta_{g}$ for all $g\in
S:=(\boldsymbol{\ell}_{0}\cup\boldsymbol{\ell}_{1}\cup\cdots\cup\boldsymbol{\ell}_{n})\cap\mathbb{Z}^{2}$.
For any $g\in\mathbb{Z}^{2}\backslash S$, we define
$\vartheta_{g}=\vartheta_{g+tu}$, where $t\in\mathbb{Z}$ is the unique integer
such that $g+tu\in S$. By construction, $\vartheta$ is periodic of period $u$
and, since $\theta$ is periodic of period $u$, $\vartheta$ satisfies all
required conditions. ∎

######  Proposition 2.9 (Kari and Szabados [9]).

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with $\mathcal{A}\subset R$, be a
non-periodic configuration. Suppose $\eta=\eta_{1}+\cdots+\eta_{m}$ is a
$R$-minimal periodic decomposition, $h_{i}\in\mathbb{Z}^{2}$ is a period for
$\eta_{i}$, with $1\leq i\leq m$, and
$\varphi(X)=(X^{h_{1}}-1)\cdots(X^{h_{m}}-1)$. If
$\psi\in\operatorname{Ann}_{R}(\eta)$, then, for every edge $w\in
E(\mathcal{S}_{\varphi})$, there exists an edge $w^{\prime}\in
E(\mathcal{S}_{\psi})$ parallel to $w$.

###### Proof.

Let $\psi\in\operatorname{Ann}_{R}(\eta)$ and suppose, by contradiction, that
there exists $w\in E(\mathcal{S}_{\varphi})$ that is not parallel to any edge
of $\mathcal{S}_{\psi}$. According to Remark 2.3, $w$ is either parallel or
antiparallel to some vector $h_{\iota}$, with $1\leq\iota\leq m$. Renaming
$\eta_{1},\ldots,\eta_{m}$ if necessary, we may assume that $\iota=1$. Let
$\boldsymbol{\ell}\subset\mathbb{R}^{2}$ be the oriented line through the
origin parallel to $w$. In particular,
$\mathcal{S}_{\psi}\cap\boldsymbol{\ell}_{\mathcal{S}_{\psi}}$ is a vertex of
$\mathcal{S}_{\psi}$. Since $\mathcal{S}_{\psi}$ is an $\eta$-generating set,
Lemma 2.2 implies that $\boldsymbol{\ell}\not\in\operatorname{ONED}(\eta)$.
Hence, by Proposition 2.7 it follows that $m\geq 3$. Thus, let

$\sigma(X):=(X^{h_{1}}-1)(X^{h_{2}}-1)\ \ \text{and}\ \
\varphi_{3}(X):=(X^{h_{3}}-1)\cdots(X^{h_{m}}-1).$

Note that $\varphi_{3}\eta=\varphi_{3}\eta_{1}+\varphi_{3}\eta_{2}$ and
$\sigma\in\operatorname{Ann}_{R}(\varphi_{3}\eta)$. Moreover,
$\mathcal{S}_{\sigma}$ has an edge $w^{\prime}\in E(\mathcal{S}_{\sigma})$
parallel to $w$. Since

$\psi(\varphi_{3}\eta)=\varphi_{3}(\psi\eta)=0,$

i.e., $\psi\in\operatorname{Ann}_{R}(\varphi_{3}\eta)$, then, as before, Lemma
2.2 implies that
$\boldsymbol{\ell}\not\in\operatorname{ONED}(\varphi_{3}\eta)$. Hence, being
$\boldsymbol{\ell}$ parallel to $w$ and so to $w^{\prime}$, by Proposition 2.7
results that $\varphi_{3}\eta$ is periodic.

We claim that $\varphi_{3}\eta$ has a period $u\in\mathbb{Z}^{2}$ such that
the vectors $u,h_{3},h_{4},\ldots,h_{m}$ are in pairwise distinct directions.
Indeed, if $\varphi_{3}\eta$ is a fully periodic configuration,then, we may
consider, for instance, a vector $u\in\mathbb{Z}^{2}$ parallel to $h_{1}$ or
$h_{2}$. Otherwise, the unique line
$\ell^{\prime}\in\operatorname{NEL}(\varphi_{3}\eta)$ contains any period for
$\varphi_{3}\eta$. Since, for some orientation,
$\boldsymbol{\ell}^{\prime}\in\operatorname{ONED}(\varphi_{3}\eta)$, then,
according to Remark 2.5, $\boldsymbol{\ell}^{\prime}$ is either parallel or
antiparallel to $h_{2}$, which proves the claim.

Let $u\in\mathbb{Z}^{2}$ be a period for $\varphi_{3}\eta$ as in the previous
claim. To conclude the proof, we will contradict the minimality of $m$. We
claim that $\eta$ can be decomposed into a sum of $m-1$ periodic
configurations. Indeed, by Lemma 2.8 there exists a periodic configuration
$\Theta_{2}\in R[[X^{\pm 1}]]$, with $u$ a period for $\Theta_{2}$, such that
$(X^{h_{3}}-1)\Theta_{2}=\varphi_{3}\eta$. For each $3\leq i\leq m$, let

$\varphi_{n}(X):=\prod_{i=n}^{m}(X^{h_{i}}-1).$

For $\Theta_{3}:=\varphi_{4}\eta-\Theta_{2}$, it follows that
$\varphi_{4}\eta=\Theta_{2}+\Theta_{3}$ and

$(X^{h_{3}}-1)\Theta_{3}=\varphi_{3}\eta-(X^{h_{3}}-1)\Theta_{2}=0.$

Suppose we have constructed periodic configurations
$\theta_{2},\ldots,\theta_{m-1}\in R[[X^{\pm 1}]]$, with $u$ a period for
$\theta_{2}$ and, for each $3\leq i\leq m-1$, $h_{i}$ a period for
$\theta_{i}$, such that

$(X^{m}-1)\eta=\theta_{2}+\cdots+\theta_{m-1}.$

Thanks to Lemma 2.8, there exist periodic configurations
$\varphi_{2},\ldots,\varphi_{m-1}\in R[[X^{\pm 1}]]$, with $u$ a period for
$\varphi_{2}$ and, for each $3\leq i\leq m-1$, $h_{i}$ a period for
$\varphi_{i}$, such that $(X^{m}-1)\varphi_{i}=\theta_{i}$. For
$\varphi_{m}:=\eta-\varphi_{2}-\cdots-\varphi_{m-1}$, it follows that
$\eta=\varphi_{2}+\cdots+\varphi_{m}$ and

$(X^{m}-1)\varphi_{m}=(X^{m}-1)\eta-(X^{m}-1)\varphi_{2}-\cdots-(X^{m}-1)\varphi_{m-1}=0,$

which proves the claim and contradicts the minimality of $m$. ∎

##  3\. Proof of main results

######  Lemma 3.1.

Let $\vartheta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}_{p}$, and suppose
$\vartheta=\vartheta_{1}+\cdots+\vartheta_{m}$ is a $\mathbb{Z}_{p}$-pe-riodic
decomposition and $h_{i}\in\mathbb{Z}^{2}$ is a period for $\vartheta_{i}$,
with $1\leq i\leq m$. If $\vartheta$ is non-periodic, suppose in addition that
the vectors $h_{1},\ldots,h_{m}$ are in pairwise distinct directions. If
$\vartheta=\vartheta^{\prime}_{1}+\cdots+\vartheta^{\prime}_{n}$, with $n<m$,
is a $\mathbb{Z}_{p}$-minimal periodic decomposition, then the following
conditions hold.

  1. (i)

There exists a sequence $1\leq i_{1}<\cdots<i_{n}\leq m$ where, for each
$1\leq j\leq n$, there exists $t_{j}\in\mathbb{Z}$ such that
$u^{\prime}_{j}=t_{j}h_{i_{j}}$ is a period for $\vartheta^{\prime}_{j}$;

  2. (ii)

If $\vartheta$ is fully periodic, then $\vartheta=\vartheta^{\prime}_{1}$ and
condition (i) holds for every $1\leq i_{1}\leq m$;

  3. (iii)

For any $1\leq i\leq m$, with $i\neq i_{1},\ldots,i_{n}$, $\vartheta_{i}$ is
fully periodic.

###### Proof.

If $\vartheta$ is periodic of period $u\in\mathbb{Z}^{2}$, but not fully
periodic, then, the unique line $\ell\in\operatorname{NEL}(\vartheta)$
contains $u$. Since, for some orientation,
$\boldsymbol{\ell}\in\operatorname{ONED}(\vartheta)$, then, according to
Remark 2.5, $\boldsymbol{\ell}$ and so $u$ is either parallel or antiparallel
to some vector $h_{i}$, with $1\leq i\leq m$. Thus, for $i_{1}=i$, there exist
$t_{1}\in\mathbb{Z}$ and $s_{1}\in\mathbb{Z}$ such that
$s_{1}u=t_{1}h_{i_{1}}$. We finish this case by setting
$u^{\prime}_{1}=s_{1}u$. If $\vartheta$ is non-periodic, let
$u_{j}\in\mathbb{Z}^{2}$ be a period for $\vartheta^{\prime}_{j}$, with $1\leq
j\leq n$. Since

$(X^{u_{1}}-1)\cdots(X^{u_{n}}-1),(X^{h_{1}}-1)\cdots(X^{h_{m}}-1)\in\operatorname{Ann}_{\mathbb{Z}_{p}}(\vartheta),$

from Proposition 2.9 we get that each vector $u_{j}$ is either parallel or
antiparallel to some vector $h_{i}$. Thus, there exist a sequence $1\leq
i_{1}<\cdots<i_{n}\leq m$ such that, for each $1\leq j\leq n$,
$s_{j}u_{j}=t_{j}h_{i_{j}}$ holds for some $t_{j},s_{j}\in\mathbb{Z}$. We
establish this case by setting $u^{\prime}_{j}=s_{j}u_{j}$ for every $1\leq
j\leq n$.

If $\vartheta$ is fully periodic, then $\vartheta_{1}^{\prime}$ is fully
periodic. Hence, for any $1\leq i_{1}\leq m$, there exists
$t_{1}\in\mathbb{Z}$ such that $u^{\prime}_{1}=t_{1}h_{i_{1}}$ is a period for
$\vartheta_{1}^{\prime}$, which proves conditions (i) and (ii).

To approach condition (iii), consider $A=\\{1\leq i\leq m:i\neq
i_{1},\ldots,i_{n}\\}$ and write $\theta=\sum_{i\in A}\vartheta_{i}$. Note
that

$0=(X^{u^{\prime}_{1}}-1)\cdots(X^{u^{\prime}_{n}}-1)\vartheta=(X^{t_{1}h_{i_{1}}}-1)\cdots(X^{t_{n}h_{i_{n}}}-1)\theta,$

i.e.,

$\varphi(X):=(X^{t_{1}h_{i_{1}}}-1)\cdots(X^{t_{n}h_{i_{n}}}-1)\in\operatorname{Ann}_{\mathbb{Z}_{p}}(\theta).$

Clearly, $\psi(X):=\prod_{i\in
A}(X^{h_{i}}-1)\in\operatorname{Ann}_{\mathbb{Z}_{p}}(\theta)$. By Lemma 2.2,
if $\boldsymbol{\ell}^{\prime}\in\operatorname{ONED}(\theta)$, then
$\boldsymbol{\ell}^{\prime}$ must be parallel to an edge of
$\mathcal{S}_{\varphi}$ and parallel to an edge of $\mathcal{S}_{\psi}$. Since
the vectors $h_{1},\ldots,h_{m}$ are in pairwise distinct directions,
$\mathcal{S}_{\varphi}$ and $\mathcal{S}_{\psi}$ does not have parallel edges,
which means that $\operatorname{ONED}(\theta)=\emptyset$. Hence,
$\operatorname{NEL}(\theta)=\emptyset$ and, by Theorem 1.1, we get that
$\theta$ is fully periodic. Let $l_{1},\ldots,l_{k}$, with $k=|A|$, be an
enumeration of the elements of $A$. If $k=1$, there is nothing to argue.
Otherwise, as $\theta$ is fully periodic, then $\theta-\vartheta_{l_{1}}$ is
periodic with period parallel to $h_{l_{1}}$. Let
$u^{\prime\prime}_{1}=t_{l_{1}}h_{l_{1}}$, with $t_{l_{1}}\in\mathbb{Z}$, be a
period for $\theta-\vartheta_{l_{1}}$. Note that

$(X^{u^{\prime\prime}_{1}}-1),\psi_{1}(X):=\prod_{\begin{subarray}{c}i\in A\\\
i\neq
l_{1}\end{subarray}}(X^{h_{i}}-1)\in\operatorname{Ann}_{\mathbb{Z}_{p}}(\theta-\vartheta_{l_{1}}).$

By Lemma 2.2, if
$\boldsymbol{\ell}^{\prime}\in\operatorname{ONED}(\theta-\vartheta_{l_{1}})$,
then we must have $u^{\prime\prime}_{1}\in\boldsymbol{\ell}^{\prime}$ and
$\boldsymbol{\ell}^{\prime}$ must be parallel to an edge of
$\mathcal{S}_{\psi_{1}}$. So as before,
$\operatorname{NEL}(\theta-\vartheta_{l_{1}})=\emptyset$ and, by Theorem 1.1,
we get that $\theta-\vartheta_{l_{1}}$ is fully periodic. Proceeding this way,
suppose we have showed that

$\theta-\vartheta_{l_{1}}-\cdots-\vartheta_{l_{k-2}}=\vartheta_{l_{k-1}}+\vartheta_{l_{k}}$

is fully periodic. Hence,
$\theta-\vartheta_{l_{1}}-\cdots-\vartheta_{l_{k-1}}=\vartheta_{l_{k}}$ is
periodic with period parallel to $h_{l_{k-1}}$. Being $\vartheta_{l_{k}}$
periodic of period $h_{l_{k}}$, we get that $\vartheta_{l_{k}}$ is fully
periodic. Therefore, as $l_{1},\ldots,l_{k}$ is an arbitrary enumeration of
the elements of $A$, then, for any $1\leq i\leq m$, with $i\neq
i_{1},\ldots,i_{n}$, $\vartheta_{i}$ is fully periodic, which establishes
condition (iii) and proves the lemma. ∎

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}_{+}$, and suppose
$\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}$-minimal periodic
decomposition. For a prime number $p\in\mathbb{N}$, we may consider the
$\mathbb{Z}_{p}$-perio- dic decomposition
$\overline{\eta}=\overline{\eta}_{1}+\cdots+\overline{\eta}_{m}$, where the
bar denotes the congruence modulo $p$. If $p$ is large enough so that
$\mathcal{A}\subset[[p]]$, then $\eta$ and $\overline{\eta}$ are the same
configurations, i.e., the bar does not change $\eta$. However, each
configuration $\overline{\eta}_{i}$ is defined on the finite alphabet
$\mathbb{Z}_{p}$. Furthermore, if $\psi(X)=\sum_{i=1}^{n}a_{i}X^{u_{i}}$, with
$a_{i}\in\mathbb{Z}$ and $u_{i}\in\mathbb{Z}^{2}$, annihilates $\eta$, then by
(1.1) we get that

$\overline{a_{1}}\cdot\overline{\eta}_{g-u_{1}}+\cdots+\overline{a_{n}}\cdot\overline{\eta}_{g-u_{n}}=0\quad\forall
g\in\mathbb{Z}^{2},$

that is,

$\overline{\psi}(X)=\sum_{i=1}^{n}\overline{a_{i}}X^{u_{i}}\in\operatorname{Ann}_{\mathbb{Z}_{p}}(\overline{\eta}).$

###  3.1. Proof of Theorem 1.6

If $m=1$, the result holds trivially. Otherwise, for each $1\leq i\leq m$, let
$h_{i}\in\mathbb{Z}^{2}$ be a period for $\eta_{i}$ and let

$\varphi_{i}(X)=\prod_{\begin{subarray}{c}k=1\\\ k\neq
i\end{subarray}}^{m}(X^{h_{k}}-1).$

Note that each configuration $\varphi_{i}\eta=\varphi_{i}\eta_{i}$ is defined
on a finite alphabet. Thus, for each $1\leq i\leq m$, let $N_{i}\in\mathbb{N}$
be such that

$(\varphi_{i}\eta+N_{i}11)_{g}\in\mathbb{Z}_{+}\quad\forall\
g\in\mathbb{Z}^{2},$

where $11_{g}=1$ for all $g\in\mathbb{Z}^{2}$. Let $p\in\mathbb{N}$, with
$\mathcal{A}\subset[[p]]$, be a prime number large enough so that, for any
$1\leq i\leq m$,

$\\{(\varphi_{i}\eta_{i}+N_{i}11)_{g}:g\in\mathbb{Z}^{2}\\}\subset[[p]].$

We claim that, for each $1\leq i\leq m$, $\overline{\eta}_{i}$ is not fully
periodic. Indeed, suppose, by contradiction, that $\overline{\eta}_{i}$ is
fully periodic. Since

$\overline{\varphi_{i}\eta+N_{i}11}=\overline{\varphi_{i}\eta_{i}+N_{i}11}=\varphi_{i}\overline{\eta}_{i}+\overline{N_{i}11},$

where on the right side $\varphi_{i}\in\mathbb{Z}_{p}[X^{\pm 1}]$, then
$\overline{\varphi_{i}\eta+N_{i}11}$ is fully periodic. However, as

$\\{(\varphi_{i}\eta_{i}+N_{i}11)_{g}:g\in\mathbb{Z}^{2}\\}\subset[[p]],$

the bar does not change $\varphi_{i}\eta+N_{i}11$, which means that
$\varphi_{i}\eta+N_{i}11$ and so $\varphi_{i}\eta$ is fully periodic. Consider
$1\leq j\leq m$, with $j\neq i$, and let $h^{\prime}_{j}=t_{j}h_{j}$, with
$t_{j}\in\mathbb{Z}$, be a period for $\varphi_{i}\eta$. Then

$(X^{h^{\prime}_{j}}-1)\varphi_{i}\eta=0,$

i.e.,
$\psi(X):=(X^{h^{\prime}_{j}}-1)\varphi_{i}(X)\in\operatorname{Ann}_{\mathbb{Z}}(\eta)$.
Since $\mathcal{S}_{\psi}$ does not have any edge parallel to $h_{i}$, by
Proposition 2.9 we reach a contradiction, which establishes the claim.

We claim that $\overline{\eta}=\overline{\eta}_{1}+\cdots+\overline{\eta}_{m}$
is a $\mathbb{Z}_{p}$-minimal periodic decomposition. Indeed, if
$\overline{\eta}=\eta^{\prime}_{1}+\cdots+\eta^{\prime}_{n}$, with $n<m$, is a
$\mathbb{Z}_{p}$-minimal periodic decomposition, then, according to Lemma 3.1,
there exists a sequence $1\leq i_{1}<\cdots<i_{n}\leq m$ such that, for each
$1\leq i\leq m$, with $i\neq i_{1},\ldots,i_{n}$, $\overline{\eta}_{i}$ is
fully periodic, which due to the previous claim is a contradiction. $\Box$

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$ be a configuration and suppose
$\mathcal{U}\subset\mathbb{Z}^{2}$ is a non-empty, convex set. We say that
$\eta{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{U}$}$ is _periodic_ if there
exists a vector $h\in(\mathbb{Z}^{2})^{*}$, called _period of
$\eta{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{U}$}$_,such that

$\eta_{g-h}=\eta_{g}\quad\forall g\in\mathcal{U}\cap(\mathcal{U}+h).$

If $\eta{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{U}$}$ has two periods
linearly independents over $\mathbb{R}^{2}$, we say that
$\eta{\mathbin{|}}\raise-1.72218pt\hbox{$\mathcal{U}$}$ is _fully peri- odic_.

######  Theorem 3.2.

Let $\eta\in\mathcal{A}^{\mathbb{Z}^{2}}$, with
$\mathcal{A}\subset\mathbb{Z}_{p}$, be a not fully periodic configuration and
suppose $\eta=\eta_{1}+\cdots+\eta_{m}$ is a $\mathbb{Z}_{p}$-minimal periodic
decomposition. If for any configuration $x\in\overline{Orb\,(\eta)}$ the
subshift $\overline{Orb\,(x)}$ has a periodic configuration, then, for each
$1\leq i\leq m$, a line $\ell\subset\mathbb{R}^{2}$ contains a period for
$\eta_{i}$ if and only if $\ell\in\operatorname{NEL}(\eta)$.

###### Proof.

The proof will be done by induction on $m$. If $m=1$, the theorem holds
trivially. If $m=2$, the theorem follows by Proposition 2.7. Thus we may
assume $m\geq 3$. Suppose, by induction hypothesis, that Theorem 3.2 holds for
any not fully periodic configuration with $\mathbb{Z}_{p}$-order $n\leq m-1$.

Let $h_{i}\in\mathbb{Z}^{2}$ be a period for $\eta_{i}$, with $1\leq i\leq m$.
Let $\vartheta\in\overline{Orb\,(\eta)}$ be a periodic configuration and
suppose $(g_{n})_{n\in\mathbb{N}}\subset\mathbb{Z}^{2}$ is a sequence such
that

$\displaystyle\lim_{n\to+\infty}T^{g_{n}}\eta=\vartheta.$

By passing to a subsequence, we may assume that, for any $1\leq i\leq m$,

$\displaystyle\lim_{n\to+\infty}T^{g_{n}}\eta_{i}=\vartheta_{i}.$

Since $T^{g_{n}}\eta=T^{g_{n}}\eta_{1}+\cdots+T^{g_{n}}\eta_{m}$, then
$\vartheta=\vartheta_{1}+\cdots+\vartheta_{m}$ is a $\mathbb{Z}_{p}$-periodic
decomposition, where $\vartheta_{i}$ is periodic of period $h_{i}$, with
$1\leq i\leq m$. If we denote $\vartheta=\vartheta^{\prime}_{1}$, then
$\vartheta=\vartheta^{\prime}_{1}$, with $1<m$, is a $\mathbb{Z}_{p}$-minimal
periodic decomposition. Thus, according to Lemma 3.1, there exists
$1\leq\iota_{1}\leq m$ such that, for any $1\leq i\leq m$, with
$i\neq\iota_{1}$, $\vartheta_{i}$ is fully periodic.

Given $1\leq k\leq m$, with $k\neq\iota_{1}$, let $1\leq j\leq m$, with
$j\neq\iota_{1}$, be such that $j\neq k$. Let $u_{j}=t_{j}h_{j}$, with
$t_{j}\in\mathbb{Z}$, be a period for $\vartheta_{k}$ and consider

$R_{l}:=\left\\{tu_{j}+sh_{k}\in\mathbb{Z}^{2}:t,s\in[-l,l]\right\\}\quad(l\in\mathbb{N}).$

For each $l\in\mathbb{N}$, there exists $n_{l}\in\mathbb{N}$ such that, for
any $1\leq i\leq m$, with $i\neq\iota_{1}$,

$(T^{g_{n_{l}}}\eta_{i}){\mathbin{|}}\raise-1.72218pt\hbox{$R_{l}$}=\vartheta_{i}{\mathbin{|}}\raise-1.72218pt\hbox{$R_{l}$}.$

Let $\ell_{j},\ell_{k}\subset\mathbb{R}^{2}$ be the lines through the origin
such that $u_{j}\in\ell_{j}$ and $h_{k}\in\ell_{k}$ and consider the strips

$S_{\ell_{j}}(l):=\\{g+tu_{j}\in\mathbb{Z}^{2}:g\in R_{l},\ t\in\mathbb{Z}\\}$

and

$S_{\ell_{k}}(l):=\\{g+th_{k}\in\mathbb{Z}^{2}:g\in R_{l},\
t\in\mathbb{Z}\\}.$

Note that
$(T^{g_{n_{l}}}\eta_{k}){\mathbin{|}}\raise-1.72218pt\hbox{$S_{\ell_{k}}(l)$}$
is fully periodic of periods $u_{j}$ and $h_{k}$. Being $\eta_{k}$ not fully
periodic, we may consider the largest convex set
$L_{\ell_{k}}(l)\subset\mathbb{Z}^{2}$, with $S_{\ell_{k}}(l)\subset
L_{\ell_{k}}(l)$, such that

  1. (i)

$(T^{g_{n_{l}}}\eta_{k}){\mathbin{|}}\raise-1.72218pt\hbox{$L_{\ell_{k}}(l)$}$
is fully periodic of periods $u_{j}$ and $h_{k}$;

  2. (ii)

$g\in L_{\ell_{k}}(l)$ if and only if $(g+\ell_{k})\cap\mathbb{Z}^{2}\subset
L_{\ell_{k}}(l)$.

Of course, $L_{\ell_{k}}(l)$ is either a strip or a half plane, which implies
that $L_{\ell_{k}}(l)$ has at least one edge $w_{\ell_{k}}(l)\in
E(L_{\ell_{k}}(l))$. Let $s_{l}\in\mathbb{Z}$ be such that $-s_{l}u_{j}$ is
closest as possible from $w_{\ell_{k}}(l)$ (see Figure 1).

$w_{\ell_{k}}(l)$
---
$L_{\ell_{k}}(l)$
---
$S_{\ell_{j}}(l)$
---
$(0,0)$
---
$S_{\ell_{k}}(l)$
---
$-s_{l}u_{j}$
---
$R_{l}$
---
Figure 1. The strips $S_{\ell_{k}}(l)$ and $S_{\ell_{j}}(l)$ and the set
$L_{\ell_{k}}(l)$.

By passing to a subsequence, we may assume that

$\lim_{l\to+\infty}T^{g_{n_{l}}+s_{l}u_{j}}\eta=\varTheta$

and, for each $1\leq i\leq m$,

$\lim_{l\to+\infty}T^{g_{n_{l}}+s_{l}u_{j}}\eta_{i}=\varTheta_{i}.$

Since
$T^{g_{n_{l}}+s_{l}u_{j}}\eta=T^{g_{n_{l}}+s_{l}u_{j}}\eta_{1}+\cdots+T^{g_{n_{l}}+s_{l}u_{j}}\eta_{m}$,
then $\varTheta=\varTheta_{1}+\cdots+\varTheta_{m}$ is a
$\mathbb{Z}_{p}$-periodic decomposition, where $h_{i}$ is a period for
$\varTheta_{i}$, with $1\leq i\leq m$. By construction, $\varTheta_{j}$ is
fully periodic, which implies that $\varTheta$ has $\mathbb{Z}_{p}$-order
lower than $m$. Let
$\varTheta=\varTheta^{\prime}_{1}+\cdots+\varTheta^{\prime}_{n}$, with $n\leq
m-1$, be a $\mathbb{Z}_{p}$-minimal periodic decomposition. Due to Lemma 3.1,
there exists a sequence $1\leq i_{1}<\cdots<i_{n}\leq m$ such that, for each
$1\leq i\ \leq m$, with $i\neq i_{1},\ldots,i_{n}$, $\varTheta_{i}$ is fully
periodic.

######  Claim 3.3.

$k\in\\{i_{1},\ldots,i_{n}\\}$.

Indeed, if $k\neq i_{1},\ldots,i_{n}$, then, by the previous discussion,
$\varTheta_{k}$ is fully periodic. For $r\in\mathbb{N}$ as large as we want,
there exists $l\in\mathbb{N}$, with $l>r$, such that

$(T^{g_{n_{l}}}\eta_{k}){\mathbin{|}}\raise-1.72218pt\hbox{$R_{r}-s_{l}u_{j}$}$

is fully periodic. But, since $L_{\ell_{k}}(l)\cap(R_{r}-s_{l}u_{j})$ can be
as large as we want, by item (i) we get that

$(T^{g_{n_{l}}}\eta_{k}){\mathbin{|}}\raise-1.72218pt\hbox{$L_{\ell_{k}}(l)\cup(S_{\ell_{k}}(r)-s_{l}u_{j})$}$

is fully periodic of periods $u_{j}$ and $h_{k}$, which is a contradiction and
establishes the claim.

Note that $\varTheta$ can not be fully periodic, since, otherwise,
$\varTheta=\varTheta^{\prime}_{1}$ and condition (ii) of Lemma 3.1 allows us
to consider $i_{1}\neq k$, which due to the previous claim is a contradiction.
Thus, since $\varTheta$ has $\mathbb{Z}_{p}$-order $n\leq m-1$ and for any
configuration $x$ $\in\overline{Orb\,(\varTheta)}$ the subshift
$\overline{Orb\,(x)}$ has a periodic configuration, by induction hypothesis
Szabados’s conjecture holds for $\varTheta$.

Let $\ell_{1},\ldots,\ell_{m}\subset\mathbb{R}^{2}$ be the lines through the
origin such that, for each $1\leq i\leq m$, $h_{i}\in\ell_{i}$.

######  Claim 3.4.

$\ell_{1},\ldots,\ell_{m}\in\operatorname{NEL}(\eta)$.

Indeed, since $k\in\\{i_{1},\ldots,i_{n}\\}$, it follows by condition (i) of
Lemma 3.1 that some configuration $\varTheta^{\prime}_{i}$, with $1\leq i\leq
n$, has a period parallel to $h_{k}$. Thus, as Szabados’s conjecture holds for
$\varTheta$, then
$\ell_{k}\in\operatorname{NEL}(\varTheta)\subset\operatorname{NEL}(\eta)$.
Being $1\leq k\leq m$, with $k\neq\iota_{1}$, an arbitrary integer, we
conclude that $\ell_{i}\in\operatorname{NEL}(\eta)$ for every $1\leq i\leq m$,
with $i\neq\iota_{1}$.

If $\vartheta$ is fully periodic, then by repeating the same construction for
$1\leq l_{1}\leq m$, with $l_{1}\neq\iota_{1}$ (see condition (ii) of Lemma
3.1), we get that $\ell_{\iota_{1}}\in\operatorname{NEL}(\eta)$.

If $\vartheta=\vartheta^{\prime}_{1}$ is not fully periodic, the unique line
$\ell^{\prime}\in\operatorname{NEL}(\vartheta^{\prime}_{1})\subset\operatorname{NEL}(\eta)$
contains any period for $\vartheta^{\prime}_{1}$. Thanks to condition (i) of
Lemma 3.1, we see that such a period is either parallel or antiparallel to
$h_{\iota_{1}}$, which implies that $\ell^{\prime}=\ell_{\iota_{1}}$ and
proves the claim.

Therefore, the inductive step is done, which proves Theorem 3.2. ∎

###  3.2. Proof of Theorem 1.7

Initially, changing the alphabet if necessary, we may assume that
$\mathcal{A}\subset\mathbb{Z}_{+}$. Thanks to Theorem 1.6, there exist a prime
$p\in\mathbb{N}$, with $\mathcal{A}\subset[[p]]$, such that
$\overline{\eta}=\overline{\eta}_{1}+\cdots+\overline{\eta}_{m}$ is a
$\mathbb{Z}_{p}$-minimal periodic decomposition. Since
$\ell\in\operatorname{NEL}(\eta)$ if and only if
$\ell\in\operatorname{NEL}(\overline{\eta})$, the result follows by Theorem
3.2. $\Box$.

## References

  * [1] Boyle, M., Lind, D.: Expansive Subdynamics. Trans. Amer. Math. Soc. 349(1), 55-102 (1997).
  * [2] Colle, C. F.: On Periodic Decompositions, One-sided Nonexpansive Directions and Nivat’s Conjecture. arXiv:1909.08195v4 (2022).
  * [3] Cyr, V., Kra, B.: Nonexpansive $\mathbb{Z}^{2}$-Subdynamics and Nivat’s Conjecture. Trans. Amer. Math. Soc. 367, 6487-6537 (2015).
  * [4] Franks, J, Kra, B.: Polygonal $Z^{2}$-subshifts. Proc. Lond. Math. Soc. 121, 252-286 (2020).
  * [5] Kari, J., Moutot, E.: Nivat’s Conjecture and Pattern Complexity in Algebraic Subshifts. Theor. Comput. Sci. 777, 379-386 (2019).
  * [6] Kari, J., Moutot, E.: Decidability and Periodicity of Low Complexity Tilings. 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 154, 14:1–14:12 (2020).
  * [7] Kari, J., Moutot, E.: Decidability and Periodicity of Low Complexity Tilings. Theory of Computing Systems , https://doi.org/10.1007/s00224-021-10063-8 (2021).
  * [8] Kari, J., Szabados, M.: An Algebraic Geometric Approach to Nivat’s Conjecture. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, Proceedings, Part II, 273–285 (2015).
  * [9] Kari, J., Szabados, M.: An Algebraic Geometric Approach to Nivat’s Conjecture. Information and Computation 271, 104-481 (2020).
  * [10] Nivat, M.: Invited Talk at ICALP. Bologna (1997).
  * [11] Szabados, M.: Nivat’s Conjecture holds for Sums of two Periodic Configurations. SOFSEM 2018: Theory and Practice of Computer Science, 539-551 (2018).
  * [12] Szabados, M.:. An algebraic approach to Nivat’s Conjecture. Ph.D. thesis, University of Turku (2018).