# Finite rotations on Z2: A hierarchical framework for bijectivity analysis

Nicolas Passat, Phuc Ngo, Yukiko Kenmochi

<figure><img src="image_1.png" /></figure>

## To cite this version:

Nicolas Passat, Phuc Ngo, Yukiko Kenmochi. Finite rotations on Z2: A hierarchical framework for bijectivity analysis. Journal of Mathematical Imaging and Vision, 2025, 67 (3), pp.35. 10.1007/s10851-025-01233-1. hal-04945727

HAL Id: hal-04945727

https://hal.science/hal-04945727v1

Submitted on 15 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Finite Rotations on $Z^2$: A Hierarchical Framework for Bijectivity Analysis

Nicolas Passat · Phuc Ngo · Yukiko Kenmochi

Received: date / Accepted: date

**Abstract** In Euclidean spaces ($\mathbb{R}^d$, $d \ge 2$), rotations preserve distances and angles; they are also bijective. These important properties are no longer guaranteed when rotations are considered in discrete spaces. This is especially the case in the Cartesian spaces ($Z^d$, $d \ge 2$), where rotations are however crucial for various applications, from image processing to computer graphics. In this article, we deal with the issue of bijectivity of discrete rotations in the 2-dimensional case ($Z^2$). We contribute to the state of the art from two points of view. First, we investigate the structure of the (finite and infinite) rotations in $Z^2$, and we shed light on the nature of this combinatorial space, which is analogue to a watershed tree. Second, we focus on the finite rotations, i.e. rotations that act on (finite) Euclidean balls instead of the (infinite) set $Z^2$. Under these hypotheses, we investigate the bijective rotations either as the restrictions of bijective rotations on $Z^2$, or as injective rotations on the Euclidean balls (thus bijective from their domain to their image). We provide two algorithmic schemes for building the combinatorial space of these finite rotations. Codes are freely available at the following url: https://github.com/ngophuc/DiscreteRotationSpace

**Keywords** Finite rotations · Cartesian grid · Bijectivity · Algorithmics · Hierarchical models

## 1 Introduction

Rotations are basic, yet fundamental transformations in geometry. In the fields of image analysis, geometry processing or computer graphics, rotations are required to build higher level image / object transformations. In $\mathbb{R}^d$ ($d \ge 2$), rotations are both isometries (i.e. they preserve lengths) and conformal transformations (i.e. they preserve angles). They are also homeomorphic, and a fortiori bijective, transformations. When defining some analogues of rotations in discrete spaces built as tesselations of $\mathbb{R}^d$, these properties are no longer guaranteed. This is especially true when we consider $Z^d$ as a discrete model of $\mathbb{R}^d$ [15, 17].

Among the above properties, bijectivity is crucial for various reasons. First, it is mandatory for ensuring that a transformation is lossless with regards to the handled images / objects. This is important for instance in terms of reversibility or of composition of transformations. Second, it is a necessary condition for topology preservation. On the one hand, non-surjectivity may lead to the alteration of the topological content of the image (e.g. a non-surjective rotation may lead to vanishing one-point connected components [25]). On the other hand, non-injectivity may lead to conflicting configurations that result in an ill-defined transformed image / object [27].

Rotations on $Z^d$, or related spaces, have been studied over the last decades (Sect. 2). The issue of bijectivity remains, however, not fully tackled. In this article, we contribute to the state of the art of bijective rotations in $Z^2$. Our global objective is twofold:

- Proposing algorithmic schemes for building the combinatorial (hierarchical) space of finite discrete rotations.

- Investigating the notion(s) of bijectivity in the case of finite discrete rotations and being able to build them.

<footnote>N. Passat (corresponding author)
Université de Reims Champagne-Ardenne, CRESTIC, Reims, France
E-mail: nicolas.passat@univ-reims.fr</footnote>

<footnote>P. Ngo
Université de Lorraine, CNRS, LORIA, 54000, Nancy, France
E-mail: hoai-diem-phuc.ngo@loria.fr</footnote>

<footnote>Y. Kenmochi
Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, F-14050
Caen, France
E-mail: yukiko.kenmochi@unicaen.fr</footnote>
By contrast with other related transformations (e.g. the space
of the discrete rigid motions that presents a size $O(n^{9/2})$ [21]
with respect to the number of points *n* of the processed sub-
set of $\mathbb{Z}^2$) the space of the discrete rotations presents a rel-
atively low size, namely $O(n^{3/2})$ [1]. Building—and actually
handling—the combinatorial space<fnref n="1" /> of these transformations
is then tractable. In addition, this space has a simple struc-
ture. Indeed, it is organized as a morphological (partition)
tree [19]. Based on these favorable properties, we then build
upon algorithmics on such trees to propose some efficient
strategies for the construction of the space of discrete rota-
tions.

This article is an extended and improved version of the
conference paper [30]. By comparison with [30], it provides:

- a theoretical discussion about the tree structure of the combinatorial space of the discrete rotations, both finite and infinite;

- two algorithms with complete and formal descriptions, time cost analysis and bijectivity handling paradigms;

- a C++ code of these two algorithms.

The article is organized as follows. In Sect. 2, we recall
related works dedicated to discrete rotations, in particular,
with respect to their bijective properties. In Sect. 3, we pro-
vide a few comments to improve the readability of the arti-
cle. In Sect. 4, we recall basic notions on rotations in $\mathbb{R}^2$ and
in $\mathbb{Z}^2$. In Sect. 5, we focus on the notion of finite discrete
rotations, defined on Euclidean balls intersected with $\mathbb{Z}^2$. In
Sect. 6, we introduce the two notions of bijectivity that we
will investigate for the finite discrete rotations. In Sect. 7,
we recall basic notions on (morphological) trees, that will
be useful for the modeling of the combinatorial space of the
(finite) discrete rotations and the construction of this space.
In Sect. 8, we characterize the watershed tree structure of
the combinatorial space of the discrete rotations. In Sect. 9,
we propose a bottom-up strategy for building the trees of
the combinatorial spaces of the (bijective) discrete rotations.
In Sect. 10, we propose an alternative top-down strategy for
building these trees. In Sect. 11, we present experimental re-
sults related to these construction strategies. In Sect. 12, we
provide concluding remarks. Proofs of properties are given
in Appendix A. The proofs of the propositions are given di-
rectly in the core of the article. They are generally proposed
as discussions preceding the propositions.

## 2 Related works

When we apply geometric transformations to digital images
or subsets of $\mathbb{Z}^d$, we usually start by performing a geomet-
ric transformation of points of $\mathbb{Z}^d$ and then interpolate from
the values of those transformed points to find the values on
the new grid points. Here, nearest neighbor interpolation,
one of the simplest methods, is considered as our interest
is studying bijection of such transfomations. Various defini-
tions of such pixelwise geometric transformations on $\mathbb{Z}^d$ or
its subsets have been investigated over the last decades. In
this context, rotations have received a specific attention, ei-
ther standalone [1–3, 5, 7–10, 14, 26–28, 31, 34, 36–38], com-
posed with scalings [13] or, more frequently, with transla-
tions thus leading to rigid motions [20–25, 29, 32].

Focusing on the only rotations, various issues were dealt
with: describing their combinatorial structure with respect
to $\mathbb{R}^d$ versus $\mathbb{Z}^d$ [1, 5, 26, 36, 37], ensuring their transitivity
[28], or guaranteeing their bijectivity [2, 3, 7–10, 14, 27, 31,
34] in $\mathbb{Z}^d$. These are non-trivial questions, and their difficulty
increases with the dimension of the Cartesian grid. Indeed,
most of these works deal with $\mathbb{Z}^2$ [2, 3, 5, 8, 9, 14, 27, 28, 34],
fewer with $\mathbb{Z}^3$ [7, 10, 31, 37, 38].

Early in the study of discrete rotations, efforts were gea-
red towards understanding under which hypotheses discrete
rotations could be bijective. In [14], a sufficient condition
was proposed for bijectivity of discrete rotations on $\mathbb{Z}^2$ in
the case where the rounding digitization paradigm is con-
sidered. In [27,34], a characterization of bijective discrete
rotations on $\mathbb{Z}^2$ was further proposed in that case, whereas
it was proved in [11] that there is no bijective discrete ro-
tation on $\mathbb{Z}^2$ in the specific case where the floor digitization
paradigm is considered. Extensions of these results were in-
vestigated in the hexagonal grid [33] and in $\mathbb{Z}^3$ [7,31], a
similar characterization was obtained for the hexagonal grid
while a certification algorithm [31] and a conjecture [7] are
only available for the 3-dimensional cubical grid. The first is
based on arithmetic, whereas the latter is based on geometric
algebra, in which rotations are represented by compositions
of bijective discrete reflections [7,9].

As there are few rotation angles that induce bijective dis-
crete rotations (see Fig. 5 for the distribution of such rotation
angles), an alternative approximation approach, which gives
a priority to guaranteeing the bijection by relaxing the ex-
act rotation, was developed. In [2] a family of rotations on
$\mathbb{Z}^2$ based on quasi-shears was proposed, also fulfilling bijec-
tivity properties. This paradigm was extended to hexagonal
grids in [4] and 3-dimensional cubical grids in [10]. In a
similar context of prioritizing the bijection, in [3], bijective
rotations were handled via the composition of bijective re-
flections based on the idea of partitioning the plane into dig-
ital lines. Recently, several methods to approximate discrete
rotations with bijective transformations, including the com-

<footnote n="1">¹ This combinatorial space consists of a discrete set of elements that symbollically represent each a discrete rotation, and the links between these elements. Here, these links are related to the fact that either (1) two rotations defined on the same Euclidean ball have their interval of angles adjacent, or (2) two rotations share a same interval of angles and correspond to two successive radii of Euclidean balls defining their domain of application. In practice, this combinatorial space is formalized in the framework of graphs.</footnote>
position of bijective discrete reflections, bijective rotations by circles and bijective rotations through optimal transport were presented with their experimental comparisons [8].

We have so far reviewed the contributions on bijections on the whole set $\mathbb{Z}^d$. However, bijections may also be considered on smaller, and in particular finite subsets of $\mathbb{Z}^d$. An algorithm for verifying the bijectivity of a given rational rigid motion for a finite set of $\mathbb{Z}^2$ was investigated in [32]. An approach, based on combinatorial geometry, which is similar to [27], was considered for this verification, while the structure of the set of all such bijective rational rigid motions for finite sets of $\mathbb{Z}^2$ is not yet explored.

### 3 Preliminaries

We first provide preliminary elements (notations, remarks) useful for the reader in the next sections.

**Continuous and discrete intervals** We consider two different notations for intervals. If $\mathcal{X}$ is a continuous set (typically $\mathbb{R}$) and $a \le b$ two elements of $\mathcal{X}$, we set $[a, b] = \{x \in \mathcal{X} | a \le x \le b\}$. If $a$ (resp. $b$) is excluded from this interval, we replace $"[$$ (resp. $"]$) by $"($ (resp. $")$). If $\mathcal{X}$ is a discrete set and $a \le b$ two elements of $\mathcal{X}$, we set

$$ \llbracket a, b \rrbracket = \{x \in \mathcal{X} | a \le x \le b\} \quad (1) $$

**The set of square roots of integers** In this study, we consider values in the continuous set $\mathbb{R}$ and in the discrete set $\mathbb{N}$, but also values of the discrete set composed by the $\sqrt{n}$ for $n \in \mathbb{N}$. In particular, we use the following notation

$$ \sqrt{\mathbb{N}} = \{\sqrt{n} | n \in \mathbb{N}\} \quad (2) $$

The notation of discrete interval (Eq. (1)) is used for both $\mathbb{Z}$ and $\sqrt{\mathbb{N}}$. In particular, for elements $a \le b$, the interval $\llbracket a, b \rrbracket$ is defined on $\mathbb{Z}$ (resp. $\sqrt{\mathbb{N}}$) if $a$ and $b$ are elements of $\mathbb{Z}$ (resp. $\sqrt{\mathbb{N}}$).

For two elements $a \le b$ of $\mathbb{N}$, the intervals $\llbracket a, b \rrbracket \subseteq \mathbb{N}$ and $\llbracket \sqrt{a}, \sqrt{b} \rrbracket \subseteq \sqrt{\mathbb{N}}$ are in bijection by the function $n \mapsto \sqrt{n}$. More generally, this bijection induces an isomorphism between $(\llbracket a, b \rrbracket, \le)$ and $(\llbracket \sqrt{a}, \sqrt{b} \rrbracket, \le)$. It is then convenient to define an analogue in $\sqrt{\mathbb{N}}$ of the $+1$ and $-1$ operations in $\mathbb{N}$. We then introduce the following two notations$^2$, for any $c \in \sqrt{\mathbb{N}}$

$$ c \oplus 1 = \sqrt{c^2 + 1} \quad (3) $$

$$ c \ominus 1 = \sqrt{c^2 - 1} \quad (\text{with } c \neq 0) \quad (4) $$

<table><caption>**Table 1** Correspondence between the main distinct notations.</caption><thead><tr><th>Current notations</th><th></th><th>Notations in [30]</th><th></th></tr></thead><tbody><tr><td>$\mathcal{S}_{\bullet}^{\rho}$</td><td>Eq. (27)</td><td>$\mathcal{H}_{\bullet}^{\rho}$</td><td>Eq. (9)</td></tr><tr><td>$\mathcal{S}_{\bullet \to \bullet}^{\rho}$</td><td>Eq. (28)</td><td>$\mathcal{H}_{\bullet \to \bullet}^{\rho}$</td><td>Eq. (10)</td></tr><tr><td>$\mathcal{S}_{\bullet \to \bullet}^{\rho}$</td><td>Eq. (29)</td><td>$\mathcal{H}_{\bullet \to \bullet}^{\rho}$ or $\mathcal{S}^{\rho}$</td><td>Eq. (11)</td></tr><tr><td>$\mathfrak{B}_{\bullet \to \bullet}^{\rho}$</td><td>Eq. (35)</td><td>$\mathfrak{B}^{\rho}$</td><td>Sect. 4.1</td></tr><tr><td>$\mathcal{S}_{\bullet \to \bullet}^{\sqrt{0}, \mu \parallel}$</td><td>Eq. (46)</td><td>$\mathcal{K}^{\mu}$</td><td>Sect. 3.1</td></tr><tr><td>$\mathfrak{Z}(\mathfrak{R}_{\bullet \to \bullet}^{\sqrt{0}, \mu \parallel})$</td><td>Prop. 15</td><td>$\mathfrak{Z}^{\mu}$</td><td>Sect. 3.1</td></tr><tr><td>$\mathfrak{G}^{\mu, (\mathcal{V}^{\mu}, \mathcal{E}^{\mu})}$</td><td>Sect. 8.2</td><td>$\mathcal{G}^{\mu, (\mathcal{V}^{\mu}, \mathcal{E}^{\mu})}$</td><td>Sect. 3.2</td></tr><tr><td>$\mathcal{S}_{\bullet \to \bullet}^{\rho, \beta}$</td><td>Eqs. (76-77), Sect. 9.3</td><td>$\mathfrak{Z}^{\rho}$</td><td>Sect. 4.1</td></tr><tr><td>$\mathcal{S}_{\bullet \to \bullet}^{\rho, \alpha}$</td><td>Eqs. (76-77,86-87)</td><td>$\mathfrak{Y}^{\rho}$</td><td>Sect. 4.2</td></tr></tbody></table>

**Landau notations** Regarding time and space cost analyses, we will use two of the usual Landau notations, $O$ (domination) and $\Theta$ (equivalence). The domination notation $O$ will be used in particular when the equivalence $\Theta$ is not guaranteed.

**Modified notations compared to [30]** In this article, we sometimes adopt some notations that differ from [30]. In order to avoid any ambiguity, Tab. 1 establishes the correspondences between the main differing notations.

### 4 Rotations

#### 4.1 Continuous rotations

We set $\mathbb{U} = [0, 2\pi)$. Let $\theta \in \mathbb{U}$. Let $\mathcal{A}(\theta) \in \mathcal{M}_{2 \times 2}(\mathbb{R})$ be the matrix defined by

$$ \mathcal{A}(\theta) = \begin{pmatrix} \cos \theta - \sin \theta \\ \sin \theta \cos \theta \end{pmatrix} \quad (5) $$

The rotation of center $\mathbf{0} = (0, 0) \in \mathbb{R}^2$ and of angle $\theta$ is the application $\mathcal{R}_{\theta}: \mathbb{R}^2 \to \mathbb{R}^2$ defined, for all $\mathbf{p} \in \mathbb{R}^2$, by

$$ \mathcal{R}_{\theta}(\mathbf{p}) = \mathcal{A}(\theta) \cdot \mathbf{p} \quad (6) $$

i.e. by

$$ \begin{aligned} \mathcal{R}_{\theta} \left( \begin{pmatrix} p_x \\ p_y \end{pmatrix} \right) &= \begin{pmatrix} \cos \theta - \sin \theta \\ \sin \theta \cos \theta \end{pmatrix} \cdot \begin{pmatrix} p_x \\ p_y \end{pmatrix} \\ &= \begin{pmatrix} p_x \cos \theta - p_y \sin \theta \\ p_x \sin \theta + p_y \cos \theta \end{pmatrix} \end{aligned} \quad (7) $$

Such rotation is called a *continuous rotation*. We denote by $\mathfrak{R}_{\mathbb{R}^2}$ the set of all the continuous rotations.

**Remark 1** We consider the rotations of center $\mathbf{0}$. From now on, we will no longer mention their centre of rotation.

<footnote>$^2$ By setting $\sqrt{\mathbb{Z}} = \{\text{sign}(n) \cdot \sqrt{|n|} | n \in \mathbb{Z}\}$, $\sqrt{\mathbb{Z}}$ and $\mathbb{Z}$ are trivially in bijection and $(\mathbb{Z}, \le)$ and $(\sqrt{\mathbb{Z}}, \le)$ are isomorphic lattices. In particular, the triplet $(\mathbb{Z}, +1, -1)$ is associated to an isomorphic triplet $(\sqrt{\mathbb{Z}}, \oplus 1, \ominus 1)$. The definitions of Eqs. (3-4) correspond to the restriction of $\oplus 1$ and $\ominus 1$ to $\sqrt{\mathbb{N}}$. Since $(+1, -1)$ is an adjunction on the lattice $(\mathbb{Z}, \le)$, the couple $(\oplus 1, \ominus 1)$ is also an adjunction on $(\sqrt{\mathbb{Z}}, \le)$. In other words, $\oplus 1$ and $\ominus 1$ are a dilation and an erosion, respectively [12], which justifies the standard use of the notations $\oplus$ and $\ominus$.</footnote>
## 4.2 Hinge angles

Let $\theta \in \mathbb{U}$. Let $\mathcal{R}_{\theta} \in \mathbb{R}^2$ be the continuous rotation of angle $\theta$. Let $\mathbf{p} \in \mathbb{Z}^2$. Let $\mathbf{q} = (q_x, q_y) = \mathcal{R}_{\theta}(\mathbf{p}) \in \mathbb{R}^2$ be the image of $\mathbf{p}$ by the rotation $\mathcal{R}_{\theta}$.

Let us suppose that there exists $k \in \mathbb{Z}$ such that the first (resp. the second) of the following two equations is satisfied

$$p_x \cos \theta - p_y \sin \theta = k + \frac{1}{2} \qquad (8)$$

$$p_x \sin \theta + p_y \cos \theta = k + \frac{1}{2} \qquad (9)$$

Then, we have $q_x = k + \frac{1}{2}$ (resp. $q_y = k + \frac{1}{2}$) and we say that $\mathbf{p}$ is a $x$-critical (resp. $y$-critical) point for $\mathcal{R}_{\theta}$. We say that $\mathbf{p}$ is a critical point for $\mathcal{R}_{\theta}$ if it is a $x$- or a $y$-critical point for $\mathcal{R}_{\theta}$ (Fig. 1).

If $\mathcal{R}_{\theta}$ admits a critical point, then we say that $\theta$ is a hinge angle [28] (induced by $\mathbf{p}$). We denote by $\mathbb{H} \subset \mathbb{U}$ the set of all the hinge angles. Note that $\mathbb{H}$ is dense in $\mathbb{U}$ [26]. We set

$$\mathbb{U} = \mathbb{U} \setminus \mathbb{H} \qquad (10)$$

the set of all the non-hinge angles.

A hinge angle is determined by a triplet $(p_x, p_y, k) \in \mathbb{Z}^3$. However a triplet in $\mathbb{Z}^3$ does not necessarily define a hinge angle. In particular, $(p_x, p_y, k) \in \mathbb{Z}^3$ defines a hinge angle iff

$$\left| k + \frac{1}{2} \right| \le \|(p_x, p_y)\|_2 \qquad (11)$$

We denote by $\mathbb{T} \subset \mathbb{Z}^3$ the set of all the triplets that define hinge angles.

Let $\eta: \mathbb{T} \to \mathbb{H}$ be the surjective application such that for any $\mathbf{t} = (p_x, p_y, k) \in \mathbb{T}$, $\eta(\mathbf{t})$ is the hinge angle induced by $\mathbf{t}$. The application $\eta$ is non-injective. Indeed, many triplets of $\mathbb{T}$ define a same hinge angle of $\mathbb{H}$ (Fig. 1). The following proposition clarifies this many-to-one relation.

**Proposition 2 ([26]** Let $h \in \mathbb{H}$. There exists a prime generator triplet $\hat{\mathbf{t}} = (p_x, p_y, k) \in \mathbb{T}$ (by prime, we mean that $\gcd(p_x, p_y, k) = 1$) such that

$$\eta^{-1}(\{h\}) = \{\mathbf{t} \in \mathbb{T} \mid \eta(\mathbf{t}) = h\} \\ = \{(2n+1) \cdot \hat{\mathbf{t}} + (0, 0, n) \mid n \in \mathbb{Z}\} \qquad (12)$$

For instance, the prime triplet $(1, 0, 0)$ generates the triplets $(3, 0, 1)$, $(5, 0, 2)$, etc. for positive values of $n$ and $(-1, 0, -1)$, $(-3, 0, -2)$, etc. for negative values of $n$. All these triplets lead to a unique hinge angle $h$ (Fig. 1).

**Remark 3** The triplet $\mathbf{t} = (p_x, p_y, k) \in \mathbb{T}$ satisfies Eq. (8) iff the triplet $\mathbf{t}' = (-p_y, p_x, k) \in \mathbb{T}$ satisfies Eq. (9), and we have $\eta(\mathbf{t}) = \eta(\mathbf{t}')$. In other words, it is sufficient to consider only one of these two equations for handling the hinge angles via their triplets.

<figure><img src="image_3.png" /><figcaption>**Fig. 1** Continuous rotation $\mathcal{R}_{\theta}$ with $\theta = \frac{\pi}{6}$. The intersections of the thick black lines correspond to the points of $\mathbb{Z}^2$. The blue point is $\mathbf{0} \in \mathbb{Z}^2$. The blue line is the image by $\mathcal{R}_{\theta}$ of the horizontal black line of equation $y = 0$. The point $(1, 0)$ (in red) is a critical point, since its image $(\frac{\sqrt{3}}{2}, \frac{1}{2})$ (also in red) lies on the line of equation $y = \frac{1}{2}$. Its associated (prime) generator triplet is $(1, 0, 0)$. The points $(-1, 0)$, $(3, 0)$ and $(5, 0)$ (in orange) are also critical points, since their respective images (also in orange) lie on the lines of equation $y = -\frac{1}{2}$, $\frac{3}{2}$ and $\frac{5}{2}$, respectively. Their generator triplets are $(-1, 0, -1)$, $(3, 0, 1)$ and $(5, 0, 2)$, respectively. These four triplets / critical points correspond to the same hinge angle, namely $\theta = \frac{\pi}{6}$, emphasizing the non-injectivity of the application $\eta$.</figcaption></figure>

## 4.3 Discrete rotations

We now consider rotations from $\mathbb{Z}^2$ to $\mathbb{Z}^2$. Let $\theta \in \mathbb{U}$. Let $\mathcal{R}_{\theta} \in \mathbb{R}^2$ be the corresponding continuous rotation (Eqs. (5-7)). Let $\mathbf{p} \in \mathbb{Z}^2$. In general, there is no guarantee that $\mathcal{R}_{\theta}(\mathbf{p}) \in \mathbb{Z}^2$. Indeed, except when $\theta \in \frac{\pi}{2}\mathbb{Z}$, we have $\mathcal{R}_{\theta}(\mathbb{Z}^2) \not\subseteq \mathbb{Z}^2$. To tackle this issue, i.e. to ensure that the result of a rotation applied on $\mathbb{Z}^2$ lies in $\mathbb{Z}^2$, it is common to compose the result of the continuous rotation with a discretization operator, which is generally set as

$$\left| D : \mathbb{R}^2 \to \mathbb{Z}^2 \right. \\ \left. \qquad (p_x, p_y) \mapsto ([p_x], [p_y]) \right. \qquad (13)$$

where $[\cdot]$ is the rounding function on $\mathbb{R}$.

Then, we can define a rotation of angle $\theta$ from $\mathbb{Z}^2$ to $\mathbb{Z}^2$ as a function $R_{\theta}: \mathbb{Z}^2 \to \mathbb{Z}^2$ such that, for all $\mathbf{p} \in \mathbb{Z}^2$, we have

$$R_{\theta}(\mathbf{p}) = (D \circ \mathcal{R}_{\theta})(\mathbf{p}) \\ = \begin{pmatrix} [p_x \cos \theta - p_y \sin \theta] \\ [p_x \sin \theta + p_y \cos \theta] \end{pmatrix} \qquad (14)$$

This rotation is called a discrete rotation (Fig. 2). Such discrete rotation $R_{\theta}$ is well-defined iff $\theta \in \hat{\mathbb{U}}$, i.e. $\theta$ is not a hinge angle. This results from the ambiguous definition of $[\cdot]$ on $\mathbb{Z} + \frac{1}{2}$. We set

$$\mathbb{R}_{\mathbb{Z}^2} = \{R_{\theta} \mid \theta \in \hat{\mathbb{U}}\} \qquad (15)$$

the set of all the discrete rotations. We denote by $R: \hat{\mathbb{U}} \to \mathbb{R}_{\mathbb{Z}^2}$ the surjective application defined for each $\theta \in \hat{\mathbb{U}}$ by $R(\theta) = R_{\theta}$.
<figure><img src="image_4.png" /><figcaption>**Fig. 2** The image $Y \subset \mathbb{R}^2$ (blue dots) of a finite subset $X = \llbracket x, x + 4 \rrbracket \times \llbracket y, y + 3 \rrbracket \subset \mathbb{Z}^2$ (for a given $(x, y) \in \mathbb{Z}^2$) composed of 20 points, transformed by a rotation $R_\theta$, i.e. $Y = R_\theta(X)$. The image $P$ (green and yellow dots) of $X$ by the associated discrete rotation $R_\theta$, i.e. $P = R_\theta(X)$. The green dots correspond to the points $\mathbf{q} \in P$ such that there exists exactly one point $\mathbf{p} \in X$ that satisfies $\mathbf{q} = R_\theta(\mathbf{p})$ (locally bijective configurations). The yellow dots correspond to the points $\mathbf{q} \in P$ such that there exist many points $\mathbf{p} \in X$ that satisfy $\mathbf{q} = R_\theta(\mathbf{p})$ (locally non-injective configurations). The red dots correspond to points $\mathbf{q} \notin P$, i.e. there exists no point $\mathbf{p} \in X$ that satisfies $\mathbf{q} = R_\theta(\mathbf{p})$ (locally non-surjective configurations).</figcaption></figure>

## 4.4 Finite discrete rotations

We now focus on the finite discrete rotations, which are the restrictions of the discrete rotations to finite domains defined by (discrete) Euclidean balls. These discrete rotations are especially those that allow us to define rotations on finite images. In particular, our further study will mainly deal with these rotations, for which we then introduce dedicated notions.

Let $\theta \in \hat{U}$ be a non-hinge angle. Let $R_\theta \in \Re_{\mathbb{Z}^2}$ be a discrete rotation. Let $\rho \in \mathbb{R}_+ = \{x \in \mathbb{R} \mid x \ge 0\}$. Let $B^\rho$ be the Euclidean ball of radius $\rho$ in $\mathbb{Z}^2$, i.e.

$$B^\rho = \{ \mathbf{q} \in \mathbb{Z}^2 \mid \|\mathbf{q}\|_2 \le \rho \} \qquad (16)$$

We denote by $R_\theta^\rho : B^\rho \to \mathbb{Z}^2$ the rotation defined as $R_\theta^\rho = (R_\theta)_{B^\rho}$, i.e. the restriction of the discrete rotation $R_\theta$ to the Euclidean ball $B^\rho$. Such rotation $R_\theta^\rho$ is called a discrete $\rho$-rotation (or simply a $\rho$-rotation). We denote by

$$\Re_{\mathbb{Z}^2}^\rho = \{R_\theta^\rho \mid R_\theta \in \Re_{\mathbb{Z}^2}\} \qquad (17)$$

the set of all the $\rho$-rotations. We set $R^\rho : \hat{U} \to \Re_{\mathbb{Z}^2}^\rho$ the surjective application defined for each $\theta \in \hat{U}$ by $R^\rho(\theta) = R_\theta^\rho$. We define the set $\mathbb{T}^\rho \subset \mathbb{T}$ by

$$\mathbb{T}^\rho = \{ \mathbf{t} = (p_x, p_y, k) \in \mathbb{Z}^3 \mid \left| k + \frac{1}{2} \right| \le \|(p_x, p_y)\|_2 \le \rho \} \qquad (18)$$

which gathers the triplets of $\mathbb{T}$ induced by the points inside the Euclidean ball $B^\rho$. We have

$$|\mathbb{T}^\rho| = \Theta(\rho^3) \qquad (19)$$

<figure><img src="image_5.png" /><figcaption>**Fig. 3** Subdivisions of $\mathbb{U}$ by the three sets $S_\bullet^\rho$ (a), $S_{\bullet \to \infty}^\rho$ (b) and $S_{\bullet \to \infty}^\rho$ (c). The illustration is given here for $\rho = 1$. The elements of $S_\bullet^\rho$, $S_{\bullet \to \infty}^\rho$ and $S_{\bullet \to \infty}^\rho$ are depicted in black. (a) $S_\bullet^\rho$ is composed by singletons that correspond to hinge angles. (b) $S_{\bullet \to \infty}^\rho$ is composed by open intervals bounded by these hinge angles. Note that $S_{\bullet \to \infty}^\rho$ is a partition of $\hat{U}$. (c) $S_{\bullet \to \infty}^\rho$ is composed by the segments where each segment is one of the open intervals of $S_{\bullet \to \infty}^\rho$ to which the left-bounding hinge angle has been added. Note that $S_\bullet^\rho \cup S_{\bullet \to \infty}^\rho$ is a partition of $\mathbb{U}$, and in particular we have $S_\bullet^\rho \cap S_{\bullet \to \infty}^\rho = \emptyset$. Note that $S_{\bullet \to \infty}^\rho$ is also a partition of $\mathbb{U}$ (the white spaces left between two successive segments in (c) are for visualization only). Each segment of $S_{\bullet \to \infty}^\rho$ (c) is composed by the union of an open interval of $S_{\bullet \to \infty}^\rho$ (b) and a singleton set of $S_\bullet^\rho$ (a).</figcaption></figure>

We define the set $\mathbb{H}^\rho \subset \mathbb{H}$ by

$$\mathbb{H}^\rho = \eta(\mathbb{T}^\rho) \\ = \{\eta(\mathbf{t}) \mid \mathbf{t} \in \mathbb{T}^\rho\} \qquad (20)$$

that gathers the hinge angles induced by the triplets of $\mathbb{T}^\rho$, i.e. the hinge angles induced at a radius lower than or equal to $\rho$. We have [26]

$$|\mathbb{H}^\rho| = \mathcal{O}(\rho^3) \qquad (21)$$

Note that we have

$$(\rho < 1) \iff (\mathbb{T}^\rho = \mathbb{H}^\rho = \emptyset) \qquad (22)$$

We consider on $\mathbb{U}$ the restriction of the total order $\le$ on $\mathbb{R}$. By assuming that $\mathbb{H}^\rho$ is ordered by $\le$, we set

$$\mathbb{H}^\rho = \{h_j^\rho\}_{j=0}^{\sigma^\rho-1} \qquad (23)$$

with $\sigma^\rho = |\mathbb{H}^\rho| \in \mathbb{N}$.

We consider on $\mathbb{T}$ the preorder $\le_T$ defined, for any $\mathbf{t}_1, \mathbf{t}_2 \in \mathbb{T}$ by

$$(\mathbf{t}_1 \le_T \mathbf{t}_2) \iff (\eta(\mathbf{t}_1) \le \eta(\mathbf{t}_2)) \qquad (24)$$

By assuming that $\mathbb{T}^\rho$ is sorted with respect to $\le_T$, we set

$$\mathbb{T}^\rho = \{\mathbf{t}_i^\rho\}_{i=0}^{s^\rho-1} \qquad (25)$$

with $s^\rho = |\mathbb{T}^\rho| \in \mathbb{N}$. We have $\sigma^\rho \le s^\rho$ and

$$(\rho \ge 1) \iff (\sigma^\rho \ge 1) \qquad (26)$$

**Remark 4** Although the number $s^\rho$ of triplets is greater than the number $\sigma^\rho$ of hinge angles, we recall that the number of prime triplets (see Prop. 2) is equal to the number of hinge angles.
## 5 Modeling discrete finite rotations

We now introduce three related families of subsets of $\mathcal{U}$, namely $\mathcal{S}_{\bullet}^{\rho}$, $\mathcal{S}_{\bullet \to \circ}^{\rho}$, $\mathcal{S}_{\bullet \to \circ}^{\rho}$ (Fig. 3). These sets, that play a technical role in the sequel, are directly induced by the set of hinge angles $\mathcal{H}^{\rho}$:

- $\mathcal{S}_{\bullet}^{\rho}$ associates each hinge angle $h \in \mathcal{H}^{\rho}$ with its induced singleton set;

- $\mathcal{S}_{\circ \to \circ}^{\rho}$, associates each hinge angle $h \in \mathcal{H}^{\rho}$ with the open interval of $\mathcal{U}$ bounded on the left by $h$ and on the right by its successor (modulo $\sigma^{\rho}$) in the ordered set $(\mathcal{H}^{\rho}, \leq)$;

- $\mathcal{S}_{\bullet \to \circ}^{\rho}$, associates each hinge angle $h \in \mathcal{H}^{\rho}$ with the left-closed/right-open interval (also called segment, for the sake of concision) of $\mathcal{U}$ bounded on the left by $h$ and on the right by its successor (modulo $\sigma^{\rho}$) in the ordered set $(\mathcal{H}^{\rho}, \leq)$.

If $\rho < 1$ then we have $\mathcal{H}^{\rho} = \emptyset$, i.e. there is no hinge angle (Eq. (22)). In that case, we set $\mathcal{S}_{\bullet}^{\rho} = \emptyset$ and $\mathcal{S}_{\circ \to \circ}^{\rho} = \mathcal{S}_{\bullet \to \circ}^{\rho} = \{\mathcal{U}\}$. If $\rho \ge 1$ then we have $\mathcal{H}^{\rho} \neq \emptyset$ and following the above description, we set

$$ \mathcal{S}_{\bullet}^{\rho} = \{ \{h_j^{\rho}\} \}_{j=0}^{\sigma^{\rho}-1} \qquad (27) $$

$$ \mathcal{S}_{\circ \to \circ}^{\rho} = \{ (h_j^{\rho}, h_{(j+1)[\sigma^{\rho}]}^{\rho}) \}_{j=0}^{\sigma^{\rho}-1} \qquad (28) $$

$$ \mathcal{S}_{\bullet \to \circ}^{\rho} = \{ S_{j}^{\rho} = [h_{j}^{\rho}, h_{(j+1)[\sigma^{\rho}]}^{\rho}] \}_{j=0}^{\sigma^{\rho}-1} \qquad (29) $$

where $a[b]$ is a modulo $b$ (Fig. 3).

**Remark 5 ([30]**) Let $\rho \in \mathbb{R}_{+}$.

- The two sets $\mathcal{H}^{\rho}$ and $\mathcal{S}_{\bullet}^{\rho}$ are in bijection.

- The two sets $\mathcal{S}_{\circ \to \circ}^{\rho}$ and $\mathcal{S}_{\bullet \to \circ}^{\rho}$ are in bijection.

- If $\rho \ge 1$ then the four sets $\mathcal{H}^{\rho}$, $\mathcal{S}_{\bullet}^{\rho}$, $\mathcal{S}_{\circ \to \circ}^{\rho}$ and $\mathcal{S}_{\bullet \to \circ}^{\rho}$ are in bijection.

By analogy with Eq. (10), we define

$$ \mathcal{U}^{\rho} = \mathcal{U} \setminus \mathcal{H}^{\rho} \qquad (30) $$

the set of all the angles of $\mathcal{U}$ which are not hinge angles induced at a radius lower than or equal to $\rho$.

**Remark 6** Let $\rho \in \mathbb{R}_{+}$.

- The set $\mathcal{S}_{\circ \to \circ}^{\rho}$ is a partition of $\mathcal{U}^{\rho}$.

- The set $\mathcal{S}_{\bullet \to \circ}^{\rho}$ is a partition of $\mathcal{U}$.

- The union of sets $\mathcal{S}_{\bullet}^{\rho} \cup \mathcal{S}_{\circ \to \circ}^{\rho}$ is a partition of $\mathcal{U}$ that refines the partition $\mathcal{S}_{\bullet \to \circ}^{\rho}$.

**Remark 7 ([30]**) Let $I = (h^{-}, h^{+}) \in \mathcal{S}_{\circ \to \circ}^{\rho}$ (Fig. 4(b)). For any $\theta_1, \theta_2 \in I \cap \mathcal{U}$, we have $R_{\theta_1}^{\rho} = R_{\theta_2}^{\rho}$. Let $h \in I \cap \mathcal{H}$ be a hinge angle that belongs to $I$ (Fig. 4(a)). Since $h$ is a hinge angle, the discrete rotation $R_h$ is undefined, and so is the $\rho$-rotation $R_h^{\rho}$. Nonetheless, the hinge angle $h \in \mathcal{H}$ does not belong to $\mathcal{H}^{\rho}$. As a consequence, we can extend $R^{\rho}$ by continuity, by setting $R^{\rho}(h) = R^{\rho}(\theta_1)$.

<figure><img src="image_6.png" /><figcaption>**Fig. 4** (b) An open interval $I = (h^{-}, h^{+}) \in \mathcal{S}_{\circ \to \circ}^{\rho}$. This interval $I$ is depicted by the black line. The two hinge angles $h^{-}, h^{+}$ are depicted by blue circles. We have $I \subseteq \mathcal{U}$, but $I \not\subseteq \mathcal{U}$. In particular, there exist hinge angles $h \in \mathcal{H}$ such that $h \in I$. (a) The set $I \cap \mathcal{U}$, depicted by the black lines. The hinge angles $h \in I \cap \mathcal{H}$ are depicted by orange circles. (c) The segment $S = I \cup \{h^{-}\} \in \mathcal{S}_{\bullet \to \circ}^{\rho}$, depicted by the black line and black dot. The function $R^{\rho}$ can be extended by continuity from $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ to $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ (i.e. from (a) to (b)), see Rem. 7. It can then be extended by continuity from $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ to $\mathcal{U} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ (i.e. from (b) to (c)), see Rem. 9. The open interval $I$ and the segment $S$ both model a specific $\rho$-rotation, see Rem. 9.</figcaption></figure>

From Rem. 7, we can now assume that we have extended $R^{\rho}$ from $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ to $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ (Fig. 4(a,b)).

Let $\sim_{\rho}$ be the equivalence relation on $\mathcal{U}^{\rho}$ defined, for any $\theta_1, \theta_2 \in \mathcal{U}^{\rho}$ by

$$ (\theta_1 \sim_{\rho} \theta_2) \iff (R_{\theta_1}^{\rho} = R_{\theta_2}^{\rho}) \qquad (31) $$

Each equivalence class $[\theta]_{\sim_{\rho}}$ (with $\theta \in \mathcal{U}^{\rho}$) corresponds to a specific $\rho$-rotation. In other words, the sets $\mathcal{R}_{\mathbb{Z}^2}^{\rho}$ and $\mathcal{U}^{\rho} / \sim_{\rho}$ are in bijection.

**Remark 8 ([30]**) Let $\rho \in \mathbb{R}_{+}$. We have $\mathcal{S}_{\circ \to \circ}^{\rho} = \mathcal{U}^{\rho} / \sim_{\rho}$.

It follows that there is a bijection between the set $\mathcal{R}_{\mathbb{Z}^2}^{\rho}$ of the $\rho$-rotations and the set $\mathcal{S}_{\circ \to \circ}^{\rho}$ of the open intervals that partitions $\mathcal{U}^{\rho}$. This bijection is simply given by the mapping from $\mathcal{S}_{\circ \to \circ}^{\rho}$ to $\mathcal{R}_{\mathbb{Z}^2}^{\rho}$ defined by $(h^{-}, h^{+}) \mapsto R_{\theta}^{\rho}$ with $\theta = \frac{h^{-}+h^{+}}{2}$. As a consequence, we can model $\mathcal{R}_{\mathbb{Z}^2}^{\rho}$ by $\mathcal{S}_{\circ \to \circ}^{\rho}$, or any other set in bijection with $\mathcal{S}_{\circ \to \circ}^{\rho}$ (Rem. 5).

**Remark 9 ([30]**) Let $h^{-} = h_{j}^{\rho} \in \mathcal{H}^{\rho}$ ($0 \le j \le \sigma^{\rho} - 1$). The $\rho$-rotation $R_{h^{-}}^{\rho}$ is undefined. However, $R_{\theta}^{\rho}$ is defined and constant for all $\theta \in (h_{j}^{\rho}, h_{(j+1)[\sigma^{\rho}]}^{\rho})$. We can then extend $R_{h^{-}}^{\rho}$ by continuity, by setting $R^{\rho}(h^{-}) = R^{\rho}(\theta)$.

From Rem. 9, we can now assume that we have extended $R^{\rho}$ from $\mathcal{U}^{\rho} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ to $\mathcal{U} \to \mathcal{R}_{\mathbb{Z}^2}^{\rho}$ (Fig. 4(b,c)).

## 6 Bijectivity of discrete rotations

The continuous rotations are bijective. By contrast, the question of the bijectivity of the rotations is less trivial in the discrete case. See Fig. 2 for an example of a non-bijective discrete rotation.
<figure><img src="image_7.png" /><figcaption>**Fig. 5** Bijective discrete rotation angles depicted on the unit disk. There exist an infinity of such angles $\theta$; only the first angles obtained for values $p \in [0, 10]$ in Eq. (32) are depicted here. The red ones correspond to $(\cos \theta, \sin \theta) = (\frac{2p(p+1)}{2p^2+2p+1}, \frac{2p+1}{2p^2+2p+1})$. The blue ones, obtained by symmetry with respect to the diagonal axis, correspond to $(\cos \theta, \sin \theta) = (\frac{2p+1}{2p^2+2p+1}, \frac{2p(p+1)}{2p^2+2p+1})$. The angles of the other three quadrants are obtained by symmetry with respect to the horizontal and vertical axes.</figcaption></figure>

Let $\theta \in \mathring{U}$. The discrete rotation $R_{\theta} \in \mathbb{R}_{\mathbb{Z}^2}$ may be bijective or not, depending on the value of $\theta$. A characterization of the bijective discrete rotations was proposed in [14] and proved in [27]. Let us set

$$ \mathbb{B} = \left\{ \theta \in \mathring{U} \mid \sin \theta \in \left\{ \pm \frac{2p(p+1)}{2p^2+2p+1}, \pm \frac{2p+1}{2p^2+2p+1} \mid p \in \mathbb{N} \right\} \right\} \quad (32) $$

**Proposition 10 ([27])** Let $\theta \in \mathring{U}$. The discrete rotation $R_{\theta} \in \mathbb{R}_{\mathbb{Z}^2}$ is bijective if and only if $\theta \in \mathbb{B}$.

See Fig. 5 for an illustration of these characterized rotation angles.

We denote by

$$ \mathbb{B}_{\mathbb{Z}^2} = \{R_{\theta} \in \mathbb{R}_{\mathbb{Z}^2} \mid \theta \in \mathbb{B}\} \quad (33) $$

the set of the bijective discrete rotations.

The set $\mathbb{B}$ is a subset of Pythagorean angles (i.e. angles with rational sine and cosine determined by Pythagorean triplets). Pythagorean angles do not intersect hinge angles [28], and we then have

$$ \mathbb{B} \cap \mathbb{H} = \emptyset \quad (34) $$

In this section, we describe two paradigms for defining the bijectivity of $\rho$-rotations. The first (Sect. 6.1) defines bijective $\rho$-rotations as the restrictions of the bijective discrete rotations. The second (Sect. 6.2) considers injective $\rho$-rotations, which are then bijective from their finite support to their finite image set.

## 6.1 Bijective $\rho$-rotations as the restrictions of bijective discrete rotations

We consider the $\rho$-rotations which are restrictions of bijective discrete rotations.

<figure><img src="image_8.png" /><figcaption>**Fig. 6** (a,c,e) Initial sets, in blue: (a) $\mathbb{Z}^2$ (restricted to the set $X$ of the points $p$ such that $\|p\|_{\infty} \le 8$, for the sake of visualization); (c) the Euclidean ball $B^{\sqrt{12}} \subset \mathbb{Z}^2$ of radius $\sqrt{12}$; (e) the Euclidean ball $B^{\sqrt{13}} \subset \mathbb{Z}^2$ of radius $\sqrt{13}$. (b,d,f) Images of these sets by application of discrete rotations of angle $\pi/10$: (b) image of $\mathbb{Z}^2$ (restricted to $X$) by the discrete rotation $R_{\pi/10}$; (d) image of $B^{\sqrt{12}}$ by the $\rho$-rotation $R_{\pi/10}^{\sqrt{12}}$; (f) image of $B^{\sqrt{13}}$ by the $\rho$-rotation $R_{\pi/10}^{\sqrt{13}}$. The rotations have a bijective behaviour for the blue points and a non-injective behaviour for the red points. (a–b) The discrete rotation $R_{\pi/10}$ is not bijective, i.e. $R_{\pi/10} \notin \mathbb{B}_{\mathbb{Z}^2}$. (c–d) The $\rho$-rotation $R_{\pi/10}^{\sqrt{12}}$ is injective, i.e. $R_{\pi/10}^{\sqrt{12}} \in \mathbb{B}_{\mathbb{Z}^2}^{\sqrt{12}}$, but $R_{\pi/10}^{\sqrt{12}} \notin \mathbb{B}_{\mathbb{Z}^2}^{\sqrt{12}}$ since $R_{\pi/10} \notin \mathbb{B}_{\mathbb{Z}^2}$. (e–f) The $\rho$-rotation $R_{\pi/10}^{\sqrt{13}}$ is not injective, i.e. $R_{\pi/10}^{\sqrt{13}} \notin \mathbb{B}_{\mathbb{Z}^2}^{\sqrt{13}}$ and a fortiori $R_{\pi/10}^{\sqrt{13}} \notin \mathbb{B}_{\mathbb{Z}^2}^{\sqrt{13}}$. This example illustrates the fact that for an angle $\theta$ that does not induce a bijective discrete rotation, we may however build $\rho$-rotations which are injective (and thus bijective from their domain to their image) for certain radii $\rho$ of Euclidean balls sufficiently small (here, the $\rho$-rotations of angle $\pi/10$ are injective for $\rho \le \sqrt{12}$, and become non-injective for $\rho \ge \sqrt{13}$).</figcaption></figure>

Let $\rho \in \mathbb{R}_+$. We set

$$ \begin{aligned} \mathfrak{B}_{\mathbb{Z}^2}^{\rho} &= \{R_{\theta}^{\rho} \in \mathfrak{R}_{\mathbb{Z}^2}^{\rho} \mid R_{\theta} \in \mathfrak{B}_{\mathbb{Z}^2}\} \\ &= \{R_{\theta}^{\rho} \in \mathfrak{R}_{\mathbb{Z}^2}^{\rho} \mid \theta \in \mathbb{B}\} \end{aligned} \quad (35) $$
the subset of the $\rho$-rotations which are restrictions of bijective discrete rotations (Eq. (33)).

From this definition, the $\rho$-rotation associated to the segment $[h_j^\rho, h_{(j+1)[\sigma^\rho]}^\rho]$ ($0 \le j \le \sigma^\rho - 1$) is bijective iff there exists at least an angle $\theta \in \mathbb{B}$ (Eq. (32)) such that $h_j^\rho < \theta < h_{(j+1)[\sigma^\rho]}^\rho$, thanks to Eq. (34). A way to determine the bijective $\rho$-rotations would be to sort the set $\mathbb{H}^\rho \cup \mathbb{B}$. Since $\mathbb{B}$ is infinite, this whole sorting is not tractable. Nonetheless, we can consider only a finite subset of $\mathbb{B}$.

Let us set $\mathbb{B}^\rho \subset \mathbb{B}$ as

$$ \mathbb{B}^{\rho} = \left\{ \theta \in \mathring{\mathbb{U}} \mid \sin \theta \in \left\{ \begin{array}{l} \pm \frac{2p(p+1)}{2p^2+2p+1}, \\ \pm \frac{2p+1}{2p^2+2p+1} \end{array} \mid p \in \mathbb{N} \wedge p \le 2\rho \right\} \right\} \quad (36) $$

**Property 11 ([30]** Let $\rho \in \mathbb{R}_+$. We have

$$ \mathfrak{B}_{\mathbb{Z}^2}^{\rho} = \{R_{\theta}^{\rho} \in \mathfrak{R}_{\mathbb{Z}^2}^{\rho} \mid \theta \in \mathbb{B}^{\rho}\} \quad (37) $$

From Prop. 11, in order to define $\mathfrak{B}_{\mathbb{Z}^2}^\rho$, it is sufficient to sort the finite set $\mathbb{H}^\rho \cup \mathbb{B}^\rho$. The exact comparison of elements of $\mathbb{H}^\rho \cup \mathbb{B}^\rho$ can be made in constant time [28,36].

## 6.2 Injective $\rho$-rotations

In a second time, we consider the $\rho$-rotations $R_\theta^\rho$ which are injective and thus bijective from the Euclidean ball $\mathbb{B}^\rho$ to $R_\theta^\rho(\mathbb{B}^\rho)$.

Let $\rho \in \mathbb{R}_+$. We set

$$ \mathfrak{F}_{\mathbb{Z}^2}^{\rho} \subseteq \mathfrak{R}_{\mathbb{Z}^2}^{\rho} \quad (38) $$

the subset of the injective $\rho$-rotations.

A bijective $\rho$-rotation (as defined in Sect. 6.1) is injective, i.e. $\mathfrak{B}_{\mathbb{Z}^2}^\rho \subseteq \mathfrak{F}_{\mathbb{Z}^2}^\rho$. However, the reciprocal is not always true. Indeed, an injective $\rho$-rotation may be non-bijective, i.e. we may have $\mathfrak{F}_{\mathbb{Z}^2}^\rho \not\subseteq \mathfrak{B}_{\mathbb{Z}^2}^\rho$ (see Fig. 6).

The $\rho$-rotation $R_\theta^\rho \in \mathfrak{R}_{\mathbb{Z}^2}^\rho$ associated to the segment $[h_j^\rho, h_{(j+1)[\sigma^\rho]}^\rho]$ ($0 \le j \le \sigma^\rho - 1$) is injective iff we have

$$ \forall \mathbf{p}, \mathbf{q} \in \mathbb{B}^{\rho}, (R_{\theta}^{\rho}(\mathbf{p}) = R_{\theta}^{\rho}(\mathbf{q})) \implies (\mathbf{p} = \mathbf{q}) \quad (39) $$

Then, one can assess the potential injectivity of $R_\theta^\rho$ by incrementally considering each point of the Euclidean ball $\mathbb{B}^\rho$ and checking its image by $R_\theta^\rho$ with respect to the image of the already processed points.

<figure><img src="image_9.png" /><figcaption>**Fig. 7** The set $\Xi = \{a, b, c, d, e, f, g, h, i, j, k, l\}$ is endowed with a hierarchical order relation $\sqsubseteq$. The elements of $\Xi$ are depicted by disks. The relation $\triangleleft$ associated to $\sqsubseteq$ is depicted by edges. Here, the higher the position, the greater the value with respect to $\sqsubseteq$. In particular, $a$ (in green) is the maximum of $(\Xi, \sqsubseteq)$ and thus the root of the tree $(\Xi, \triangleleft)$. The elements $e, g, i, j, k, l$ (in yellow) are the minimal elements of $(\Xi, \sqsubseteq)$ and thus the leaves of the tree $(\Xi, \triangleleft)$. The elements greater than or equal to $j$ compose the set $\{j, h, f, c, a\}$ which is totally ordered by $\sqsubseteq$ (see the red part of the tree).</figcaption></figure>

## 7 Trees, partition trees

In graph theory, a tree is a connected acyclic graph. Hereafter, we formulate the notions of tree in the framework of ordered sets, which is compliant with the framework of graphs (Sect. 7.1). We describe the notion of a partition tree, that allows to model a sequence of successively refining partitions (Sect. 7.2) and we recall specific kinds of partition trees defined in mathematical morphology, namely (binary) partition trees and watershed trees (Sect. 7.3).

### 7.1 Trees

Let $\Xi$ be a nonempty set. Let $\sqsubseteq$ be an order (i.e. reflexive, transitive, antisymmetric) relation on $\Xi$. Then $(\Xi, \sqsubseteq)$ is a directed graph. Let $\triangleleft$ be the relation obtained as the reflexive-transitive reduction of $\sqsubseteq$ (i.e. by removing the reflexive links (loops) and all the links induced by the transitivity of the order). The graph $(\Xi, \triangleleft)$ is called the Hasse diagram of $(\Xi, \sqsubseteq)$. In particular, $(\Xi, \triangleleft)$ is a subgraph of $(\Xi, \sqsubseteq)$.

We say that $\sqsubseteq$ is a hierarchical order if the following two conditions hold:

- $\Xi$ admits a maximum (denoted as $\top$) for the order $\sqsubseteq$;

- for all $x \in \Xi$, the subset $\{y \in \Xi \mid x \sqsubseteq y\} \subseteq \Xi$ of the elements greater than $x$ is totally ordered by $\sqsubseteq$.

If $\sqsubseteq$ is a hierarchical order on $\Xi$ then the Hasse diagram $(\Xi, \triangleleft)$ of $(\Xi, \sqsubseteq)$ is a tree. The root of this tree is the maximum $\top$ of $(\Xi, \sqsubseteq)$. The leaves of this tree are the minimal elements of $(\Xi, \sqsubseteq)$. See Fig. 7.
<figure><img src="image_10.png" /><figcaption>**Fig. 8** A set $\mathcal{O}$ composed of 7 elements, depicted by 7 distinct colours. (a) A set $\{\Pi_i\}_{i=0}^5$ of partitions of $\mathcal{O}$ such that for any $i, j \in [0, 5]$ we have $(i \ge j) \Rightarrow (\Pi_i \in \Pi_j)$. For each $i \in [0, 5]$, each $X \in \Pi_i$ is depicted by elements of $\mathcal{O}$ linked by horizontal black edges. The partition $\Pi_0$ is the trivial partition $\{\mathcal{O}\}$. (b) The partition tree $(\Xi, <)$ associated to the set of partitions $\{\Pi_i\}_{i=0}^5$. Each element $X \in \Xi = \cup_{i=0}^5 \Pi_i$ is depicted once. The relation $<$ is represented by the vertical black edges.</figcaption></figure>

<caption>**Fig. 9** A set $\mathcal{O}$ composed of 7 elements, depicted by 7 distinct colours. (a) A set $\{\Pi_i\}_{i=0}^5$ of general partitions of $\mathcal{O}$ such that for any $i, j \in [0, 5]$ we have $(i \ge j) \Rightarrow (\Pi_i \in \Pi_j)$. For each $i \in [0, 5]$, each $X \in \Pi_i$ is depicted by elements of $\mathcal{O}$ linked by horizontal black edges. The general partition $\Pi_0$ is the trivial partition $\{\mathcal{O}\}$. (b) The general partition tree $(\Xi, <)$ associated to the set of general partitions $\{\Pi_i\}_{i=0}^5$. Each element $X \in \Xi = \cup_{i=0}^5 \Pi_i$ is depicted once. The relation $<$ is represented by the vertical black edges.</caption>

## 7.2 Partition trees

Let $\mathcal{O}$ be a nonempty set. Let $\Pi_1, \Pi_2$ be two partitions of $\mathcal{O}$. We say that $\Pi_2$ refines $\Pi_1$, and we write $\Pi_2 \in \Pi_1$ if for any $X_2 \in \Pi_2$ there exists $X_1 \in \Pi_1$ such that $X_2 \subseteq X_1$.

Let $\{\Pi_k\}_{k=0}^t$ ($t \in \mathbb{N} \cup \{\infty\}$) be a set of partitions of $\mathcal{O}$ such that $\Pi_0 = \{\mathcal{O}\}$ and for any $0 \le i, j \le t$ we have $(i \ge j) \Rightarrow (\Pi_i \in \Pi_j)$. See Fig. 8(a).

Let $\Xi = \cup_{k=0}^t \Pi_k$. The inclusion relation $\subseteq$ is a hierarchical order on $\Xi$. The Hasse diagram $(\Xi, <)$ of $(\Xi, \subseteq)$ is a tree, called partition tree of $\mathcal{O}$. See Fig. 8(b). (The dendrograms, usually considered in hierarchical data clustering, are examples of partition trees.)

In the above definitions, one can substitute the notion of a *general partition* to the notion of a partition. A general partition $\Pi$ of $\mathcal{O}$ is a partition of a nonempty subset $\tilde{\mathcal{O}} \subseteq \mathcal{O}$. Considering a set $\{\Pi_k\}_{k=0}^t$ of general partitions, instead of partitions, leads to defining the so-called general partition tree. See Fig. 9.

## 7.3 Particular partition trees

In the framework of mathematical morphology [19], various partition trees and general partition trees were proposed over the last decades. Within these morphological trees, two deserve to be mentioned in this article: the (binary) partition tree [35] and the watershed tree [18]. Indeed, they present an interest for modeling the combinatorial structure of the discrete rotations (Sect. 8), and they provide guidelines for the construction of this combinatorial structure (Sect. 9).

The binary partition tree [35] is a partition tree such as defined in Sect. 7.2, but with two specificities. First, the elements of $\Xi$ are connected subsets of a set $\mathcal{O}$. (This implies that $\mathcal{O}$ be endowed with a structure (e.g. topological space, graph framework) that provides a notion of connectedness.) Second, for each non-leaf element $X \in \Xi$ of the tree, there exist exactly two elements $X_1 < X$ and $X_2 < X$ and $\{X_1, X_2\}$ is a partition of $X$.

The set $\mathcal{O}$ is generally composed by elements that are (isomorphic to) the leaves of the tree. This set of leaves is generally endowed with an adjacency (i.e. irreflexive/loopless, symmetric) relation $\sim$ so that $(\mathcal{O}, \sim)$ is an undirected graph. A binary partition tree can be built by iteratively merging pairwise the adjacent vertices of $(\mathcal{O}, \sim)$ so that it progressively collapses onto the trivial graph $((\mathcal{O}, \emptyset), \emptyset)$. The last, unique vertex of this collapsed graph, namely $\mathcal{O}$, becomes the root of the binary partition tree, and this tree encodes the history of the successive merging operations and the induced connected subsets of $\mathcal{O}$. The size of this tree is $\Theta(|\mathcal{O}|)$ and its construction has a time cost $O(|\mathcal{O}| \log |\mathcal{O}|)$ [35].

The watershed tree [18] is a partition tree defined by following the watershed paradigm [6]. It is similar to the binary partition tree, but with two slight differences. First, it may be non-binary. For each non-leaf element $X \in \Xi$ of the watershed tree, there exist $k$ elements $X_i \in \Xi$ ($1 \le i \le k \ge 2$) such that $X_i < X$ and $\{X_i\}_{i=1}^k$ is a partition of $X$. Second, its construction is guided by a valuation of the edges of the graph $(\mathcal{O}, \sim)$. This valuation is defined as an application $\nu: \sim \to \mathbb{N}$. The construction of the watershed tree follows the same paradigm as the construction of a binary partition tree.
tree, except that $k \ge 2$ vertices can be merged at the same time to form a new element. We merge in priority the vertices that share adjacency edges (·) of maximal valuation $v$. In particular, the watershed tree can be built first as a binary partition tree, and then post-processed as a general partition tree via a simple merging procedure. The size of this tree is $\Theta(|\Omega|)$ and its construction has a time cost $O(|\Omega| \log |\Omega|)$.

## 8 Tree structure of the space of discrete rotations

We recall that the set of angles $U$ is partitioned by $\{\mathbb{H}, \hat{\mathbb{U}}\}$, i.e. by the subsets of hinge and non-hinge angles, respectively (Sect. 4.2). Let $\theta \in U$. If $\theta \in \mathbb{H}$ (i.e. $\theta$ is a hinge angle) then there is no discrete rotation associated to $\theta$. If $\theta \in \hat{\mathbb{U}}$ (i.e. $\theta$ is not a hinge angle) then the discrete rotation $R_{\theta} \in \mathbb{R}_{\mathbb{Z}^2}$ exists. More precisely, the set of non-hinge angles and the set of discrete rotations are linked as follows.

**Remark 12 ([30])** The sets $\hat{\mathbb{U}}$ and $\mathbb{R}_{\mathbb{Z}^2}$ are in bijection.

In other words, one can model the discrete rotations by the non-hinge angles.

In this section, we describe the combinatorial (tree) structure of the (infinite) discrete rotations and of the (finite) $\rho$-rotations. This will facilitate the further definition of two paradigms proposed in Sects. 9–10 for building the space of the bijective and general $\rho$-rotations. Before starting this description, let us first consider the following remark.

**Remark 13 ([30])** Let $r \in \mathbb{N}$. Let $\rho_1, \rho_2 \in \mathbb{R}_+$. We have

$$ (\sqrt{r} \le \rho_1 \le \rho_2 < \sqrt{r+1}) \implies (B^{\rho_1} = B^{\rho_2} = B^{\sqrt{r}}) \quad (40) \\ \implies (\forall \theta \in U, R_{\theta}^{\rho_1} = R_{\theta}^{\rho_2} = R_{\theta}^{\sqrt{r}}) $$

As a consequence, in order to study the $\rho$-rotations, it is sufficient to consider the values of $\sqrt{\mathbb{N}}$ instead of $\mathbb{R}_+$.

### 8.1 Combinatorial structure of all the discrete rotations: An infinite tree

We recall that, for any $\rho \in \sqrt{\mathbb{N}}$, the set $S_{\circ\circ}^{\rho}$ (Eq. (28))—that gathers the open intervals bounded by the hinge angles of $\mathbb{H}^{\rho}$ (Eq. (20)) induced by the points within the Euclidean ball $B^{\rho}$—is a partition of $\hat{\mathbb{U}}^{\rho}$ (Rem. 6).

Let $\rho_1, \rho_2 \in \sqrt{\mathbb{N}}$. We have

$$ (\rho_1 \le \rho_2) \Rightarrow (\mathbb{T}^{\rho_1} \subseteq \mathbb{T}^{\rho_2}) \Rightarrow (\mathbb{H}^{\rho_1} \subseteq \mathbb{H}^{\rho_2}) \Rightarrow \left\{ \begin{array}{l} (\hat{\mathbb{U}}^{\rho_2} \subseteq \hat{\mathbb{U}}^{\rho_1}) \\ (S_{\circ\circ}^{\rho_2} \in S_{\circ\circ}^{\rho_1}) \end{array} \right. \quad (41) $$

(Eqs. (18,20,30)). Let us set

$$ S_{\circ\circ} = \{\{\theta\} | \theta \in \hat{\mathbb{U}}\} \quad (42) $$

<figure><img src="image_11.png" /><figcaption>**Fig. 10** The set $S_{\circ\circ}^*$ decomposed from top to bottom by increasing values of $\rho \in \sqrt{\mathbb{N}}$ (symbolic view: the number and position of the hinge angles are arbitrary, here). At the $\rho^2$-th line ($\rho \ge \sqrt{1}$), each horizontal black segment depicts an open interval of $S_{\circ\circ}^\rho$ separated from the others by hinge angles, and the associated (finite) $\rho$-rotation. The last line corresponds to $S_{\circ\circ}$. Each red circle depicts a (closed) singular interval $\{\theta\}$ so that $\theta \in \hat{\mathbb{U}}$ is a non-hinge angle, and the associated (infinite) discrete rotation. Each interval at a given line is included in an interval at a higher line. The Hasse diagram $(S_{\circ\circ}^*, \triangleleft)$ of the ordered set $(S_{\circ\circ}^*, \subseteq)$ is then a general partition tree. The blue vertical lines depict the edges of the relation $\triangleleft$.</figcaption></figure>

which is trivially in bijection with $\hat{\mathbb{U}}$ and is, in particular, a partition of $\hat{\mathbb{U}}$. For any $\rho \in \sqrt{\mathbb{N}}$, we have $\hat{\mathbb{U}} \subseteq \hat{\mathbb{U}}^{\rho}$ and $S_{\circ\circ} \in S_{\circ\circ}^{\rho}$

Let us set

$$ S_{\circ\circ}^* = S_{\circ\circ} \cup \bigcup_{\rho \in \sqrt{\mathbb{N}}} S_{\circ\circ}^{\rho} \quad (43) $$

Following the definitions and notations of Sect. 7.2, the Hasse diagram $(S_{\circ\circ}^*, \triangleleft)$ of the ordered set $(S_{\circ\circ}^*, \subseteq)$ is a general partition tree. Based on this discussion and on the facts that:

- for any $\rho \in \sqrt{\mathbb{N}}$, $S_{\circ\circ}^{\rho}$ and $\mathbb{R}_{\mathbb{Z}^2}^{\rho}$ are in bijection (Rem. 8); and

- $S_{\circ\circ}$ and $\mathbb{R}_{\mathbb{Z}^2}$ are in bijection (Rem. 12 and Eq. (42));

we have the following result.

We set

$$ \mathbb{R}_{\mathbb{Z}^2}^* = \mathbb{R}_{\mathbb{Z}^2} \cup \bigcup_{\rho \in \sqrt{\mathbb{N}}} \mathbb{R}_{\mathbb{Z}^2}^{\rho} \quad (44) $$

which gathers the finite and infinite discrete rotations.

**Proposition 14** The combinatorial space of $\mathbb{R}_{\mathbb{Z}^2}^*$ is the general partition tree $\mathfrak{T}(\mathbb{R}_{\mathbb{Z}^2}^*) = (S_{\circ\circ}^*, \triangleleft)$. Its root is the (unique, finite) $\sqrt{0}$-rotation $R_{\theta}^{\sqrt{0}}$ (for any $\theta \in U$). Its leaves are all the (infinite) discrete rotations $R_{\theta}$ (for all $\theta \in \hat{\mathbb{U}}$).

This combinatorial structure (Fig. 10) has the virtue to model all the (finite and infinite) discrete rotations via a tree, and to shed light on the links that exist between the (finite) $\rho$-rotations (that compose the upper part of the tree, in black, i.e. all the tree but the leaves) and the (infinite) discrete rotations (that compose the lower part of the tree, in red, i.e. the leaves).
However, this tree is infinite, both because its set of leaves is infinite (with a “size” $|\tilde{U}|$) and because its set of non-leaves is infinite (with a “size” $|\tilde{U}^\rho| = O(\rho^3)$ with $\rho \to \infty$). Then, beyond its theoretical interest, this structure cannot be handled in practice as it stands.

## 8.2 Combinatorial structure of the first finite discrete rotations: A finite tree

Let $\mu \in \sqrt{\mathbb{N}}$. We now restrict ourselves to the finite subspace of the $\rho$-rotations for all the values $\rho \in [\sqrt{0}, \mu]$ (of size $\Theta(\mu^2)$). In other words, we consider a finite upper part of the previous tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^*)$. We recall that, for any $\rho \in \sqrt{\mathbb{N}}$, the set $\mathbb{S}_{\bullet, \bullet}^\rho$ (Eq. (29))—that gathers the segments bounded by the hinge angles of $\mathbb{H}^\rho$ (Eq. (20)) induced by the points within the Euclidean ball $B^\rho$—is a partition of $\mathbb{U}$ (Rem. 6). Let $\rho_1, \rho_2 \in \sqrt{\mathbb{N}}$. We have

$$ (\rho_1 \le \rho_2) \Rightarrow (\mathbb{T}^{\rho_1} \subseteq \mathbb{T}^{\rho_2}) \Rightarrow (\mathbb{H}^{\rho_1} \subseteq \mathbb{H}^{\rho_2}) \Rightarrow (\mathbb{S}_{\bullet, \bullet}^{\rho_2} \in \mathbb{S}_{\bullet, \bullet}^{\rho_1}) \quad (45) $$

We set

$$ \mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]} = \bigcup_{\rho \in [\sqrt{0}, \mu]} \mathbb{S}_{\bullet, \bullet}^{\rho} \quad (46) $$

Following the definitions and notations of Sect. 7.2, the Hasse diagram $(\mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}, \prec)$ of the ordered set $(\mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}, \subseteq)$ is a partition tree. We recall that for any $\rho \in \sqrt{\mathbb{N}}$, $\mathbb{S}_{\bullet, \bullet}^\rho$ and $\mathfrak{R}_{\mathbb{Z}^2}^\rho$ are in bijection (Rems. 8–9). We set

$$ \mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]} = \bigcup_{\rho \in [\sqrt{0}, \mu]} \mathfrak{R}_{\mathbb{Z}^2}^{\rho} \quad (47) $$

which gathers all the $\rho$-rotations for $\rho \in [\sqrt{0}, \mu]$. Based on the above discussion, we have the following result.

**Proposition 15 (Stated in [30] with partial proof)** Let $\mu \in \sqrt{\mathbb{N}}$. The combinatorial space of $\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}$ is the partition tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}) = (\mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}, \prec)$. Its root is the (unique, finite) $\sqrt{0}$-rotation $R_\theta^{\sqrt{0}}$ (for any $\theta \in \mathbb{U}$). Its leaves are all the (finite) $\mu$-rotations $R_\theta^\mu$ (for all $\theta \in \mathbb{U}$).

**Remark 16** The size of the set of leaves of the tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is $|\mathbb{S}_{\bullet, \bullet}^\mu| = O(\mu^3)$. Since $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is a partition tree, its size is $|\mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}| = O(\mu^3)$. For each $\rho \in [\sqrt{0}, \mu]$, the size of set $\mathfrak{R}_{\mathbb{Z}^2}^\rho$ of the $\rho$-rotations is $|\mathbb{S}_{\bullet, \bullet}^\rho| = O(\rho^3)$. If all the sets $\mathbb{S}_{\bullet, \bullet}^\rho$ were disjoint, the size of $\mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}$ would be $O(\mu^5)$ as $||[\sqrt{0}, \mu]| = O(\mu^2)$. Indeed, these sets are not disjoint. More precisely, for two successive sets $\mathbb{S}_{\bullet, \bullet}^\rho$ and $\mathbb{S}_{\bullet, \bullet}^{\rho \oplus 1}$ ($\rho \in [\sqrt{0}, \mu \ominus 1]$), the number of elements that differ between them is only $O(\rho)$.

<figure><img src="image_12.png" /><figcaption>**Fig. 11** (a) The set $\mathbb{S}_{\bullet, \bullet}^\mu$, composed of segments $S = [h^-, h^+)$ with $h^-$, $h^+$ successive hinge angles in $\mathbb{H}^\mu$. Each segment $S$ is depicted by a black arc and a black dot. See also Fig. 3(c). (b) The two sets $\mathbb{S}_{\bullet, \bullet}^\mu$ and $\mathbb{S}_{\bullet, \bullet}^\rho$. The set $\mathbb{S}_{\bullet, \bullet}^\mu$ is in bijection with $\mathbb{S}_{\bullet, \bullet}^\rho$. Each open interval of $\mathbb{S}_{\bullet, \bullet}^\mu$ is depicted by a black arc. Each singular closed interval of $\mathbb{S}_{\bullet, \bullet}^\mu$ is depicted by a black dot. See also Fig. 3(a,b). Each segment $S = [h^-, h^+)$ of $\mathbb{S}_{\bullet, \bullet}^\mu$ is in bijection with the open interval $(h^-, h^+)$ of $\mathbb{S}_{\bullet, \bullet}^\rho$. Each adjacency link between two segments $S_1 = [h^-, h)$, $S_2 = [h, h^+)$ is in bijection with the singular closed interval $\{h\}$ of $\mathbb{S}_{\bullet, \bullet}^\mu$. (c) The graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$. Each vertex of $\mathcal{V}^\mu$ (depicted by a white dot) is a segment of $\mathbb{S}_{\bullet, \bullet}^\mu$. Each edge of $\mathcal{E}^\mu$ (depicted by a black line) is an adjacency link between two successive segments of $\mathbb{S}_{\bullet, \bullet}^\mu$. The graph $\mathfrak{G}^\mu$ is a $\sigma^\mu$-cycle graph (with $\sigma^\mu = 8$ in this toy example). This graph $\mathfrak{G}^\mu$ has the same structure as $(\mathbb{S}_{\bullet, \bullet}^\mu, \mathbb{S}_{\bullet, \bullet}^\rho)$ seen as a 1-complex.</figcaption></figure>

For each $S \in \mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}$, we denote by $\alpha(S)$ (resp. $\omega(S)$) the lowest (resp. greatest) value $\rho \in [\sqrt{0}, \mu]$ such that $S \in \mathbb{S}_{\bullet, \bullet}^\rho$. It is plain that for any other $\rho \in [\alpha(S), \omega(S)]$, we also have $S \in \mathbb{S}_{\bullet, \bullet}^\rho$.

**Remark 17** For each $\rho \in [\sqrt{0}, \mu]$, the size of set $\mathfrak{R}_{\mathbb{Z}^2}^\rho$ of the $\rho$-rotations is $|\mathbb{S}_{\bullet, \bullet}^\rho| = O(\rho^3)$. All the sets $\mathfrak{R}_{\mathbb{Z}^2}^\rho$ are disjoint. It follows that the size of $\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}$ is $O(\mu^5)$ as $||[\sqrt{0}, \mu]| = O(\mu^2)$. Each element $S \in \mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]}$ may then model many distinct $\rho$-rotations. More precisely, it models $(\omega(S))^2 - (\alpha(S))^2 + 1$ distinct $\rho$-rotations, for $\rho \in [\alpha(S), \omega(S)]$.

Based on Rems. 16–17, in the tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$, a $\rho$-rotation $R_\theta^\rho$ ($\theta \in \mathbb{U}$) is modeled by the couple $(S, \rho) \in \mathbb{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]} \times [\sqrt{0}, \mu]$ such that $S = [h, h') \in \mathbb{S}_{\bullet, \bullet}^\rho$ and $h \le \theta < h'$.

In addition to being a partition tree, we establish hereafter that $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is a watershed tree, which is defined based on an edge weighted graph (Sect. 7.3).

If $\mu = \sqrt{0}$, the tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \sqrt{0}]})$ is reduced to a unique element and can then be trivially defined as a watershed tree. Let us now suppose that $\mu > \sqrt{0}$. Let us define the (undirected, irreflexive) graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ such that:

- the set of vertices $\mathcal{V}^\mu$ is composed by the segments of $\mathbb{S}_{\bullet, \bullet}^\mu$;

- the set of edges $\mathcal{E}^\mu$ is composed by the adjacency links between the segments of $\mathbb{S}_{\bullet, \bullet}^\mu$.

Here, since all the elements of $\mathbb{S}_{\bullet, \bullet}^\mu$ are segments, two distinct vertices $S_1 = [h_1^-, h_1^+)$, $S_2 = [h_2^-, h_2^+)$ are adjacent iff $h_1^+ = h_2^-$. See Fig. 11(a,c).

**Remark 18** The graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ is a $\sigma^\mu$-cycle graph (with $\sigma^\mu = |\mathbb{H}^\mu|$, i.e. it is a connected graph where each vertex is of degree 2. See Fig. 11(c).)
<figure><img src="image_13.png" /><figcaption>**Fig. 12** (a) The sets ($\mathcal{S}_{\bullet, \bullet}^\mu$, $\mathcal{S}_\bullet^\mu$) for $\rho$ from $\sqrt{0}$ (innest part of the circles) to $\sqrt{5}$ (outest part of the circles). Each open interval of $\mathcal{S}_{\bullet, \bullet}^\mu$ is depicted by a black arc. Each singular closed interval of $\mathcal{S}_\bullet^\mu$ is depicted by a dot. For $\rho = \sqrt{0}$ (central circle), we have $\mathcal{S}_{\bullet, \bullet}^\mu = \{\mathbb{U}\}$ and $\mathcal{S}_\bullet^\mu = \emptyset$. For $\rho = \sqrt{5}$ (external circle), we have $|\mathcal{S}_{\bullet, \bullet}^\mu| = |\mathcal{S}_\bullet^\mu| = 8$ (i.e. 8 hinge angles) and $(\mathcal{S}_{\bullet, \bullet}^\mu, \mathcal{S}_\bullet^\mu)$ corresponds to $(\mathcal{S}_{\bullet, \bullet}^\mu, \mathcal{S}_\bullet^\mu)$ in Fig. 11(b). For each hinge angle $h \in \mathbb{H}^\mu$, we assign a value $\Delta(h)$ as defined in Eq. (48), with the following colour code: $\Delta(h) = \sqrt{1}$ (red); $\Delta(h) = \sqrt{2}$ (orange); $\Delta(h) = \sqrt{3}$ (yellow); $\Delta(h) = \sqrt{4}$ (green); $\Delta(h) = \sqrt{5}$ (blue). A series of dots of same angular position correspond to a unique hinge angle $h$. The color corresponds to the value $\Delta(h)$ at which this hinge angle appeared. The hinge angle persists for greater values, justifying the series of dots from the most central one to the most radial one. (b) The graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$. See also Fig. 11(c). Each vertex of $\mathcal{V}^\mu$ (depicted by a white dot) is a segment of $\mathcal{S}_{\bullet, \bullet}^\mu$, in bijection with an open interval of $\mathcal{S}_{\bullet, \bullet}^\mu$ in (a). Each edge of $\mathcal{E}^\mu$ (depicted by a line) is an adjacency link between two successive segments of $\mathcal{S}_\bullet^\mu$ on (a). To each edge of $\mathcal{E}^\mu$, we assign the $\Delta$ value induced by Eq. (48). The colour code is the same as in (a).</figcaption></figure>

In particular, if two adjacent vertices $S_1 = [h^-, h)$, $S_2 = [h, h^+)$ are merged in $\mathfrak{G}^\mu$, the newly created vertex $S = [h^-, h^+]$ still models a segment, whereas the modified graph $\mathfrak{G}^{\mu \oplus 1}$ becomes a $(\sigma^\mu - 1)$-cycle graph.

**Remark 19** We observe that:

- the set of vertices $\mathcal{V}^\mu = \mathcal{S}_{\bullet, \bullet}^\mu$ is in bijection with $\mathcal{S}_{\bullet, \bullet}^\mu$ (Rem. 5); and

- the set of edges $\mathcal{E}^\mu$ is in bijection with $\mathcal{S}_\bullet^\mu$ (from the definition of adjacency given above).

Then, the graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ has the same structure as the couple $(\mathcal{S}_{\bullet, \bullet}^\mu, \mathcal{S}_\bullet^\mu)$ that can be seen as a 1-complex model where the 1-faces are gathered in $\mathcal{S}_{\bullet, \bullet}^\mu$ and the 0-faces in $\mathcal{S}_\bullet^\mu$, respectively. In particular, $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ and $(\mathcal{S}_{\bullet, \bullet}^\mu, \mathcal{S}_\bullet^\mu)$ provide the same modeling of the topological structure of the unit circle associated to $\mathbb{U}$ and subdivided by $\mathbb{H}^\mu$ in the 1-dimensional frameworks of digital topology [16] and cellular complexes [17], respectively. See Fig. 11(b,c).

We endow the set of edges $\mathcal{E}^\mu$ with a valuation. To this end, let us first define the function

$$ \left| \Delta : \mathbb{H}^\mu \to \sqrt{\mathbb{N}} \right. \\ \left. h \mapsto \min \left\{ \rho \in [\sqrt{0}, \mu] \mid h \in \mathbb{H}^\rho \right\} \right| \qquad (48) $$

which associates to each hinge angle $h \in \mathbb{H}^\mu$ the radius $\rho \in [\sqrt{0}, \mu]$ of the smallest Euclidean ball $\mathcal{B}^\rho$ that contains

<figure><img src="image_14.png" /><figcaption>**Fig. 13** The watershed tree $\mathfrak{T}(\mathbb{R}_{Z^2}^{\sqrt{0}, \mu})$ associated to the graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ endowed with the valuation $\Delta$ of Fig. 12(b) which models the hierarchy of partitions of Fig. 12(a). (a) The watershed tree viewed as the progressive (bottom-up) collapsing of the graph $\mathfrak{G}^\mu$ from $\rho = \mu = \sqrt{5}$ to $\sqrt{0}$. The layer at $\rho = \mu = \sqrt{5}$ corresponds to $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ (see Fig. 12(b)). Each layer at value $\rho \in [\sqrt{0}, \sqrt{4}]$ corresponds to the collapsing of the graph of the layer at value $\rho \oplus 1$ by merging vertices that share an edge of $\Delta$ value $\rho \oplus 1$. (c) The watershed tree of (a) viewed as a partition tree. The layer at $\rho = \mu = \sqrt{5}$ corresponds to the external partition in Fig. 12(a). Each segment of $\mathcal{S}_{\bullet, \bullet}^{\sqrt{5}}$ corresponds to a vertex in (a). (b) The watershed tree of (a) seen in a compact way. Each set of equal vertices of the successive graphs (linked by thin vertical edges in (a)) is depicted only once. (d) The watershed tree of (b) seen in a compact way. Each set of equal segments of the successive partitions (linked by thin vertical edges in (b)) is depicted only once.</figcaption></figure>

the point $(p, q) \in \mathbb{Z}^2$ associated to the triplet $(p, q, k)$ which induces this hinge angle $h = \eta(p, q, k)$ (Sect. 4.2).

**Remark 20 ([30])** Let $S = [h, h') \in \mathcal{S}_{\bullet, \bullet}^{[\sqrt{0}, \mu]} \setminus \mathcal{S}_{\bullet, \bullet}^{\sqrt{0}}$. We have

$$ \alpha(S) = \max \{\Delta(h), \Delta(h')\} \qquad (49) $$

**Property 21 (Stated in [30] without proof)** Let $h \in \mathbb{H}^\mu$. Let $\mathbf{t} = (p_x, p_y, k) \in \mathbb{T}$ be the prime generator of $h$, associated to the point $\mathbf{p} = (p_x, p_y) \in \mathbb{Z}^2$. We have $\Delta(h) = \|\mathbf{p}\|_2$.

The function $\Delta$ is defined on $\mathbb{H}^\mu$. Since $\mathbb{H}^\mu$ and $\mathcal{S}_\bullet^\mu$ are in bijection, it can be redefined on $\mathcal{S}_\bullet^\mu$. Finally, since $\mathcal{S}_\bullet^\mu$ and $\mathcal{E}^\mu$ are also in bijection, it can also be redefined on $\mathcal{E}^\mu$. This leads to a valuation $\Delta$ of the edges of the graph $\mathfrak{G}^\mu$. We
call the valued graph ($\mathfrak{G}^\mu, \Delta$) the $\mu$-rotation saliency graph (Fig. 12).

Now, let us consider the two sets $S_{\bullet, \infty}^{\mu} (\mu \ge \sqrt{1})$ and $S_{\bullet, \infty}^{\mu \cap 1}$. Let $S = [h, h') \in S_{\bullet, \infty}^{\mu}$. From Rem. 20, Eq. (49), if $\alpha(S) < \mu$, then we have $S \in S_{\bullet, \infty}^{\mu \cap 1}$. By contrast, if $\alpha(S) = \mu$ (we cannot have $\alpha(S) > \mu$) then we have $\Delta(h) = \mu$ or $\Delta(h') = \mu$. Let us suppose that $\Delta(h) = \mu$ (the same reasoning holds for $h'$, and both may hold simultaneously). Then, from Prop. 21, there is no triplet $t = (p_x, p_y, k) \in \mathbb{T}$ such that $\|(p_x, p_y)\|_2 = \mu \not\equiv 1$ and $h = \eta(t)$. It follows that the unique $S' \in S_{\bullet, \infty}^{\mu \cap 1}$ such that $S \subset S'$ is a vertex of the graph $\mathfrak{G}^{\mu \cap 1}$ built by merging (at least) $S$ and the unique vertex $\hat{S} = [\hat{h}, h)$, that shares with $S$ an edge of valuation $\mu$. The same holds for all the edges of valuation $\mu$. It follows, by induction, that the construction of the successive sets $S_{\bullet, \infty}^{\rho}$ for $\rho$ from $\mu$ down to $\sqrt{0}$ relies on the paradigm of the watershed tree. See Fig. 13. This justifies the following result.

**Proposition 22 (stated in [30] with partial proof)** Let $\mu \in \sqrt{\mathbb{N}}$. The combinatorial space of $\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}$, namely the partition tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is the watershed tree of the $\mu$-rotation saliency graph $(\mathfrak{G}^\mu, \Delta)$.

## 9 Discrete rotation tree construction: Bottom-up

From the previous section, the combinatorial space $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is a watershed tree. It is then possible to rely on watershed tree construction algorithms to build it. We first describe some initial steps dedicated to build the objects required for the construction of $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ (Sect. 9.1). Then, we propose an algorithm for this construction (Sect. 9.2).

### 9.1 Initialization

The algorithm takes as input a value $\mu \in \sqrt{\mathbb{N}}$, which is the size of a Euclidean ball $B^\mu$ in $\mathbb{Z}^2$. The output of the initialization step, used as input for the watershed tree construction, is the $\mu$-rotation saliency graph (Fig. 12(b)), composed of:

- the graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$;

- the edge valuation function $\Delta : \mathcal{E}^\mu \to \sqrt{\mathbb{N}}$.

The successive steps of this initialization are as follows.

1. Building the Euclidean ball $B^\mu \subset \mathbb{Z}^2$ (Eq. (16)). The size of $B^\mu$ is $\Theta(\mu^2)$ and the time cost for its construction is $\Theta(\mu^2)$.

2. Building the set of triplets $\mathbb{T}^\mu \subset \mathbb{Z}^3$ (Eq. (18)). The size of $\mathbb{T}^\mu$ is $\Theta(\mu^3)$ and the time cost for its construction is $\Theta(\mu^3)$.

3. Sorting $\mathbb{T}^\mu$ with respect to $\le_T$ (Eq. (24)) and discarding the triplets $t = (p_x, p_y, k)$ which are not prime for a given point $(p_x, p_y)$ (Prop. 2). The time cost for this sorting is $\Theta(\mu^3 \log \mu)$.

4. Building the set of hinge angles $\mathbb{H}^\mu \subset \mathbb{U}$ from $\mathbb{T}^\mu$, naturally sorted with respect to $\le$ (Eq. (24)). The size of $\mathbb{H}^\mu$ is $O(\mu^3)$. Its construction has a time cost $O(0)$ since the sets $\mathbb{H}^\mu$ and $\mathbb{T}^\mu$ (after discarding redundant triplets) are in bijection.

5. Building the graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$. Since $\mathfrak{G}^\mu$ is a $\sigma^\mu$-cycle graph, with vertices and edges in bijection with $\mathbb{H}^\mu$, the size of $\mathfrak{G}^\mu$ is $O(\mu^3)$ and its construction has a time cost $O(\mu^3)$.

6. Building $\Delta : \mathbb{H}^\mu \to \sqrt{\mathbb{N}}$ from $\mathbb{T}^\mu$ (Prop. 21). The size of $\Delta$ is $O(\mu^3)$ and the time cost for its construction is $\Theta(\mu^3)$ if it is built in parallel to $\mathbb{H}^\mu$.

7. Building a second occurrence of $\mathbb{H}^\mu$, sorted with respect to $\Delta$ (Eq. (48)). This construction / sorting has a time cost $O(\mu^3 \log \mu)$.

The complexity analysis of these steps justifies the following result.

**Proposition 23 (stated in [30] with partial proof)** The construction of $\mathfrak{G}^\mu$ and $\Delta$, both of size $O(\mu^3)$, has a time cost $\Theta(\mu^3 \log \mu)$.

### 9.2 Watershed tree construction

We present, in Alg. 1, a version of the watershed tree construction process adapted to the cycle graph structure of $\mathfrak{G}^\mu$. The first part of the process (Lines 1–19) builds a binary partition tree in a watershed-like fashion. The second part of the process (Lines 20–27) simplifies this binary partition tree by merging the vertices that correspond to a same element in the watershed tree, leading to a potentially non-binary structure. Hereafter are some comments on this bottom-up algorithm.

- We use the following notations, in this algorithm and the next ones:

- “$A \equiv B$” means “$A$ is equivalent to / handled as $B$”;

- “$A = B$” means “$A$ is equal to $B$”;

- “$A := B$” means “$A$ is set with $B$”;

- “$A \to B$” means “$B$ is removed from $A$”;

- “$A \leftarrow B$” means “$B$ is added to $A$”.

- Input: The graph $\mathfrak{G}^\mu = (\mathcal{V}^\mu, \mathcal{E}^\mu)$ is handled as $(S_{\bullet, \infty}^{\mu}, \mathbb{H}^\mu)$. In other words, each vertex of the graph is viewed as the corresponding segment, whereas each edge between two vertices is viewed as the hinge angle between the two corresponding segments. By side effect, the valuation $\Delta$, that acts on the edges, is also handled as the valuation that acts on the hinge angles.

- Output: The algorithm computes the watershed tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ (Fig. 13(b) for a graph-based representation and (d) for a segment-based representation). It also computes the values $\alpha(S)$ and $\omega(S)$ for any $S \in S_{\bullet, \infty}^{[\sqrt{0}, \mu]}$. Indeed, each $\rho$-rotation $(\rho \in [\sqrt{0}, \mu])$ is associated not only to a segment
<caption>**Algorithm 1:** Building $\mathfrak{Z}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu]})$ (bottom-up)</caption>

**Input:** $\mathfrak{G}^{\mu} = (\mathcal{V}^{\mu}, \mathcal{E}^{\mu}) \equiv (\mathbb{S}_{\bullet, \infty}^{\mu}, \mathbb{H}^{\mu})$ with $\mu \ge \sqrt{1}$
**Input:** $\Delta : \mathcal{E}^{\mu} \to \sqrt{\mathbb{N}} \equiv \Delta : \mathbb{H}^{\mu} \to \sqrt{\mathbb{N}}$
**Output:** $\mathfrak{Z}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu]}) = (\mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}, \triangleleft)$
**Output:** $\alpha, \omega : \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]} \to \sqrt{\mathbb{N}}$
1. $(\mathcal{V}, \mathcal{E}) := (\mathcal{V}^{\mu}, \mathcal{E}^{\mu})$
2. $(\mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}, \triangleleft) := (\mathcal{V}^{\mu}, \emptyset)$
3. **foreach** $S \in \mathcal{V}$ **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;**if** $|S| = 1$ **then**
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathcal{E} \to h = \arg_{\mathcal{E}} \max_{\Delta} \| \mathcal{E} \text{ is sorted w.r.t. } \Delta \leqno{\text{6}} $$
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ S := \{[h^{-}, h), [h, h^{+})\} \subset \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]} \leqno{\text{7}} $$
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $|S| = 1$ **then**
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \alpha(S^{*}) := \sqrt{0} \text{ where } S = \{S^{*}\} \leqno{\text{9}} $$
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ S := [h^{-}, h^{+}) \leqno{\text{11}} $$
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \omega(S) := \Delta(h) \ominus 1 \leqno{\text{12}} $$
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathcal{V} \leftarrow S \leqno{\text{13}} $$
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]} \leftarrow S \text{ // } \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]} \text{ is sorted w.r.t. } \omega \leqno{\text{14}} $$
14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $S^{*} \in S$ **do**
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathcal{V} \to S^{*} \leqno{\text{16}} $$
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \alpha(S^{*}) := \Delta(h) \leqno{\text{17}} $$
17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \triangleleft \leftarrow (S^{*}, S) \leqno{\text{18}} $$
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**until** $|\mathcal{E}| = 0$
19. &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $S \in \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}$ **by increasing values of** $\omega(S)$ **do**
20. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\alpha(S) > \omega(S)$ **then**
21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]} \to S \leqno{\text{22}} $$
22. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \triangleleft \to (S, S') \leqno{\text{23}} $$
23. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $S'' \triangleleft S$ **do**
24. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \triangleleft \to (S'', S) \leqno{\text{25}} $$
25. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \triangleleft \to (S'', S') \leqno{\text{26}} $$

---

$S$ but also to a value in $[\alpha(S), \omega(S)]$ (Fig. 13(a,c) where a vertex / segment can appear at various successive values $\rho$).

- Line 1: The graph that is progressively collapsed and updated accordingly is stored in $(\mathcal{V}, \mathcal{E})$, and initialized by $\mathfrak{G}^{\mu}$. In practice, one can directly act on $\mathfrak{G}^{\mu}$, and the time cost for this instruction is then $\Theta(0)$.

- Line 2: Each segment of $\mathcal{V}^{\mu}$ is a leaf of the tree $\mathfrak{Z}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu]})$ and is then added to $\mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}$. The time cost for this instruction is equal to the size $O(\mu^3)$ of $\mathbb{S}_{\bullet, \infty}^{\mu}$.

- Lines 3-4: Each segment $S \in \mathcal{V} = \mathbb{S}_{\bullet, \infty}^{\mu}$ has its value $\omega(S)$ set to $\mu$. In the complete (infinite) combinatorial structure of the discrete rotations $(\mathfrak{Z}(\mathfrak{R}_{Z^2}^{\star}))$, the true value of $\omega(S)$ may be greater than $\mu$. Here, it is set to $\mu$ since the computed tree $(\mathfrak{Z}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu]}))$ is bounded by $\mu$. The time cost for each instruction of Line 4 is $\Theta(1)$ and the number of iterations of Line 3 is the size $O(\mu^3)$ of $\mathbb{S}_{\bullet, \infty}^{\mu}$. The time cost for the block of instructions of Lines 3-4 is then $O(\mu^3)$.

- Lines 5-19: At each iteration of the repeat loop, a hinge angle is discarded from $\mathcal{E}$. These iterations end when $|\mathcal{E}| = 0$ (the test of this condition has a time cost $\Theta(1)$). The number of iterations is then the size $O(\mu^3)$ of $\mathbb{H}^{\mu}$. At each iteration of Line 5:

- Line 6: A hinge angle $h$ of maximal $\Delta$ value is chosen and removed from $\mathcal{E}$. Since $\mathbb{H}^{\mu}$ has been sorted with respect to $\Delta$, the time cost of this instruction is $\Theta(1)$.

- Line 7: The set $S$ of segments of $\mathcal{V}$ adjacent by $h$ is defined. This set is generally of size 2. The only case where it is of size 1 is when the graph $(\mathcal{V}, \mathcal{E})$ is a 1-cycle graph, which happens once at the last iteration of the loop. The time cost of this instruction is $\Theta(1)$.

- Lines 8-19: Two cases can occur: either $|S| = 1$ (Lines 8-9) or $|S| = 2$ (Lines 10-18). The test of this condition has a time cost $\Theta(1)$.

• Lines 8-9 (First case: $|S| = 1$): This case occurs at the last iteration of the repeat loop. At this stage, the graph $(\mathcal{V}, \mathcal{E})$ is composed by one hinge angle $h$ and one segment $[h, h)$. In other words, this segment is $\mathcal{U}$, that already corresponds to the root of the tree and is already present in $\mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}$. It is then only required to set its $\alpha$ value to $\sqrt{0}$ (Line 9). This instruction has a time cost $\Theta(1)$.

• Lines 10-18 (Second case: $|S| = 2$): In that case, there exist two distinct segments $[h^{-}, h)$ and $[h, h^{+})$ adjacent by $h$. We create a new segment $[h^{-}, h^{+})$ by merging $[h^{-}, h)$ and $[h, h^{+})$ (Line 11). We set the value $\alpha$ for $[h^{-}, h)$ and $[h, h^{+})$ and the value $\omega$ for $[h^{-}, h^{+})$ (Lines 12 and 17). (Note that the $\omega$ value of $[h^{-}, h)$ and $[h, h^{+})$ had been set at their creation, at a previous iteration.) The segment $[h^{-}, h^{+})$ replaces the two segments $[h^{-}, h)$ and $[h, h^{+})$ in the graph $(\mathcal{V}, \mathcal{E})$ (Lines 13 and 16). The tree in construction is updated by adding the new segment $[h^{-}, h^{+})$ in $\mathbb{S}_{\bullet, \infty}^{[\sqrt{0},\mu]}$ (Line 14) and by connecting the two segments $[h^{-}, h)$ and $[h, h^{+})$ to it (Line 18). All these instructions have a time cost $\Theta(1)$, so the whole block also has a time cost $\Theta(1)$.

Overall, the block of the Lines 5-19 has a time cost $O(\mu^3)$.

- Lines 20-26: At each iteration of the loop (Line 20), a segment of $\mathcal{V}$ is handled, with the guarantee that its parent has already been processed. The number of iterations is $O(\mu^3)$. At each iteration:

- Line 21-26: If the $\alpha$ value of the segment is strictly greater than its $\omega$ value, then this segment (i) has been created by merging two segments via a hinge angle of a given $\Delta$ value and (ii) has been merged with another segment at the same $\Delta$ value. In other words, this “binary” element does not exist in the
watershed tree, and then it has to be skipped in $\mathfrak{Z}(\mathfrak{R}^{\lfloor\sqrt{0},\mu\rfloor})$. This whole process has a time cost $O(\mu^3 \log \mu)$ with $O(\mu^3 \log \mu)$ for the processing of the leaves and $O(\mu^3)$ for the processing of the other vertices.

The removal of this segment (Line 22) and the update of the edges accordingly (Lines 23–26) have a time cost $\Theta(1)$. The test of the condition of Line 21 has a time cost $\Theta(1)$. (Note that if the $\alpha$ value of the segment is lower than or equal to its $\omega$ value, then this segment is indeed a vertex of the watershed tree, and then nothing has to be done.)

Overall, the block of the Lines 20–26 has a time cost $O(\mu^3)$.

These elements justify the following result.

**Proposition 24 (stated in [30] with partial proof)** *The construction of $\mathfrak{Z}(\mathfrak{R}^{\lfloor\sqrt{0},\mu\rfloor})$, of size $O(\mu^3)$, from $\mathfrak{B}^\mu$ and $\Delta$, has a time cost $O(\mu^3)$. Its construction ex nihilo has a time cost $O(\mu^3 \log \mu)$.*

## 9.3 The case of bijective $\rho$-rotations

Let us now come back to the issue of modeling the bijective $\rho$-rotations, either as the restrictions of bijective discrete rotations (Sect. 6.1) or as injective $\rho$-rotations from a Euclidean ball to its image (Sect. 6.2).

Let us consider the first definition for the bijectivity of $\rho$-rotations. In Sect. 6.1, we stated that it is possible to determine which $\rho$-rotations are bijective for a given value $\rho \in \sqrt{\mathbb{N}}$ by sorting the set $\mathbb{H}^\rho \cup \mathbb{B}^\rho$ composed by the hinge angles ($\mathbb{H}^\rho$) that appear within the Euclidean ball $\mathbb{B}^\rho$ and the “first” angles ($\mathbb{B}^\rho$) that induce bijective rotations. This set $\mathbb{H}^\rho \cup \mathbb{B}^\rho$ is finite. More precisely, we have $|\mathbb{H}^\rho| = O(\rho^3)$ and $|\mathbb{B}^\rho| = O(\rho)$. Since two hinge angles (resp. a hinge angle and a Pythagorean angle) can be compared with a time cost $\Theta(1)$ [28] (resp. [36]), sorting $\mathbb{H}^\rho \cup \mathbb{B}^\rho$, and thus determining the bijective $\rho$-rotations has a time cost $O(\rho^3 \log \rho)$.

From Eq. (35), for any $\theta \in \mathbb{U}$ and any $\rho_1, \rho_2 \in \sqrt{\mathbb{N}}$, we have

$$ (\rho_1 \le \rho_2) \wedge (R_{\theta}^{\rho_2} \in \mathfrak{B}_{\mathbb{Z}^2}^{\rho_2}) \implies (R_{\theta}^{\rho_1} \in \mathfrak{B}_{\mathbb{Z}^2}^{\rho_1}) \quad (50) $$

Let us set the Boolean function $\beta : \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor} \to \{\perp, \top\}$ that characterizes the bijectivity of each $S \in \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor}$ and then consider each bijective $\rho$-rotation for $\rho \in [\sqrt{0}, \mu]$. From Eq. (50), it follows that for any $S \in \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor} \setminus \mathbb{S}_{\mathbb{Z}^2}^{\mu}$, we have

$$ \beta(S) = \bigvee_{S' \prec_S S} \beta(S') \quad (51) $$

Then, we can build the function $\beta$ over $\mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor}$ from the tree $\mathfrak{Z}(\mathfrak{R}^{\lfloor\sqrt{0},\mu\rfloor})$ by:

- initializing $\beta$ on the set of leaves $\mathbb{S}_{\mathbb{Z}^2}^{\mu}$ (via the analysis of $\mathbb{H}^\mu \cup \mathbb{B}^\mu$); and

- propagating the computation of $\beta$ in $\mathfrak{Z}(\mathfrak{R}^{\lfloor\sqrt{0},\mu\rfloor})$ from the leaves up to the root thanks to Eq. (51).

Now, let us consider the second definition for the bijectivity of $\rho$-rotations, based on injectivity (Sect. 6.2). From Eq. (39), for any $\theta \in \mathbb{U}$ and any $\rho_1, \rho_2 \in \sqrt{\mathbb{N}}$, we have

$$ (\rho_1 \le \rho_2) \wedge (R_{\theta}^{\rho_2} \in \mathfrak{Z}_{\mathbb{Z}^2}^{\rho_2}) \implies (R_{\theta}^{\rho_1} \in \mathfrak{Z}_{\mathbb{Z}^2}^{\rho_1}) \quad (52) $$

Similarly to the first definition of bijectivity, we would like to build a function $\iota$, analogue to $\beta$, that characterizes the injective $\rho$-rotations. Despite the fact that Eq. (52) has the same structure as Eq. (50), the construction of $\iota$ is not straightforward, compared to that of $\beta$. In particular, the difficulties to tackle are the following.

- The definition of $\iota$ requires a degree of precision greater than the definition of $\beta$. Indeed, $\beta$ can be defined on the segments of $\mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor}$ since all the $\rho$ rotations associated to a given segment $S \in \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor}$ are either bijective or non-bijective, by definition. By contrast, for a unique segment $S \in \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor}$ and two distinct $\rho_1, \rho_2 \in [\alpha(S), \omega(S)]$, the two $\rho_1$- and $\rho_2$-rotations associated to the couples $(S, \rho_1)$ and $(S, \rho_2)$, respectively, may be different in terms of (non)-injectivity. More precisely, there exists $\rho^* \in [\alpha(S), \omega(S)]$ such that each $\rho$-rotation associated to $(S, \rho)$ with $\rho \in [\alpha(S), \rho^*]$ (resp. $\rho \in [\rho^* \oplus 1, \omega(S)]$) is injective (resp. non-injective). In particular, this means that if $\rho^* < \omega(S)$, then there exists a point $\mathbf{p} \in \mathbb{Z}^2$ with $\|\mathbf{p}\|_2 = \rho^*$ such that the rotation $R_\theta$ associated to the segment $S$ is such that $R_\theta(\mathbf{p}) = R_\theta(\mathbf{q})$ with $\mathbf{q} \in \mathbb{Z}^2$ and $\|\mathbf{q}\|_2 < \rho^*$. In other words, the Boolean function that characterizes the injectivity of the $\rho$-rotations has to be defined as $\iota : \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor} \times \sqrt{\mathbb{N}} \to \{\perp, \top\}$ by contrast to $\beta : \mathbb{S}_{\mathbb{Z}^2}^{\lfloor\sqrt{0},\mu\rfloor} \to \{\perp, \top\}$.

- Contrary to the first definition of bijectivity, for which there is an efficient way to build the bijective $\mu$-rotations that form the leaves of $\mathfrak{Z}(\mathfrak{R}^{\lfloor\sqrt{0},\mu\rfloor})$ before a bottom-up propagation, there is no efficient way to build ex nihilo the injective $\mu$-rotations. It follows that a bottom-up strategy is not adapted to the modeling of the injective $\rho$-rotations.

These elements motivate the proposal of a second, top-down paradigm for the computation of the discrete rotations, in the general, bijective and injective cases.

# 10 Discrete rotation tree construction: Top-down

We now propose a generic approach for building in a top-down fashion, i.e. from the root to the leaves, the combinatorial structure of the $\rho$-rotations, and more generally those
that satisfy a (decreasing) Boolean criterion, such as the bi-
jective $\rho$-rotations. This approach mainly relies on two para-
digms: refining a partition (Sect. 10.1) and selecting a subset
of a partition (Sect. 10.2). We provide first a general incre-
mental algorithm in Sects. 10.3 (one step) and 10.4 (com-
plete), which is then specified for all, bijective and injective
cases, respectively, in Sect. 10.5.

10.1 Partition refinement

Let $A^\bullet$, $A^\circ \subset U$ be two finite sets of angles. Assuming that the elements of $A^\bullet$ and $A^\circ$ are sorted with respect to $\leq$, we set

$$
A^{\bullet} = \{a_i^{\bullet}\}_{i=0}^{\sigma^{\bullet}-1} \qquad (53)
$$

$$
A^{\circ} = \{a_i^{\circ}\}_{i=0}^{\sigma^{\circ}-1} \qquad (54)
$$

with $\sigma^\bullet, \sigma^\circ \in \mathbb{N}$. See Fig. 14(a).

Let $\Pi(A^\bullet)$, $\Pi(A^\circ) \subset 2^U$ be the two finite sets of segments induced by $A^\bullet$ and $A^\circ$, respectively. We set

$$
\Pi(A^{\bullet}) = \Pi^{\bullet} = \{[b_{i}^{\bullet}, c_{i}^{\bullet}]\}_{i=0}^{\sigma^{\bullet}-1} \quad (55)
$$

$$
\Pi(A^{\circ}) = \Pi^{\circ} = \{[b_{i}^{\circ}, c_{i}^{\circ}]\}_{i=0}^{\sigma^{\circ}-1} \quad (56)
$$

with

$$
a_i^\bullet = b_i^\bullet = c_{i-1[\sigma^\bullet]} \quad (0 \le i \le \sigma^\bullet - 1) \qquad (57)
$$

$$
a_i^\circ = b_i^\circ = c_{i-1[\sigma^\circ]} \quad (0 \le i \le \sigma^\circ - 1) \qquad (58)
$$

See Fig. 14(b). For the sake of concision, we write $\Pi(A^\bullet) = \Pi^\bullet$ and $\Pi(A^\circ) = \Pi^\circ$. More generally, $\Pi(A)$ will be defined as in Eqs. (55–58) for a set of angles $A \subset U$.

Let $\Pi^* \subseteq \Pi^\bullet$ be a subset of $\Pi^\bullet$. We set

$$
\Pi^* = \{[b_i^*, c_i^*] = [b_{\zeta(i)}, c_{\zeta(i)}^*] \in \Pi^*\}_{i=0}^{\sigma^*-1} \quad (59)
$$

where $\sigma^* \in \mathbb{N}$, $\sigma^* \le \sigma^\bullet$ and $\zeta$ is a strictly increasing application. See Fig. 14(c). The sets $\Pi^*$ and $\Pi^\circ$ are partitions of $U$. The set $\Pi^*$ is a general partition of $U$.

Let us consider the general partition

$$
\Pi = \bigwedge^{\mathcal{C}} \{\Pi^*, \Pi^\circ\} \qquad (60)
$$

i.e. the infimum of $\Pi^*$ and $\Pi^\circ$ in the lattice of the general partitions of $U$ induced by the refinement relation $\mathcal{C}$. In other words, $\Pi$ is the coarsest general partition that refines both $\Pi^*$ and $\Pi^\circ$ (see Fig. 14(c)), and is thus written as

$$
\Pi = \bigvee_{S \in \Pi^*} \bigwedge_{\mathcal{C}} \{S\}, \Pi^\circ \quad (61)
$$

$$
= \bigcup_{S \in \Pi^*} \bigwedge_{\mathcal{C}} \{S\}, \Pi^\circ \quad (62)
$$

<figure><img src="image_15.png" /><figcaption>**Fig. 14** (a) Two finite sets $A^\bullet$, $A^\circ$ (black dots) of angles of $U$ (red line). (b) The two partitions $\Pi^\bullet$ and $\Pi^\circ$ of $U$ induced by $A^\bullet$ and $A^\circ$, respectively. Each segment $S$ (horizontal line) of $\Pi^\bullet$ and $\Pi^\circ$ is of the form $S = [b, c)$ where $b \in S$ (depicted by a small vertical line) and $c \notin S$. (c) A general partition $\Pi^* \subseteq \Pi^\bullet$. Each segment $S \in \Pi^*$ is depicted by a distinct colour. The general partition $\Pi$ defined as the infimum of the general partition $\Pi^*$ and the partition $\Pi^\circ$ (see Eqs. (60–62)). For each (coloured) segment $S \in \Pi^*$, the partition $\Pi_S$ of $S$ defined as the infimum of $\{S\}$ and $\Pi^\circ$ is depicted with the same colour in $\Pi$ (see Eq. (63)). The whole general partition $\Pi$ is then defined as the union of all the $\Pi_S$ for $S \in \Pi^*$ (see Eq. (64)). (d) The general partition $\Pi$ and a general partition $\Pi_k \subset \Pi$ obtained by discarding from $\Pi$ the segments $S$ that do not satisfy a given criterion $\kappa$ (see Sect. 10.2).</figcaption></figure>

i.e. $\Pi$ is the supremum of the infima of each singleton parti-
tion $\{S\}$ for the segments $S$ of $\Pi^*$, and $\Pi^\circ$.

Now let us consider $S \in \Pi^*$ and set $A_S^\circ = A^\circ \cap S$. We denote by $\Pi_S$ the partition of $S$ induced by the set of angles $A_S^\circ$, namely

$$
\Pi_S = \bigwedge^{\mathcal{C}} \{S\}, \Pi^\circ \qquad (63)
$$

and then Eq. (61) is rewritten by using the union instead of
the supremum as follows

$$
\Pi = \bigcup_{S \in \Pi^*} \Pi_S \qquad (64)
$$

Based on this discussion, the process of defining in $\mathbb{U}$ the coarsest general partition $(\Pi)$ that refines a general partition $(\Pi^*)$ and a partition $(\Pi^\circ)$ is described in Funct. Refine.

Assuming that the elements of $\Pi^*$ and $\Pi^\circ$ are sorted, we
can make the following observations.

- Input: We suppose that none of $\Pi^*$ and $\Pi^\circ$ is the trivial partition $\{\mathbb{U}\}$. Indeed, if $\Pi^* = \{\mathbb{U}\}$ (resp. $\Pi^\circ = \{\mathbb{U}\}$), then we simply have $\Pi = \Pi^\circ$ (resp. $\Pi = \Pi^*$).

- Line 1: If we directly act on $\Pi^*$ then this instruction has a time cost $\Theta(0)$.
**Function Refine($\Pi^*, \Pi^°$)**

**Input:** $\Pi^*$: a general partition of $\mathbb{U}$

**Input:** $\Pi^° \equiv \mathbb{A}^°$: a partition of $\mathbb{U}$

**Output:** $\Pi$: the coarsest general partition refining $\Pi^*$ and $\Pi^°$

1. $\Pi := \Pi^*$

2. **foreach** $a^° \in \mathbb{A}^°$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists[a^-, a^+) \in \Pi$ **such that** $a^° \in (a^-, a^+)$ **then**

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \Pi \to [a^-, a^+) $$

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \Pi \leftarrow [a^-, a^°) $$

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \Pi \leftarrow [a^°, a^+) $$

7. **return** $\Pi$

**Function Select($\Pi, \kappa$)**

**Input:** $\Pi$: a general partition of $\mathbb{U}$

**Input:** $\kappa: 2^\mathbb{U} \to \{\perp, \top\}$: a Boolean criterion

**Output:** $\Pi_k$: the subset of $\Pi$ composed of the segments satisfying $\kappa$

1. $\Pi_k := \Pi$

2. **foreach** $S \in \Pi_k$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\neg \kappa(S)$ **then**

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \Pi_k \to S $$

5. **return** $\Pi_k$

- Lines 2–6: The for loop iterates $\Theta(|\Pi^°|)$ times.

- Lines 3–6: At each iteration, we test if $a^°$ lies strictly between the bounds of a segment of $\Pi$. If so, the time cost of the block of Lines 4–6 is $\Theta(1)$; otherwise, it is $\Theta(0)$.

- Lines 2–3: Since $\Pi^*$ and $\Pi^°$ are sorted, so is $\Pi$ during its construction. In such conditions, the time cost for carrying out all the tests of Line 3 for all the iterations of Line 2 is:

- $O(|\Pi^°| \log |\Pi^*|)$ if $\Pi^*$ is of an order of size strictly greater than $\Pi^°$ (since we proceed by dichotomy);

- $\Theta(|\Pi^°|)$ otherwise (since we scan $\Pi^*$ and $\Pi^°$ iteratively and in parallel).

These remarks justify the following result.

**Proposition 25** Let $\rho \in \sqrt{\mathbb{N}}$. Let $k \in \mathbb{N}$. Let $\Pi^*$ be a general partition and $\Pi^°$ be a partition as defined above. Let us suppose that $|\Pi^*| = \Theta(\rho^k)$ and $|\Pi^°| = \Theta(\rho)$. The time cost of Funct. Refine is

$$ \begin{cases} O(\rho \log \rho) & \text{if } k > 1 \\ O(\rho) & \text{if } k \le 1 \end{cases} \qquad (65) $$

## 10.2 Partition selection

Let $\Pi$ be a general partition defined as output of Funct. Refine. Let us consider a criterion $\kappa$ that associates a Boolean value to each segment of $\Pi$. The process of selection of the part of $\Pi$ composed by the segments that satisfy $\kappa$ (Fig. 14(d)) is given in Funct. Select and we have the following result.

**Function Build($\mathcal{S}_{\bullet, \cdot}^{\rho, \kappa}, \rho, \kappa$)**

**Input:** $\kappa: 2^\mathbb{U} \to \{\perp, \top\}$: a decreasing Boolean criterion

**Input:** $\rho \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$

**Input:** $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa}$: a general partition of $\mathbb{U}$ composed of the segments of $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top 1}}$ that satisfy $\kappa$

**Output:** $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa}$: the general partition of $\mathbb{U}$ composed of the segments of $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top 1}}$ that satisfy $\kappa$

1. Build and sort $\mathbb{H}^\rho$

2. $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa} := \text{Refine}(\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa}, \Pi(\hat{\mathbb{H}}^\rho))$

3. $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa} := \text{Select}(\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa}, \kappa)$

4. **return** $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top}, \kappa}$

**Proposition 26** Let $\rho \in \sqrt{\mathbb{N}}$. Let $k \in \mathbb{N}$. Let $\Pi$ be a general partition as defined above, supposing that $|\Pi| = \Theta(\rho^k)$. Let $\kappa: 2^\mathbb{U} \to \{\perp, \top\}$ be a Boolean criterion. The time cost of Funct. Select is $\Theta(K \cdot \rho^k)$ where $K$ is the time cost for evaluating $\kappa$ on a segment.

We say that a Boolean criterion $\kappa$ is decreasing if for all segments $S, S'$, we have

$$ (S \subseteq S') \implies (\neg \kappa(S') \Rightarrow \neg \kappa(S)) \qquad (66) $$

In the sequel, we will consider three instances of criteria $\kappa$, namely:

- $\kappa = \top$, the constant (true) criterion;

- $\kappa = \beta$, that characterizes bijective $\rho$-rotations;

- $\kappa = \iota$, that characterizes injective $\rho$-rotations.

These three criteria satisfy the property of decreasingness expressed in Eq. (66), that will be useful from an algorithmic point of view, as discussed in the next section.

## 10.3 Sketch of one iteration of the incremental algorithm

For any $\rho \in \sqrt{\mathbb{N}}$, we denote by $\mathcal{R}_{Z^2}^{\rho} \subseteq \mathcal{R}_{Z^2}^{\rho}$ the set of all the $\rho$-rotations that satisfy a decreasing Boolean criterion $\kappa$, and $\mathcal{S}_{\bullet, \cdot}^{\rho, \kappa} \subseteq \mathcal{S}_{\bullet, \cdot}^{\rho}$ the set of segments associated to $\mathcal{R}_{Z^2}^{\rho}$.

Let $\mu \in \sqrt{\mathbb{N}}$ be the maximal radius of the Euclidean ball on $\mathbb{Z}^2$ that we consider. We denote by $\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}$ the set of all the $\rho$-rotations that satisfy $\kappa$ for $\rho \in [[\sqrt{0}, \mu]]$ and $\mathfrak{T}(\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ the general partition tree that models $\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]}$. By abuse of notation, we still write $\mathcal{S}_{\bullet, \cdot}^{[\sqrt{0}, \mu]}$ the union of all the sets $\mathcal{S}_{\bullet, \cdot}^{\rho, \kappa}$ for $\rho \in [[\sqrt{0}, \mu]]$.

Let us suppose that $\mathfrak{T}(\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \rho^{\top 1}]})$ has been built and that we now want to extend it to build $\mathfrak{T}(\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \rho]})$. In other words, we want to add the elements of $\mathcal{S}_{\bullet, \cdot}^{\rho, \kappa}$ to the tree $\mathfrak{T}(\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \rho^{\top 1}]})$ and connect them to its leaves, namely the elements of $\mathcal{S}_{\bullet, \cdot}^{\rho^{\top 1}, \kappa}$. This operation constitutes the core of the top-down construction algorithm. Indeed, it is sufficient to apply it iteratively for $\rho \in [[1, \mu]]$ for building $\mathfrak{T}(\mathcal{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$.
Let us focus on the operation of extending $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\rho^{\perp 1}]})$ to $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\rho]})$. To carry out this task, we need two sets:

- $S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}$, which is a general partition of $\mathbb{U}$ available as (a part of) the set of leaves of $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\rho^{\perp 1}]})$; and

- $S_{\bullet, \bullet}^{\rho, \kappa}$, not yet available.

The first task consists of building $S_{\bullet, \bullet}^{\rho, \kappa}$. By definition, we have

$$ S_{\bullet, \bullet}^{\rho, \kappa} = \{S \in S_{\bullet, \bullet}^{\rho} | \kappa(S)\} \quad (67) $$

The partition $S_{\bullet, \bullet}^{\rho}$ is generated by the set of hinge angles $\mathbb{H}^{\rho} = \mathbb{H}^{\rho^{\perp 1}} \cup \hat{\mathbb{H}}^{\rho}$ where $\hat{\mathbb{H}}^{\rho}$ is the set of hinge angles generated by the points $\mathbf{p} \in \mathbb{Z}^2$ of norm $\|\mathbf{p}\|_2 = \rho$, i.e.

$$ \hat{\mathbb{H}}^{\rho} = \bigcup_{\mathbf{p} \in C^{\rho}} \hat{\mathbb{H}}^{\mathbf{p}} \quad (68) $$

with

$$ C^{\rho} = \{ \mathbf{q} \in \mathbb{Z}^2 | \|\mathbf{q}\|_2 = \rho \} \quad (69) $$

$$ \hat{\mathbb{H}}^{\rho} = \eta(\hat{\mathbb{T}}^{\rho}) \quad (70) $$

$$ \hat{\mathbb{T}}^{\rho} = \{ \mathbf{t} = (p_x, p_y, k) \in \mathbb{T} | \mathbf{p} = (p_x, p_y) \} \quad (71) $$

In particular, we have

$$ S_{\bullet, \bullet}^{\rho} = \Pi(\mathbb{H}^{\rho}) \quad (72) $$

$$ = \Pi(\mathbb{H}^{\rho^{\perp 1}} \cup \hat{\mathbb{H}}^{\rho}) \quad (73) $$

$$ = \bigcap_{\epsilon} \{ \Pi(\mathbb{H}^{\rho^{\perp 1}}), \Pi(\hat{\mathbb{H}}^{\rho}) \} \quad (74) $$

$$ = \bigcap_{\epsilon} \{ S_{\bullet, \bullet}^{\rho^{\perp 1}}, \Pi(\hat{\mathbb{H}}^{\rho}) \} \quad (75) $$

Based on the fact that $\kappa$ is decreasing, we have

$$ S_{\bullet, \bullet}^{\rho, \kappa} \subseteq \bigcap_{\epsilon} \{ S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}, \Pi(\hat{\mathbb{H}}^{\rho}) \} \quad (76) $$

More precisely, we have

$$ S_{\bullet, \bullet}^{\rho, \kappa} = \{ S \in \bigcap_{\epsilon} \{ S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}, \Pi(\hat{\mathbb{H}}^{\rho}) \} | \kappa(S) \} \quad (77) $$

The construction of $S_{\bullet, \bullet}^{\rho, \kappa}$ from $S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}$ and $\kappa$ can then be carried out as described in Funct. Build. The set of angles $\hat{\mathbb{H}}^{\rho}$ is built from the sets of angles $\hat{\mathbb{H}}^{\mathbf{p}}$ for all $\mathbf{p} \in C^{\rho}$. One may remark that:

- the size of $C^{\rho}$ is $O(1)$;

- $C^{\rho}$ can be built with a time cost $O(1)$ at the same time as the whole set $B^{\mu}$ with $\rho \in [[\sqrt{0}, \mu]]$;

- for each $\mathbf{p} \in C^{\rho}$, $\hat{\mathbb{H}}^{\mathbf{p}}$ is of size $O(\rho)$;

- for each $\mathbf{p} \in C^{\rho}$, $\hat{\mathbb{H}}^{\mathbf{p}}$ can be built and sorted with a time cost $O(\rho)$.

It follows that $\hat{\mathbb{H}}^{\rho}$ is of size $O(\rho)$ and can be built and sorted with a time cost $O(\rho)$. This, together with Props. 25–26, justifies the following result.

<caption>**Algorithm 2: Building $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu^2]})$ top-down.**</caption>

Input: $\mu \in \sqrt{\mathbb{N}}$ ($\mu > 0$)

Input: $\kappa: 2^{\mathbb{U}} \to \{\perp, \top\}$: a decreasing Boolean criterion

Output: $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu^2]})$

Output: $\alpha, \omega: S_{\bullet, \bullet}^{[\sqrt{0},\mu^2]} \to \mathbb{N}$

1. $\langle \alpha, \omega \rangle := \emptyset$

2. $S_{\bullet, \bullet}^{0, \kappa} := \{\mathbb{U}\}$

3. **for $\rho$ from 1 to $\mu$ do**

4. $\left\lfloor \begin{array}{l} S_{\bullet, \bullet}^{\rho, \kappa} := \text{Build}(S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}, \rho, \kappa) \\ \text{with side effects on } \langle \alpha, \omega \rangle \end{array} \right.$

5. **foreach $S \in S_{\bullet, \bullet}^{\mu, \kappa}$ do**

6. $\lfloor \omega(S) \rfloor := \mu$

**Proposition 27** Let $\rho \in \sqrt{\mathbb{N}}$. Let $k \in \mathbb{N}$. Let us suppose that $|S_{\bullet, \bullet}^{\rho, \kappa}| = \Theta(\rho^k)$. Let $\kappa: 2^{\mathbb{U}} \to \{\perp, \top\}$ be a decreasing Boolean criterion. The time cost of Funct. Build for computing $S_{\bullet, \bullet}^{\rho, \kappa}$ from $S_{\bullet, \bullet}^{\rho^{\perp 1}, \kappa}$ and $\kappa$ is

$$ \left\{ \begin{array}{ll} O(\rho \log \rho + K \cdot \rho^k) & \text{if } k > 1 \\ O(\rho + K \cdot \rho^k) & \text{if } k \le 1 \end{array} \right. \quad (78) $$

where $K$ is the time cost for evaluating $\kappa$ on a segment.

10.4 Complete algorithm

For any $\mu \in \sqrt{\mathbb{N}}$, the construction of the whole tree $\mathfrak{I}(\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu^2]})$ which models the space $\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu^2]}$ of all the $\rho$-rotations ($\rho \in [[\sqrt{0}, \mu]]$) that satisfy $\kappa$, is performed by iteratively applying Funct. Build for all $\rho \in [[1, \mu]]$. In particular, this provides us with all the segments of $S_{\bullet, \bullet}^{[\sqrt{0},\mu^2]}$ that correspond to rotations satisfying the criterion $\kappa$ associated to $\mathfrak{R}_{Z^2}^{[\sqrt{0},\mu^2]}$. However, two pieces of information are still missing:

- the links between these segments, i.e. the relation $\langle$;

- the values $\alpha(S), \omega(S) \in [[\sqrt{0}, \mu]]$ associated to each segment $S \in S_{\bullet, \bullet}^{[\sqrt{0},\mu^2]}$, that characterize all the $\rho$-rotations associated to $S$ for $\rho \in [[\alpha(S), \omega(S)]]$.

In practice, the definition of these elements is straightforward by slightly enriching the above functions.

Regarding the definition of $\langle$ and $\alpha$, it is sufficient to add the instructions

$$ \langle \leftarrow ([a^{-}, a^{\circ}), [a^{-}, a^{+}]) \quad (79) $$

$$ \langle \leftarrow ([a^{\circ}, a^{+}), [a^{-}, a^{+}]) \quad (80) $$

and

$$ \alpha \leftarrow ([a^{-}, a^{\circ}), \rho) \quad (81) $$

$$ \alpha \leftarrow ([a^{\circ}, a^{+}), \rho) \quad (82) $$

in the block of Lines 3–6 of Funct. Refine. This requires to modify the input / output of this function accordingly. (Note
that we may further remove the edges $(S, [a^-, a^+])$ and the $\alpha$ values $(S, \rho)$ if the segment $S$ is discarded by Funct. Select (Line 3 in Funct. Build) after Funct. Refine (Line 2 in Funct. Build).

Regarding the definition of $\omega$, it is sufficient to add the instruction

$$ \omega \leftarrow ([a^-, a^+], \rho) \qquad (83) $$

in the block of Lines 3–6 of Funct. Refine; and the instruction

$$ \omega \leftarrow (S, \rho \ominus 1) \qquad (84) $$

in the block of Lines 3–4 of Funct. Select. Note that in Funct. Refine, for the segments $S$ such that $\alpha(S) \ominus 1 = \omega(S)$, i.e. the segments created and removed during the same execution of Funct. Refine, we must not only remove $\alpha(S)$, $\omega(S)$ and $S \prec S''$, but also update $\prec$ for the two segments $S' \prec S$ by substituting $S' \prec S''$ to $S' \prec S$. In Funct. Refine, for the segments $S$ such that $\alpha(S) \ominus 1 = \omega(S)$, we simply remove $\alpha(S)$, $\omega(S)$ and $S \prec S''$. Note that each one of these additional instructions has a time cost $\Theta(1)$.

From now on, we consider Functs. Refine, Select and Build modified as described above. The complete construction process, derived from these functions is provided in Alg. 2. (Note that the $\omega$ values for the leaves of the tree (Lines 5–6) are set the same way as in Alg. 1.) We have the following result thanks to Prop. 27.

**Proposition 28** Let $\mu \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$. Let $k \in \mathbb{N}$. Let us suppose that for each $\rho \in [[\sqrt{0}, \mu]]$, we have $|\mathbb{S}_{\bullet, \bullet}^{\rho, \kappa}| = \Theta(\rho^k)$. Let $\kappa : 2^{\mathbb{U}} \to \{\perp, \top\}$ be a decreasing Boolean criterion. The time cost of Alg. 2 for computing $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ with respect to $\kappa$ is

$$ \begin{cases} O(\mu^3 \log \mu + K \cdot \mu^{k+2}) & \text{if } k > 1 \\ O(\mu^3 + K \cdot \mu^{k+2}) & \text{if } k \le 1 \end{cases} \qquad (85) $$

where $K$ is the time cost for evaluating $\kappa$ on a segment.

## 10.5 The case of the general and bijective discrete rotations

The generic process described in Alg. 2 can build any tree $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ modeling the space of all the $\rho$-rotations $(\rho \in [[\sqrt{0}, \mu]])$ that satisfy a given decreasing Boolean criterion $\kappa$. The setting of this criterion $\kappa$ allows to choose the family of the $\rho$-rotations that we want to investigate.

In this study, we are interested by three families:

- all the $\rho$-rotations;

- the bijective $\rho$-rotations, defined as the restrictions of bijective discrete rotations (Sect. 6.1);

- the injective $\rho$-rotations (Sect. 6.2).

### 10.5.1 The general discrete rotations

Let us first consider the case of the general discrete rotations, i.e. all the possible $\rho$-rotations for $\rho \in [[\sqrt{0}, \mu]]$. These $\rho$-rotations are characterized by the trivial Boolean criterion $\kappa$ such that $\kappa(S) = \top$ for any segment $S$. The time cost for assessing $\kappa$ is then $\Theta(0)$, i.e. $K = 0$ with the previous notations.

We also know that in that case we have, for any $\rho \in [[\sqrt{0}, \mu]]$, $\mathbb{S}_{\bullet, \bullet}^{\rho, \kappa} = \mathbb{S}_{\bullet, \bullet}^{\rho}$. It follows that $|\mathbb{S}_{\bullet, \bullet}^{\rho, \kappa}| = O(\rho^3)$ (i.e. $k = 3$). Based on these elements, we have the following result as a corollary of Prop. 28.

**Corollary 29** Let $\mu \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$. The time cost of Alg. 2 for computing $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is $O(\mu^3 \log \mu)$.

In particular, the proposed (top-down) approach of Alg. 2 has the same time cost as the (bottom-up) approach of Alg. 1.

### 10.5.2 The bijective discrete rotations

Let us now consider the case of the bijective discrete rotations, i.e. all the $\rho$-rotations for $\rho \in [[\sqrt{0}, \mu]]$, which are restrictions of bijective rotations. These $\rho$-rotations are characterized by the Boolean criterion $\kappa = \beta$ (Sect. 9.3). This criterion $\beta$ can be computed for a segment $S$ with a time cost $\Theta(1)$ provided that the values of $\mathbb{B}^\rho$ be stored in the associated segments $\mathbb{S}_{\bullet, \bullet}^{\rho, \beta}$ (with no additional space or time cost). We then have $K = 1$ with the previous notations.

We also know that in that case, we have $|\mathbb{S}_{\bullet, \bullet}^{\rho, \beta}| = O(\rho)$ (i.e. $k = 1$). Based on these elements, we have the following result as a corollary of Prop. 28.

**Corollary 30** Let $\mu \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$. The time cost of Alg. 2 for computing $\mathfrak{T}(\mathfrak{R}_{\mathbb{Z}^2}^{[\sqrt{0}, \mu]})$ is $O(\mu^3)$.

In particular, the proposed (top-down) approach of Alg. 2 has a lower time cost compared with the (bottom-up) approach of Alg. 1 which is $O(\mu^3 \log \mu)$.

### 10.5.3 The injective discrete rotations

Let us finally consider the case of the injective discrete rotations, i.e. all the $\rho$-rotations for $\rho \in [[\sqrt{0}, \mu]]$, which are bijections from $B^\rho$ to its image. These $\rho$-rotations are characterized by the Boolean criterion $\kappa = \iota$ (Sect. 9.3).

If $\rho = \sqrt{0}$, then $\iota(S) = \top$ for the unique $S \in \mathbb{S}_{\bullet, \bullet}^{\sqrt{0}}$. Now, let $\rho \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$ and let us consider a segment $S \in \mathbb{S}_{\bullet, \bullet}^{\rho}$ associated to the rotation $R_\theta (\theta \in \mathbb{U})$ such that $S \prec S'$ with $S' \in \mathbb{S}_{\bullet, \bullet}^{\rho, \Theta(1)}$. It is plain that $\neg \iota(S') \Rightarrow \neg \iota(S)$, and in particular, this defines $\iota$ as decreasing. Let us now suppose that $\iota(S') = \top$. We then have

$$ \iota(S) = (\forall \mathbf{p} \in C^\rho, R_\theta(\mathbf{p}) \notin R_\theta(B^{\rho \oplus 1})) \qquad (86) $$
For any $\mathbf{p} \in \mathbb{Z}^2$, $R_\theta(\mathbf{p}) = R_\theta(\mathbf{q})$ implies that $\|\mathbf{p} - \mathbf{q}\|_2 = 1$. We set $\mathcal{N}(\mathbf{p}) = \{\mathbf{q} \in \mathbb{Z}^2 \mid (\|\mathbf{p} - \mathbf{q}\|_2 = 1) \wedge (\|\mathbf{q}\|_2 \le \|\mathbf{p}\|_2)\}$. Eq. (86) rewrites as

$$ \iota(S) = (\forall \mathbf{p} \in C^\rho, \forall \mathbf{q} \in \mathcal{N}(\mathbf{p}), R_\theta(\mathbf{p}) \neq R_\theta(\mathbf{q})) \quad (87) $$

It follows that $\iota(S)$ can be computed from $\iota(S')$ by an iterative process that considers successively the points $\mathbf{p} \in C^\rho$ (with $|C^\rho| = O(1)$) and that considers successively the neighbour points $\mathbf{q} \in \mathbb{Z}^2$ of $\mathbf{p}$ that satisfy $\|\mathbf{p} - \mathbf{q}\|_2 = 1$ and $\|\mathbf{q}\|_2 \le \|\mathbf{p}\|_2$ (the number of which is also $O(1)$).

For a given point $\mathbf{p} \in C^\rho$ and a given neighbour $\mathbf{q}$ of $\mathbf{p}$, it is convenient to process as a whole the $\iota(S)$ for all $S \in \mathbb{S}_{\bullet, \infty}^{\rho, k}$ from all the $\iota(S')$ for $S' \in \mathbb{S}_{\bullet, \infty}^{\rho, k}$. Indeed, the set $\hat{\mathbb{H}}^\mathbf{p}$ (see Eq. (70)) can be built sorted from $\hat{\mathbb{H}}^\mathbf{p}$ (see Eq. (71)) with a time cost $O(\rho)$. For each $\theta \in \hat{\mathbb{H}}^\mathbf{p}$, the value $R_\theta(\mathbf{p})$ can be computed with a time cost $O(1)$ by considering an incremental computation over the ordered set $\hat{\mathbb{H}}^\mathbf{p}$. The same remarks hold for $\hat{\mathbb{H}}^\mathbf{q}$. By considering Func. Refine applied to the two partitions induced by $\hat{\mathbb{H}}^\mathbf{p}$ and $\hat{\mathbb{H}}^\mathbf{q}$ a refined partition $\Pi(\hat{\mathbb{H}}^\mathbf{p} \cup \hat{\mathbb{H}}^\mathbf{q})$ of size $O(\rho)$ can be built with a time cost $O(\rho)$. For each $S_\theta \in \Pi(\hat{\mathbb{H}}^\mathbf{p} \cup \hat{\mathbb{H}}^\mathbf{q})$, we can check if $R_\theta(\mathbf{p}) = R_\theta(\mathbf{q})$ with a time cost $O(1)$. It follows that the cost $K$ for evaluating $\iota$ at a given segment is $O(1)$.

Based on these elements, we have the following result as a corollary of Prop. 27. Note that we do not know the size of $\mathbb{S}_{\bullet, \infty}^{\rho, k}$, namely the value of $k$. However, it lies between 1 and 3 since $k = 3$ for the general case and $k = 1$ for the bijective case.

**Corollary 31** Let $\mu \in \sqrt{\mathbb{N}} \setminus \{\sqrt{0}\}$. Let $k \in [1, 3]$. Let us suppose that for each $\rho \in [\sqrt{0}, \mu]$, we have $|\mathbb{S}_{\bullet, \infty}^{\rho, k}| = \Theta(\rho^k)$. The time cost of Alg. 2 for computing $\mathfrak{I}(\mathfrak{I}(\mathbb{S}_{\bullet, \infty}^{\rho, k}))$ is $O(\mu^{k+2})$.

This computational efficiency depends on the size of the space of the injective $\rho$-rotations.

## 11 Experiments

The algorithms proposed in Sects. 9–10 were implemented in C++ and are freely available<fnref n="3" />.

By applying these two construction algorithms, we built the combinatorial spaces of $\rho$-rotations. We illustrate the bijective ones $(\mathfrak{I}(\mathfrak{I}(\mathbb{S}_{\bullet, \infty}^{\rho, k})))$ and the injective ones $(\mathfrak{I}(\mathfrak{I}(\mathbb{S}_{\bullet, \infty}^{\rho, k})))$ in Figs. 15–18 for $\rho \in [\sqrt{0}, \mu]$, with $\mu = \sqrt{50}, \sqrt{100}, \sqrt{500}$ and $\sqrt{1000}$, respectively.

In Fig. 19, we report the size of these spaces with respect to $\rho \in [\sqrt{0}, \sqrt{1000}]$, in order to experimentally compare their actual size with their theoretical size. These experiments corroborate the fact that the number of $\rho$-rotations is $\Theta(\rho^3)$ and the number of bijective $\rho$-rotations is $\Theta(\rho)$. Regarding the number of injective (but non-bijective) $\rho$-rotations, the

trend remains ambiguous. It seems to be $\Omega(\rho)$ (Fig. 19(a)), but it does not experimentally exhibit a clear polynomial behaviour (Fig. 19(b)). For $\rho$ lower than $\sqrt{16}$, the number of injective (and non-bijective) $\rho$-rotations is generally slightly lower than the number of bijective ones. For $\rho$ greater than $\sqrt{16}$, this number of injective (and non-bijective) $\rho$-rotations becomes greater. This will motivate a dedicated combinatorial study.

## 12 Conclusion

In this article, we provided two algorithmic schemes that allow to build the combinatorial space of finite discrete rotations. They rely on discrete computation and are then free of numerical errors. These algorithms and their outputs allowed us to revisit the concepts of bijective (finite) rotations, which are important geometric operations in numerical imaging. They also led us to initiate an investigation of the injective finite rotations, which had not been much considered until now. These injective rotations are interesting both from applicative and theoretical points of view. Our further works will consist of more thoroughly studying them, in order to understand their links with bijective rotations, the evolution of their population with respect to the size of the Euclidean balls where they lie, and their persistence with respect to the size of these balls. It may also be interesting to generalize the proposed top-down algorithm for a non-Euclidean-ball region, if we are interested in preserving bijection / injection for certain pixels in an image.

## Acknowledgements

This work was supported by the French Agence Nationale de la Recherche (Grants ANR-22-CE45-0034 and ANR-23-CE45-0015).

## A Appendix – Proofs

### Proof of Property 11

Due to symmetry considerations we restrict, without loss of generality, the proof to the subset of angles $(0, \pi/4)$, where the angles $\theta$ leading to bijective discrete rotations are characterized by

$$ \sin \theta \in \left\{ s_p = \frac{2p + 1}{2p^2 + 2p + 1} \right\}_{p \in \mathbb{N}^*} \quad (88) $$

The trivial generalization of the proof to other angles is left to the reader.

Let $\theta \in (0, \pi/4)$ such that $\sin \theta = s_p$ for a given $p \in \mathbb{N}^*$. Let us suppose that $p > 2\rho$. We have $\sin \theta = \frac{2p+1}{2p^2+2p+1} < \frac{2p+1}{2p+p} = \frac{1}{p} < \frac{1}{2\rho}$. In such conditions, for any point $\mathbf{p} \in B^\rho$, we have $\|\mathbf{p} - R_\theta(\mathbf{p})\|_2 < \frac{1}{2}$, and thus $R_\theta^\rho(\mathbf{p}) = \mathbf{p}$. In other words, we have $R_\theta^\rho = R_\theta^0$. It follows that for all $p \in \mathbb{N}^*$ such that $p > 2\rho$, all the angles $\theta$ such that $\sin \theta = s_p$,

<footnote n="3">³ https://github.com/ngophuc/DiscreteRotationSpace</footnote>
<figure><img src="image_16.png" /><figcaption>**Fig. 15** The combinatorial space of the bijective and injective $\rho$-rotations for angles $\theta \in [0, \frac{\pi}{4}]$ (x-axis: angle $\theta/\pi$) (the remainder of the space is obtained by symmetry) and for radii $\rho \in [\sqrt{0}, \sqrt{50}]$ (y-axis: $\rho^2$). Bijective $\rho$-rotations are depicted in pink. (Additional) injective $\rho$-rotations are depicted in blue. (a) Rotations are defined by their angle interval of definition; the crosses indicate the first bijective rotations. (b) Rotations are defined by the centers of their angle interval of definition; the inclusion of these intervals are depicted by black edges between successive radii $\rho$.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>**Fig. 16** The combinatorial space of the bijective and injective $\rho$-rotations for angles $\theta \in [0, \frac{\pi}{4}]$ (x-axis: angle $\theta/\pi$) (the remainder of the space is obtained by symmetry) and for radii $\rho \in [\sqrt{0}, \sqrt{100}]$ (y-axis: $\rho^2$). Bijective $\rho$-rotations are depicted in pink. (Additional) injective $\rho$-rotations are depicted in blue. (a) Rotations are defined by their angle interval of definition; the crosses indicate the first bijective rotations. (b) Rotations are defined by the centers of their angle interval of definition; the inclusion of these intervals are depicted by black edges between successive radii $\rho$.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>**Fig. 17** The combinatorial space of the bijective and injective $\rho$-rotations for angles $\theta \in [0, \frac{\pi}{4}]$ (x-axis: angle $\theta/\pi$) (the remainder of the space is obtained by symmetry) and for radii $\rho \in [\sqrt{0}, \sqrt{500}]$ (y-axis: $\rho^2$). Bijective $\rho$-rotations are depicted in pink. (Additional) injective $\rho$-rotations are depicted in blue. (a) Rotations are defined by their angle interval of definition; the crosses indicate the first bijective rotations. (b) Rotations are defined by the centers of their angle interval of definition; the inclusion of these intervals are depicted by black edges between successive radii $\rho$.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>**Fig. 18** The combinatorial space of the bijective and injective $\rho$-rotations for angles $\theta \in [0, \frac{\pi}{4}]$ (x-axis: angle $\theta/\pi$) (the remainder of the space is obtained by symmetry) and for radii $\rho \in [\sqrt{0}, \sqrt{1000}]$ (y-axis: $\rho^2$). Bijective $\rho$-rotations are depicted in pink. (Additional) injective $\rho$-rotations are depicted in blue. (a) Rotations are defined by their angle interval of definition; the crosses indicate the first bijective rotations. (b) Rotations are defined by the centers of their angle interval of definition; the inclusion of these intervals are depicted by black edges between successive radii $\rho$.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>**Fig. 19** Size of the families of $\rho$-rotations for $\rho \in [\sqrt{1}, \sqrt{1000}]$. (a) All $\rho$-rotations, bijective and injective ones (log-log scale). (b) Bijective and injective $\rho$-rotations.</figcaption></figure>
generating bijective discrete rotations belong to exactly one interval of $S_{\bullet, \bullet}^p$, namely $[h_{\sigma^{p-1}, \sigma^p}, h_0^p]$ (which trivially corresponds to the bijective discrete rotation of angle 0 as well). The result follows. ■

## Proof of Property 21

Let $h \in \mathbb{H}^\mu$. Let $\mathbf{t} = (p_x, p_y, k) \in \mathbb{T}$ be the prime generator of $h$, associated to the point $\mathbf{p} = (p_x, p_y) \in \mathbb{Z}^2$. From Prop. 2, for any triplet $\mathbf{t}' = (q_x, q_y, k') \in \mathbb{T}$ such that $\eta(\mathbf{t}) = \eta(\mathbf{t}')$, there exists $n \in \mathbb{Z}$ such that $q_x = (2n+1)p_x$ and $q_y = (2n+1)p_y$. It follows that $\|\mathbf{p}\|_2 \le \|\mathbf{q}\|_2$. Since $\eta(\mathbf{t}) = h$, we have $h \in \mathbb{H}^{\|\mathbf{p}\|_2}$. But since $\mathbf{p}$ is the point of lowest norm that satisfies this property, we have $\|\mathbf{p}\|_2 = \min \{\rho \in \sqrt{\mathbb{N}} | h \in \mathbb{H}^\rho\}$ and the result follows. ■

## References

1. Amir, A., Kapah, O., Tsur, D.: Faster two-dimensional pattern matching with rotations. Theoretical Computer Science 368, 196–204 (2006)

2. Andres, É.: The quasi-shear rotation. In: Discrete Geometry for Computer Imagery (DGCI), Proceedings. Lecture Notes in Computer Science, vol. 1176, pp. 307–314. Springer (1996)

3. Andres, É., Dutt, M., Biswas, A., Largeteau-Skapin, G., Zrour, R.: Digital two-dimensional bijective reflection and associated rotation. In: Discrete Geometry for Computer Imagery (DGCI), Proceedings. Lecture Notes in Computer Science, vol. 11414, pp. 3–14. Springer (2019)

4. Andres, É., Largeteau-Skapin, G., Zrour, R.: Shear based bijective digital rotation in hexagonal grids. In: Discrete Geometry and Mathematical Morphology (DGMM), Proceedings. Lecture Notes in Computer Science, vol. 12708, pp. 217–228. Springer (2021)

5. Berthé, V., Nouvel, B.: Discrete rotations and symbolic dynamics. Theoretical Computer Science 380, 276–285 (2007)

6. Beucher, S., Lantuëjoul, C.: Use of watersheds in contour detection. In: International Workshop on Image Processing, Proceedings (1979)

7. Breuils, S., Kenmochi, Y., Andres, É., Sugimoto, A.: Conjecture on characterisation of bijective 3D digitized reflections and rotations. In: Empowering Novel Geometric Algebra for Graphics and Engineering (ENGAGE), Proceedings. Lecture Notes in Computer Science, vol. 13862, pp. 41–53. Springer (2022)

8. Breuils, S., Coeurjolly, D., Lachaud, J.O.: Construction of fast and accurate 2D bijective rigid transformation. In: Discrete Geometry and Mathematical Morphology (DGMM), Proceedings. Lecture Notes in Computer Science, vol. 14605, pp. 80–92. Springer (2024)

9. Breuils, S., Kenmochi, Y., Sugimoto, A.: Visiting bijective digitized reflections and rotations using geometric algebra. In: Discrete Geometry and Mathematical Morphology (DGMM), Proceedings. Lecture Notes in Computer Science, vol. 12708, pp. 242–254. Springer (2021)

10. Comic, L., Zrour, R., Andres, E., Largeteau-Skapin, G.: Bijective digitized 3D rotation based on beam shears. In: Discrete Geometry and Mathematical Morphology (DGMM), Proceedings. Lecture Notes in Computer Science, vol. 14605, pp. 29–40. Springer (2024)

11. Hannusch, C., Pethö, A.: Rotation on the digital plane. Periodica Mathematica Hungarica 86, 564–577 (2023)

12. Heijmans, H.J.A.M., Ronse, C.: The algebraic basis of mathematical morphology. I. Dilations and erosions. Computer Vision, Graphics, and Image Processing 50, 245–295 (1990)

13. Hundt, C., Liśkiewicz, M., Ragnar, N.: A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation. Theoretical Computer Science 410, 5317–5333 (2009)

14. Jacob, M.A., Andres, É.: On discrete rotations. In: Discrete Geometry for Computer Imagery (DGCI), Proceedings. pp. 161–174 (1995)

15. Khalimsky, E., Kopperman, R., Meyer, P.: Computer graphics and connected topologies on finite ordered sets. Topology and its Applications 36, 1–17 (1990)

16. Kong, T.Y., Rosenfeld, A.: Digital topology: Introduction and survey. Computer Vision, Graphics, and Image Processing 48, 357–393 (1989)

17. Kovalevsky, V.A.: Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Processing 46, 141–161 (1989)

18. Najman, L., Schmitt, M.: Geodesic saliency of watershed contours and hierarchical segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 18, 1163–1173 (1996)

19. Najman, L., Talbot, H. (eds.): Mathematical Morphology: From Theory to Applications. ISTE/J. Wiley & Sons (2010)

20. Ngo, P., Kenmochi, Y., Debled-Rrennesson, I., Passat, N.: Convexity-preserving rigid motions of 2D digital objects. In: Discrete Geometry for Computer Imagery (DGCI), Proceedings. Lecture Notes in Computer Science, vol. 10502, pp. 69–81. Springer (2017)

21. Ngo, P., Kenmochi, Y., Passat, N., Talbot, H.: Combinatorial structure of rigid transformations in 2D digital images. Computer Vision and Image Understanding 117, 393–408 (2013)

22. Ngo, P., Kenmochi, Y., Passat, N., Talbot, H.: Topology-preserving conditions for 2D digital images under rigid transformations. Journal of Mathematical Imaging and Vision 49, 418–433 (2014)

23. Ngo, P., Passat, N., Kenmochi, Y., Debled-Rrennesson, I.: Convexity invariance of voxel objects under rigid motions. In: International Conference on Pattern Recognition (ICPR), Proceedings. pp. 1157–1162. IEEE Computer Society (2018)

24. Ngo, P., Passat, N., Kenmochi, Y., Debled-Rrennesson, I.: Geometric preservation of 2D digital objects under rigid motions. Journal of Mathematical Imaging and Vision 61, 204–223 (2019)

25. Ngo, P., Passat, N., Kenmochi, Y., Talbot, H.: Topology-preserving rigid transformation of 2D digital images. IEEE Transactions on Image Processing 23, 885–897 (2014)

26. Nouvel, B.: Rotation discrètes et automates cellulaires. Ph.D. thesis, École Normale Supérieure de Lyon (2006)

27. Nouvel, B., Rémila, É.: Characterization of bijective discretized rotations. In: International Workshop on Combinatorial Image Analysis (IWCIA), Proceedings. Lecture Notes in Computer Science, vol. 3322, pp. 248–259. Springer (2004)

28. Nouvel, B., Rémila, É.: Incremental and transitive discrete rotations. In: International Workshop on Combinatorial Image Analysis (IWCIA), Proceedings. Lecture Notes in Computer Science, vol. 4040, pp. 199–213. Springer (2006)

29. Passat, N., Kenmochi, Y., Ngo, P., Pluta, K.: Rigid motions in the cubic grid: A discussion on topological issues. In: Discrete Geometry for Computer Imagery (DGCI), Proceedings. Lecture Notes in Computer Science, vol. 11414, pp. 127–140. Springer (2019)

30. Passat, N., Ngo, P., Kenmochi, Y.: Bijectivity analysis of finite rotations on $\mathbb{Z}^2$. In: Discrete Geometry and Mathematical Morphology (DGMM), Proceedings. Lecture Notes in Computer Science, vol. 14605, pp. 3–15. Springer (2024)

31. Pluta, K., Romon, P., Kenmochi, Y., Passat, N.: Bijectivity certification of 3D digitized rotations. In: Computational Topology in Image Context (CTIC), Proceedings. Lecture Notes in Computer Science, vol. 9667, pp. 30–41. Springer (2016)

32. Pluta, K., Romon, P., Kenmochi, Y., Passat, N.: Bijective digitized rigid motions on subsets of the plane. Journal of Mathematical Imaging and Vision 59, 84–105 (2017)
33. Pluta, K., Roussillon, T., Coeurjolly, D., Romon, P., Kenmochi, Y., Ostromoukhov, V.: Characterization of bijective digitized rotations on the hexagonal grid. Journal of Mathematical Imaging and Vision **60**, 707–716 (2018)

34. Roussillon, T., Coeurjolly, D.: Characterization of bijective discretized rotations by Gaussian integers. Tech. rep. (2016), https://hal.archives-ouvertes.fr/hal-01259826

35. Salembier, P., Garrido, L.: Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. IEEE Transactions on Image Processing **9**, 561–576 (2000)

36. Thibault, Y.: Rotations in 2D and 3D discrete spaces. Ph.D. thesis, Université Paris-Est (2010)

37. Thibault, Y., Sugimoto, A., Kenmochi, Y.: 3D discrete rotations using hinge angles. Theoretical Computer Science **412**, 1378–1391 (2011)

38. Toffoli, T., Quick, J.: Three-dimensional rotations by three shears. Graphical Models and Image Processing **59**, 89–95 (1997)