In digital geometry, Euclidean objects are represented by their discrete approximations, e.g. subsets of the lattice of integers. Rigid motions of such sets have to be defined as maps from and onto a given discrete space. One way to design such motions is to combine continuous rigid motions defined on Euclidean space with a digitization operator. However, digitized rigid motions often no longer satisfy properties of their continuous siblings. Indeed, due to digitization, such transformations do not preserve distances, furthermore bijectivity and point connectivity are generally lost.

In the context of 2D discrete spaces, we study digitized rigid motions on the lattices of Gaussian and Eisenstein integers. We characterize bijective digitized rigid motions on the integer lattice, and bijective digitized rotations on the regular hexagonal lattice.

Also, we compare the information loss induced by non-bijective digitized rigid motions defined on both lattices. Yet, for practical applications, the relevant information is not global bijectivity, but bijectivity of a digitized rigid motion restricted to a given finite subset of a lattice. We propose two algorithms testing that condition for subsets of the integer lattice, and a third algorithm providing optimal angle intervals that preserve this restricted bijectivity.

We then focus on digitized rigid motions on the 3D integer lattice. First, we study at a local scale geometric and topological defects induced by digitized rigid motions. Such an analysis consists of generating all the images of a finite digital set under digitized rigid motions. This problem amounts to computing an arrangement of hypersurfaces in a 6D parameter space. The dimensionality and degenerate cases make the problem practically unsolvable for state-of-the-art techniques. We propose an ad hoc solution, which mainly relies on parameter uncoupling, and an algorithm for computing sample points of 3D connected components in an arrangement of second degree polynomials. Finally, we focus on the open problem of determining whether a 3D digitized rotation is bijective. In our approach, we explore arithmetic properties of Lipschitz quaternions. This leads to an algorithm which answers whether a given digitized rotation-related to a Lipschitz quaternion-is bijective. v Résumé En géométrie discrète, les objets euclidiens sont représentés par leurs approximations discrètes, telles que des sous-ensembles du réseau des points à coordonnées entières. Les déplacements de ces ensembles doivent être définis comme des applications depuis et sur un espace discret donné. Une façon de concevoir de telles transformations est de combiner des déplacements continus définis sur un espace euclidien avec un opérateur de discrétisation. Cependant, les déplacements discrétisés ne satisfont souvent plus les propriétés de leurs équivalents continus. En effet, en raison de la discrétisation, de telles transformations ne préservent pas les distances, et la bijectivité et la connexité entre les points sont généralement perdues. Dans le contexte des espaces discrets 2D, nous étudions des déplacements discrétisés sur les réseaux d'entiers de Gauss et d'Eisenstein. Nous caractérisons les déplacements discrétisés bijectifs sur le réseau carré, et les rotations bijectives discrétisées sur le réseau hexagonal régulier. En outre, nous comparons les pertes d'information induites par des déplacements discrétisés non bijectifs définis sur ces deux réseaux. Toutefois, pour des applications pratiques, l'information pertinente n'est pas la bijectivité globale, mais celle d'un déplacement discrétisé restreint à un sous-ensemble fini donné d'un réseau. Nous proposons deux algorithmes testant cette condition pour un sous-ensemble donné du réseau entier, ainsi qu'un troisième algorithme fournissant des intervalles d'angles optimaux qui préservent cette bijectivité restreinte. Nous nous concentrons ensuite sur les déplacements discrétisés sur le réseau cubique 3D. Tout d'abord, nous étudions à l'échelle locale des défauts géométriques et topologiques induits par des déplacements discrétisés. Une telle analyse consiste à générer toutes les images d'un sous-ensemble fini du réseau par des déplacements discrétisés. Un tel problème revient à calculer un arrangement d'hypersurfaces dans un espace de paramètres de dimension six. La dimensionnalité et les cas dégénérés rendent le problème insoluble, en pratique, par les techniques usuelles. Nous proposons une solution ad hoc reposant sur un découplage des paramètres, et un algorithme pour calculer des points d'échantillonnage de composantes connexes 3D dans un arrangement de polynômes du second vi degré. Enfin, nous nous concentrons du problème ouvert de déterminer si une rotation discrétisée 3D est bijective ou non. Dans notre approche, nous explorons les propriétés arithmétiques des quaternions de Lipschitz. Ceci conduit à un algorithme qui détermine si une rotation discrétisée donnée, associée à un quaternion de Lipschitz, est bijective ou non.

Preface

Digital geometry deals with the geometric properties of digital sets -sets of discrete points with prescribed properties like a point connectivity, which are approximations of continuous objects known from Euclidean geometry. These digital sets are defined with respect to a given underlying lattice. In this regard, the main purpose of digital geometry is to re-establish the results of Euclidean geometry and study the differences between continuous objects and their digital approximations. Fortunately, for my own curiosity the gap between the digital and continuous worlds is not negligible. Indeed, in most of the cases the digital world seems to be ruled by a different set of laws. For instance, two digital circles are not necessary tangent at a point and two digital lines not necessary cross each other in a point -even though, their continuous counterparts do cross in a point. Everything gets even more interesting in 3D where an intuition developed in 2D digital geometry setting, sometimes leads to false conclusions, if directly applied to 3D digital geometry.

The manuscript is intended to discuss the recent advances on the topic of digitized rigid motions applied to digital sets. By digitized rigid motions I mean rigid motions applied to digital sets and followed by a digitization operator. These are sometimes called "discrete rigid motions" but this misleading because such digitized transformations, in general, do not possess the same properties as continuous rigid motions. Indeed, such transformations are not distance preserving maps and they are non-bijective. The topic itself has been studied by many at least since the 1980s but mostly in the context of 2D digital geometry defined on the square lattice. The discussion provided in this thesis touches the topic of digitized rigid motions defined on the square, the regular hexagonal and the cube lattices. Indeed, I mostly focus on topological alterations of digital sets induced by these transformations. This manuscript has been divided into two parts. The first part is related to digitized rigid motions of 2D discrete spaces and their subsets while the second is related to rigid motions defined on the 3D digital space. There are rather few dependencies between the xiii Preface xiv parts, and therefore it is not required to read the first part in order to understand the second part and vice versa. However, some ideas are shared.

The reader will quickly discover that I wrote the manuscript in the first-person plural.

The reason for doing so is simple. The presented results were obtained in collaboration with my supervisors Yukiko Kenmochi and Pascal Romon but also Nicolas Passat, Guillaume Moroz, Tristan Roussillon, David Coeurjolly and Victor Ostromoukhov. Therefore, I simply cannot put my signature on the top of everything and claim it is entirely mine.

The manuscript provides a few counterexamples/criticism to the previous studies. Please note that, it was not my intention to criticize someone's work but only to provide a deeper understanding of issues which intuition proved to be false. Also, I would like to ask readers to report any mistake spotted by writing to kacper.pluta@gmail.com. good companion for many discussion about science and academia. Finally, I would like to thank Gisela Domej for all the support and her help during writing the manuscript.

Kacper Pluta

Introduction

In classical mechanics physicists are used to work with a rigid body -an ideal solid object that keeps distances and angles defined between its points unchanged regardless of external forces that have an impact on the object. These physical notions are related to Euclidean geometry where rigid bodies are represented as geometric objects such as points, lines, et cetera. In classical geometry motions induced by forces that affect an object but do not distort it, are represented as rigid motions i.e., rotations, translations, and their combinations. In everyday life we often observe rigid motions, for example, when we want to move or rotate a spoon. Because we are surrounded by rigid motions we are used to considering them as the most basic and simple geometric transformations.

In fact, this is true as long as we stay in a continuous world.

While working with computers Euclidean objects are often represented as their discrete approximations e.g., subsets of the integer lattice Z 2 . In this context, rigid motions are simple yet crucial operations in many applications involving 2D data. For example: in template matching [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF]; object tracking [START_REF] Yilmaz | Object Tracking: A Survey[END_REF] or halftoning and printing [START_REF] Ostromoukhov | Halftoning by Rotating Non-Bayer Dispersed Dither Arrays[END_REF][START_REF] Ostromoukhov | Rotated Dispersed Dither: A New Technique for Digital Hhalftoning[END_REF]. Therefore, rigid motions of such sets have to be defined as functions from and onto a given discrete space. One way to design them as such is to combine continuous rigid motions defined on the Euclidean plane with a digitization operator that maps the results back onto the discrete space. However, a digitized rigid motion, though uniformly "close" to its continuous analogue, often no longer satisfies the same properties. In particular, due to digitization, such transformations do not preserve distances, and bijectivity and point connectivity are generally lost. In this context, it is useful to understand the combinatorial, geometric and topological alterations associated with digitized rigid motions.

Over the last thirty years digitized rigid motions-as digital geometry in general-on the square grid have attracted more attention than, for example, ones on the regular hexagonal grid. Indeed, the square grid is predominant over other grids in fields such as image processing, mostly because of its common use by image acquisition devices, even though it is burdened with fundamental topological problems. In general, one has to choose between different connectivity relations for objects of interest, and their complements [START_REF] Kong | Digital Topology: Introduction and Survey[END_REF][START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF]. On the contrary, the regular hexagonal grid is free from these problems since it possesses the following properties: equidistant neighbors-each hexagon has six equidistant neighbors; uniform connectivity-there is only one connectivity type [START_REF] Middleton | Hexagonal Image Processing: A Practical Approach[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. We refer readers interested in an exhaustive comparison between image processing tasks with respect to the hexagonal and square grids to the book by Middleton and Sivaswamy [START_REF] Middleton | Hexagonal Image Processing: A Practical Approach[END_REF].

Motivated by the aforementioned issues we introduce a framework, which enables us to study the digitized rigid motions defined on both grids, and we study geometric and topological defects induced by digitized rigid motions defined on these grids at a local scale. Our approach is a generalization of the studies of digitized rigid motions based on the concept of the neighborhood motion maps [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Pluta | Honeycomb Geometry: Rigid Motions on the Hexagonal Grid[END_REF][START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF]. This enables us, for example, to compare the information preservation between digitized rigid motions defined on the square and the hexagonal grids.

In our humble opinion, the most impacting works within the field of digital geometry defined on the square grid are: Paeth proposed a fast algorithm for rotating raster images using shear transformations [START_REF] Paeth | Graphics Gems. chapter A Fast Algorithm for General Raster Rotation[END_REF]. The Paeth algorithm has been since implemented and used-even today-by some image processing tools, e.g., ImageMagick1 or pnmrotate 2 , to name some. Later on, Andres proposed a similar idea based on quasiaffine transformations and aimed at solving some problems of the Paeth algorithm e.g., lack of reversibility and a loss of information [START_REF] Andres | The Quasi-shear Rotation[END_REF]. Nevertheless, up to our knowledge, the Andres algorithm has never raised much interest, maybe because even after such an improvement the shear-based approach is still burdened with some problems [15, Section 2.3.3]; Anglin [START_REF] Anglin | Using Pythagorean Triangles to Approximate Angles[END_REF] proved that any rotation angle can be approximated by a Pythagorean angle -angle of rational sine and cosine. An algorithm to perform such an approximation can be found in Ostromoukhov's PhD thesis [START_REF] Ostromoukhov | Reproduction Couleur par Trames Irrégulières et Semi-régulières[END_REF]; Reveillès in his thèse d'état 3 [START_REF] Reveillès | Géométrie Discrète, Calcul en Nombres Entiers et Algorithmique[END_REF] discussed a few approaches to digitized rotations e.g., bijective rotations by a digital line. He also made an important observation related to twin Pythagorean triples.

Bijective digitized rotations were then used by Ostromoukhov in his work on halftoning [START_REF] Ostromoukhov | Halftoning by Rotating Non-Bayer Dispersed Dither Arrays[END_REF][START_REF] Ostromoukhov | Rotated Dispersed Dither: A New Technique for Digital Hhalftoning[END_REF][START_REF] Ostromoukhov | Reproduction Couleur par Trames Irrégulières et Semi-régulières[END_REF]. Later on, some sufficient conditions on bijectivity of digitized rotations were proved by Andres and Jacob-Da Col [START_REF] Jacob | On Discrete Rotations[END_REF]; In his PhD thesis Andres provided, in our opinion, the first exhaustive analysis of known digitized and discrete rotations (digitized rotations, discrete rotations by circles and discrete rotations by digital lines) with a focus on bijectivity, distance preservation, connectivity preservation and commutativity of such transformations [START_REF] Andres | Cercles Discrets et Rotations Discrètes[END_REF]. He then extended the study by discussing bijectivity of digitized motions in his habilitation [START_REF] Andres | Modélisation Analytique Discrète d'Objets Géométriques[END_REF]; Nouvel and Rémila [START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF] developed a framework for studying local alterations of the integer lattice under digitized rotations, namely on certain digital sets. This combinatorial model of the local behavior led them to characterizing bijective digitized rotations [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF], and more generally studying non-bijective ones [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | Rotations Discrètes et Automates Cellulaires[END_REF]; more recently, Roussillon and Coeurjolly provided an alternative characterization of bijective digitized rotations which is based on arithmetic properties of Gaussian integers [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF]; in his PhD thesis [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF], Fredriksson considered digitized rotations, and the transition angles which correspond to a shift in the image of an integer point from one digitization cell to another. These special angles were further studied-and named hinge angles-by Nouvel and Rémila [START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF]; Ngo et al. investigated the combinatorial structure of the parameter space of rigid motions of finite digital sets [START_REF] Ngo | Combinatorial Structure of Rigid Transformations in 2D Digital Images[END_REF]. This study led to a better understanding of the topological consequences of such transformations by analyzing the structural organization of this space; to the determination of topologically equivalent motions [START_REF] Ngo | Topology-preserving Conditions for 2D Digital Images under Rigid Transformations[END_REF]. From a methodological point of view, these theoretical results led to the proposal of combinatorial registration methods [START_REF] Ngo | Discrete Rigid Registration: A Local Graph-search Approach[END_REF], and constrained rigid transformation approaches [START_REF] Ngo | On 2D Constrained Discrete Rigid Transformations[END_REF]. Finally, Ngo et al. established sufficient conditions for topology preservation under 2D digitized rigid motions [START_REF] Ngo | Topology-preserving Rigid Transformation of 2D Digital Images[END_REF].

On the other hand, studies related to digitized rotations on the regular hexagonal grid are far less numerous. Her-while working with the hexagonal grid represented by cube coordinate system in 3D-showed how to derive a rotation matrix such that it is simpler than a 3D rotation matrix obtained in a direct way [START_REF] Her | Geometric Transformations on the Hexagonal Grid[END_REF].

In this context our contributions are the following.

1. We generalize the aforementioned combinatorial model of the local behavior of digitized rotations [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF] to (i) digitized rigid motions, and (ii) any neighborhood regardless of its size, shape and the underlying grid i.e., the square or hexagonal grid. We call this local description neighborhood motion maps. In this regard we then characterize the bijective rigid motions on the square grid and compare the information loss between digitized rigid motions defined on the square and the hexagonal grid. Indeed, we show that such a loss of information is relatively lower for digitized rigid motions defined on the hexagonal grid. These contributions are related to the following publications [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Pluta | Honeycomb Geometry: Rigid Motions on the Hexagonal Grid[END_REF].

2. We restrict then to the practical problem of verifying whether a prescribed subset of the integer lattice is transformed injectively by a digitized rigid motion. To this end, the local approach of neighborhood motion maps is well suited and leads to an algorithmic answer. More precisely, two different algorithms are proposed, the efficiency of each depends on the ratio of the size of the subset to the complexity of the rigid motion measured by the integers of the Pythagorean triples. This algorithmic approach can be used for finding, for a given subset S and an injective rigid motion on S, a range of nearby parameters ensuring injectivity, thereby offering a stability result. This is done by extending the concept of hinge angles [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF][START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF][START_REF] Thibault | Computing Upper and Lower Bounds of Rotation Angles from Digital Images[END_REF] to rigid motions. The algorithms were presented in [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF].

3. While working in the framework of the hexagonal grid we characterize rational rotations and prove that any angle can be approximated by such rational rotations with any given accuracy. Then, we characterize bijective digitized rotations on the hexagonal grid and show that these are more frequent than their counterparts on the square grid. These contributions appeared in [START_REF] Pluta | Honeycomb Geometry: Rigid Motions on the Hexagonal Grid[END_REF][START_REF] Pluta | Characterization of Bijective Digitized Rotations on the Hexagonal Grid[END_REF]. [START_REF] Ostromoukhov | Rotated Dispersed Dither: A New Technique for Digital Hhalftoning[END_REF]. Finally, Appendices A-C, contain a complete (up to symmetries) set of neighborhood motions maps computed for 4-, 8-(the square grid case) and 6-neighborhoods (the hexagonal grid case). The appendices were published in [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Pluta | Honeycomb Geometry: Rigid Motions on the Hexagonal Grid[END_REF].

The remainder of Part I is organized as follows. In Chapter 2 we provide basic notations related to digital geometry and digitized rigid motions. Moreover, we provide in this chapter a characterization of rational rotations in the hexagonal grid. Then, Chapter 3 provides a discussion about the framework of neighborhood motion maps and the issue of the information preservation. In Chapter 4 we discuss the bijective digitized rigid motions on the square grid and its subsets. We finish Part I providing a characterization of bijective digitized rotations on the hexagonal grid together with a comparison of frequencies of such rotations on both grids. Note that we do not provide a general conclusion of Part I. Instead, we end each chapter by concluding the discussed topics and possible future works.

Chapter 2

Basic Notions

In this chapter we provide the basic notions and notations related to the square and regular hexagonal grids, which are the discrete spaces we work on. These notions and notations are then used in Part I.

2D Discrete Spaces

We define the square lattice as the complex numbers whose real and imaginary parts are both integers Z[i] = Z ⊕ Zi (see Hereafter, we use Z[κ κ κ] to indicate that the choice between Gaussian or Eisenstein integers is arbitrary, more specifically κ κ κ ∈ {i, ω}.

Properties of Gaussian and Eisenstein Integers

The Gaussian (resp. Eisenstein) integers form a Euclidean ring Z[i] (resp. Z[ω]) in the complex plane C; in particular they possess similar properties to the ordinary integers: division, prime factorization and greatest common divisor are well-defined. Let us con- 2.1 provides some basic properties of both types of integers. Moreover, given Gaussian (resp. Eisenstein) integers x and y, a greatest common divisor gcd(x, y) = z ∈ Z[κ κ κ], is defined as a largest Gaussian (resp. Eisenstein) integer (up to multiplications by units) which divides both x and y; every common divisor of x and y also divides z. By a largest Gaussian (resp. Eisenstein) integer we mean one of a largest modulus. Note since Gaussian (resp. Eisenstein) integers form a Euclidean ring such a greatest common divisor always exists. Also, x is said to be a Gaussian (resp.

sider x = a + bi ∈ Z[i] (resp. x = a + bω ∈ Z[ω]) then Table

Property

Gaussian integers Eisenstein integers

Conjugate

x = a -bi x = (a -b) -bω Squared modulus |x| 2 = x • x = a 2 + b 2 |x| 2 = x • x = a 2 -ab + b 2 Units Υ = {±1, ±i} Υ = {±1, ±ω, ± ω} Divisibility y|x if ∃z ∈ Z[κ κ κ] such that x = y • z and y ∈ Z[κ κ κ]
an Eisenstein) prime if its divisors are only of the form υ • x, υ ∈ Υ.

Pythagorean and Eisenstein triples

Pythagorean triples. Pythagorean triples (a, b, c) ∈ Z 3 are triples of integers such that

a 2 + b 2 = c 2 .
Thanks to the symmetry, hereafter, we consider only positive primitive Pythagorean triples, i.e., 0 < a < b < c, gcd(a, b, c) = 1. Let us then denote the set of positive primitive Pythagorean triples by P + ρ and consider the subset

Z[i] + ρ = α = a + bi ∈ Z[i] (a, b, a 2 + b 2 ) ∈ P + ρ .
We also use P ρ to refer to the set of primitive Pythagorean triples and Z[i] ρ to refer to the corresponding set of Gaussian integers. A part of Z[i] + ρ is illustrated by Figure 2.2(a).

In the case of the primitive Pythagorean triples it is well known that such triples can be generated from two integers called generators. and only if there exist p, q ∈ Z, 0 < q < p, gcd(p, q) = 1 and p -q ≡ 0 (mod 2), such that

a = p 2 -q 2 , b = 2pq, c = p 2 + q 2 .
Note that Pythagorean triples correspond to right triangles of integer side lengths e.g., the well-known [START_REF] Ostromoukhov | Halftoning by Rotating Non-Bayer Dispersed Dither Arrays[END_REF][START_REF] Ostromoukhov | Rotated Dispersed Dither: A New Technique for Digital Hhalftoning[END_REF][START_REF] Kong | Digital Topology: Introduction and Survey[END_REF] triple (see Figure 2.3(a)).

Eisenstein triples. Eisenstein triples (a, b, c) ∈ Z 3 are triples of integers such that

a 2 -ab + b 2 = c 2 .
Thanks to the symmetry, hereafter, we consider only positive primitive Eisenstein triples i.e., 0 < a < c < b, gcd(a, b, c) = 1 and either a + b + c ≡ 0 (mod 3) or 2b -a + c ≡ 0 (mod 3) [START_REF] Gordon | Properties of Eisenstein Triples[END_REF]. Let us then denote the set of positive primitive Eisenstein triples by E + ρ and consider the subset

Z[ω] + ρ = α = a + bω ∈ Z[ω] (a, b, a 2 -ab + b 2 ) ∈ E + ρ .
We also use Note that, the axes were scaled for a better visualization effect and the distance between two consecutive axes' ticks is 30.

t, gcd(s, t) = 1 and t -s ≡ 0 (mod 3), such that

a = s 2 + 2st, b = t 2 + 2st, c = s 2 + t 2 + st.
For the proof, see the discussion provided by Gilder in [START_REF] Gilder | Integer-sided Triangles with an Angle of 60 •[END_REF].

Note that the union of triangles of side lengths (a, b, c) ∈ Z 3 and (b-a, b, c) ∈ Z 3 is equal to an equilateral triangle, which sides' length is equal to b. In such a union two triangles share the side of length c. Figure 2.3(b) illustrates an example of such triangles. For more information about Eisenstein integers we encourage readers to look into [START_REF] Gordon | Properties of Eisenstein Triples[END_REF][START_REF] Gilder | Integer-sided Triangles with an Angle of 60 •[END_REF].

Digitization -From C to Discrete Spaces

In general, geometric objects represented by computers are obtained via sampling process called digitization. The most common digitization model is called Gaussian [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF].

To define such a digitization operator let us first define a grid cell centered at a Gaussian (resp. an Eisenstein) integer x, for a given rotation and scaling factor ξ ∈ Z[i] (resp.

√ 3a 2b-a , θ = arctan √ 3(b-a) b+a (b). ξ ∈ Z[ω]): C ξ (x) = y ∈ C | ∀υ ∈ Υ, ( |y -x| < |y -x + υ • ξ| ∧ |y -x| ≤ |y -x -υ • ξ|) .
→ Z[κ κ κ], such that ∀x ∈ C, ∃!D(x) ∈ Z[κ κ κ] and x ∈ C 1 (D(x)). We can note that D(B r (0)) = B r (0) ∩ Z[κ κ κ] (see Figure 2.4).
Note that this definition of a digitization operator is rather theoretical but not computationally relevant in the case of the hexagonal grid. For readers who are interested in implementing the digitization operator in the hexagonal lattice, we suggest the method proposed by Her [START_REF] Her | Geometric Transformations on the Hexagonal Grid[END_REF]. For the integer lattice a standard rounding function can be applied to the real and imaginary parts.

Rigid Motions

Rigid motions on C are bijective isometric maps [START_REF] Galarza | Introduction to Classical Geometries[END_REF]; in particular, they preserve distances and angles. The set of rigid motions includes rotations (around the origin), translations, and their compositions. integers. The ball is marked in red and the corresponding sets of digitization cells are filled with a green hatched pattern.

1 2 + 1 2 i 1 2 -1 2 i -1 2 -1 2 i -1 2 + 1 2 i 1 i 0 (a) ω-ω 3 1-ω 3 1-ω 3 ω-ω 3 ω-1 3 ω-1 3 0 1 ω (b)
U : C → C x → θ • x + t, (2.1)
where θ is a complex number of modulus |θ| = 1 and θ = arg(θ) is the corresponding rotation angle. Later on, we restrict use of the symbols θ and t = t 1 + t 2 i to denote rotation and translation, respectively.

While working in R 2 , one usually wants to represent rigid motions as a matrix-vector product followed by a vector addition. A rigid motion is then defined as a function

U : R 2 → R 2 x → Rx + v (2.2)
where v = (t 1 , t 2 ) ∈ R 2 is a translation vector and R is a rotation matrix which can be obtained from the corresponding matrix representation of a complex number θ

R =   a -b b a   =   cos θ -sin θ sin θ cos θ   (2.3)
with θ ∈ [0, 2π) being its rotation angle. This leads to the representation of rigid motions by a triplet of parameters (t 1 , t 2 , θ) ∈ R 2 × [0, 2π). Within this manuscript we use both definitions of rigid motions depending on the discussion context.

Digitized Rigid Motions

According to Equation (2.2), we generally have U(Z[κ κ κ]) Z[κ κ κ]; in other words, a rigid motion applied to a lattice maps it onto the set of complex numbers which are not necessarily members of the lattice -expect for very specific choices of θ and t. As a consequence, in order to define digitized rigid motions as maps from

Z[κ κ κ] to Z[κ κ κ],
the most common solution is to apply rigid motions to a lattice as a part of C, and then combine the results with a digitization operator. Then, digitized rigid motions are defined by

U = D • U |Z[κ κ κ] .
(2.4)

Due to the behavior of D that maps C onto Z[κ κ κ], digitized rigid motions are, most of the time, non-bijective. In other words, while any q ∈ C is associated to a unique preimage p ∈ C, such that U(p) = q, q can be associated to several (resp. no) preimages p ∈ Z[κ κ κ] for a digitized rigid motion U associated to U |Z[κ κ κ] . In such a case, U is non-injective (resp. non-surjective). For a visualization we encourage readers to see Figure 2.6.

Rational Rotations

In the later chapters we focus on some properties of digitized rigid motions such as bijectivity-to name one. We study such properties by employing some maps and studying the set of their images. Indeed, the structure of the images of these maps is related to the parameters of the underlying rigid motion. To begin we focus on the rotational part of a rigid motion and define a group

G = Z θ |θ| ⊕ Z θ |θ| • κ κ κ ⊕ Z ⊕ Zκ κ κ
where θ ∈ Z[κ κ κ] ρ and κ κ κ ∈ {i, ω}.

Then we focus on these parameters of the underlying rigid motions under which G is a lattice. We call digitized rigid motions which do lead to such cases rational.

The structure of G in the context of the digitized rotations defined on Z[i] has been intensively studied by Nouvel and Rémila [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF]. Therefore, this section is mostly devoted to digitized rigid motions defined on Z[ω]. Nevertheless, for completeness of the discussion, in the first section we recall the well-known results and facts related to the structure of G and Ḡ = G \ Z[i].

Pythagorean Rational Rotations

In a case of the square grid, it is known that only for rotations with rational cosine and sine -i.e., rotations given by primitive Pythagorean triples, G is a lattice, and Ḡ is a cyclic group [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF]. When on the contrary, cosine or/and sine are irrational, the images form an infinite and dense set, i.e. G is not a lattice [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF].

Ḡ = G/Z[i] is cyclic, | Ḡ| = c
and its generators are ψ ψ ψ = p c + q c i and φ φ φ = -q c + p c i, where p and q are the generators given in Lemma 2.1.

For more details and proofs see [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF] and the following discussion for the Eisenstein rational rotations.

Eisenstein Rational Rotations

In this section we study digitized rotations related to primitive Eisenstein triples, i.e.

such that θ ∈ Z[ω] ρ . For easiness of the discussion in this section we consider the matrix representation of rotations introduced in Section 2.2. We shall say that the rotation matrix R is Eisenstein rational if it is of the following form

R =   2a-b 2c - √ 3b 2c √ 3b 2c 2a-b 2c   = a c   1 0 0 1   + b c   -1 2 - √ 3 2 √ 3 2 1 2  
where (a, b, c) is an Eisenstein primitive triple. We must note that any rotation matrix can be written in this way, with a, b, c real numbers with c = √ a 2 -ab + b 2 , which are not Eisenstein triples (and not even integers), in general.

We state the following result.

=   1 -1 2 0 √ 3 2   -1
, so that . Thus,

Z 2 = {X( (p), (p)) | p ∈ Z[ω]}. Then we obtain Ř = XRX -1 = X   2a-b 2c - √ 3b 2c √ 3b 2c 2a-b 2c   X -1 =   a c -b c b c a-b c   , ( 2
the {(n k+1 -n k )b 1 } = {n k+1 b 1 } -{n k b 1 } converge to (0, 0).
In particular, we can find integers m, p, q, where m = n k+1 -n k for k large enough, such that e = mb 1 + (p, q) ∈ Ǧ has norm smaller than ε 3 . Note now that the second column of Ř satisfies b 2 = 0 -1 1 -1 b 1 . Then we claim that e = 0 -1 1 -1 e = mb 2 + (-q, p -q) also lies in Ǧ, has norm less that 3 e (hence less than ε) and is linearly independent from e (the matrix having no eigenvectors).

Consequently, b 1 has rational coefficients, and we may take a, b, c integers with gcd equal to one. Since cos θ = 2a-b c and sin θ = √ 3b 2c , we conclude that these form an Eisenstein primitive triple.

In the following, we focus on a subgroup of G obtained from the intersection with C 1 (0) i.e., Ḡ = G/Z[ω] and its translation by t (modulo Z[ω]) denoted Ḡ . Proof. Up to an affine transformation of (2.5), we may consider the quotient group G = Ǧ/Z 2 and we note that for a primitive Eisenstein triple (a, b, c), any two integers in the triple are coprime [34, p. 12]. Let us first give a characterization of G. From the proof of Proposition 2.6, we know already that any element x ∈ Ǧ is a rational vector of the form q 1 c , q 2 c , q 1 , q 2 ∈ Z. By definition, {x} ∈ G if and only if there exist n, m ∈ Z such that {x} = {nb 1 + mb 2 }, i.e. there exist integers n, m, u, v such that

   q 1 c + u = n a c -m b c , q 2 c + v = n b c + m a-b c
or equivalently,

   q 1 + uc = an -bm, q 2 + vc = bn + am -bm .
A linear combination of both lines yields directly bq 1 -aq 2 = c(-cm -bu + av), hence bq 1 -aq 2 ≡ 0 (mod c) is a necessary condition. It is also sufficient. Indeed, let us suppose that bq 1 -aq 2 = kc, k ∈ Z. Then, since gcd(a, b) = 1, we know that the solutions to this Diophantine equation are of the form (q 1 , q 2 ) = (a, b) + kc(β, -α), where αa + βb = 1 (Bézout identity) and ∈ Z. Consequently, (

q 1 c , q 2 c ) = b 1 + (kβ, -kα) lies in Ǧ.
Moreover, we deduce that G is cyclic with generator b 1 . Finally, { b 1 } = (0, 0) implies a = uc and b = vc for some integers u, v. Applying the Gauss's lemma to coprimes a, c, we see that needs to be a multiple of c. Therefore, | G| = c.

Density of Eisenstein Rational Rotations

In the case of rational rotations given by Pythagorean triples it is known that they are dense [START_REF] Anglin | Using Pythagorean Triangles to Approximate Angles[END_REF]. In other words, picking any angle θ it is always possible to find a Pythagorean angle, which is as close to θ as one wishes. On the other hand, in the case of Eisenstein rational rotations we provide the following result.

Lemma 2.8. Eisenstein rational rotations are dense.

Proof. Let θ ∈ R be any angle. Then there are u, v ∈ R such that θ = arg (u + vω).

For a rational rotation to have an angle close to θ, we need

α = a + bω ∈ Z[ω] ρ to satisfy b a ≈ v u .
The same reasoning holds for the square roots of α (see Chapter 5, Lemma 5.2). Hence, we might as well work with γ = (s + t) + tω, and prove that the ratio s+t t takes a dense set of values in R. Equivalently, we prove that any number x can be approximated with arbitrary precision by a ratio s/t where s, t ∈ Z, gcd(s, t) = 1 and s -t ≡ 0 (mod 3). The first constraint is satisfied by the rational approximations of a real number. There remains to show that we can choose s, t ∈ Z so that s -t ≡ 0 (mod 3). Without loss of generality, we restrict to denominators t that are prime; since these can be chosen arbitrarily large, the approximation property still holds. Now consider s t , s+1 t and s-1 t . For t large enough, they are all very close to x ∈ R, so approximation is not an issue. Among these three numerators, only one can be equal to 0 mod 3, and we consider the two remaining ones. Finally, we note that the two numerators cannot be multiples of t, because their difference-which is equal to 1 or 2-would also be multiple of t.

Chapter 3

Local Alterations Induced by

Digitized Rigid Motions

In this chapter we develop theoretical tools necessary in the study of local alterations induced by digitized rigid motions. In particular, we consider a neighborhood of p ∈ Z[κ κ κ] and we focus on the issue of neighborhood alterations, by making a connection between such alterations and the position of U(p) in a digitization cell. Though, several notations are defined and used to explain the issue of the alterations we mostly use these notations in the following chapters.

Neighborhood Motion Map

In the complex plane, an intuitive way to define a neighborhood of x ∈ C is to consider the set of complex numbers that lie within a ball of a given radius centered at x. This metric definition actually remains valid in the considered discrete spaces, where it allows us to retrieve the classical notion of neighborhood based on adjacency relations.

Definition 3.1 (Neighborhood). The neighborhood of p ∈ Z[κ κ κ] (of squared radius r ∈ R + ), denoted N r (p), is defined as N r (p) = p + d ∈ Z[κ κ κ] | |d| 2 ≤ r .
In order to track these local alterations of the neighborhood of Gaussian (resp. Eisenstein) integers, we introduce the notion of a neighborhood motion map, that is defined as a set of elements of Z[κ κ κ], each representing information about a neighbor after a rigid motion. Definition 3.2 (Neighborhood motion map). Let p ∈ Z[κ κ κ] and r ∈ R + . Let U : Z[κ κ κ] → Z[κ κ κ] be a digitized rigid motion (see Section 2.6). The neighborhood motion map of p with respect to U and r is the function defined as

G U r (p) : N r (0) → N r (0) d → U (p + d) -U (p)
(with r ≥ r). Note that r is determined by r and the underlaying space. In other words, G U r (p) associates to each relative position of q = p + d ∈ Z[κ κ κ] in the neighborhood of p, the relative position of the image U (q) in the neighborhood of U (p).

Note that a similar idea was previously proposed by Nouvel and Rémila [START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF] to track local alterations of the neighborhood N 1 defined on the square grid under 2D digitized rotations.

Remark 3.3. For the sake of readability, we will consider a visual representation of the G U r (p) functions as label maps. A first-reference-map L r will associate a specific label to each element d = qp of N r (0) for a given squared radius r (see Figure 3.1(a-c), for the maps L 1 and L 2 on Z[i] and L 1 on Z[ω]). A second map L U r (p)-associated to G U r (p), i.e. to p ∈ Z[κ κ κ] and a digitized rigid motion U -will associate, to each r ∈ N r (0), the labels of all the points q ∈ Z[κ κ κ] such that r = U (q) -U (p). Such a set of labels for each r may contain 0, 1 or 2 labels, due to the possible mappings under digitized rigid motions (see examples in Figure 3.2).

Remainder Range Partitioning and Neighborhood Motion Maps

Digitized rigid motions U = D • U |Z[κ κ κ] are piecewise constant, which is a consequence of the nature of D. In other words, the neighborhood motion map G U r (p) evolves noncontinuously according to the parameters of U |Z[κ κ κ] that underlies U . Our purpose is now to express how G U r (p) evolves.

Let us consider p + d ∈ Z[κ κ κ], in the neighborhood N r (p) of p. From Formula (2.1) we have

U(p + d) = θ • d + θ • p + t. (3.1)
We know that U(p) lies in a digitization cell C 1 (U (p)) centered at U (p), which implies that there exists a value

ρ(p) = U(p) -U (p) ∈ C 1 (0).
U(p + d) = θ • d + ρ(p) + U (p).
Without loss of generality, we can consider that U (p) is the origin of a local coordinate frame of the image space, i.e. U(p) ∈ C 1 (0). In such a local coordinate frame the former equation rewrites as

U(p + d) = θ • d + ρ(p).
∈ Z[κ κ κ], G U r (p) = G U r (q)
if and only if ρ(p) and ρ(q) are in the same frame.

In other words, Proposition 3.5 tells us that there exist a unique link between a frame and a neighborhood motion map. Note that a similar result-in the case of digitized rotations on Z[i]-was provided by Nouvel and Rémila [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF].

H -θ H + θ H -θ • (-i) H -θ • i (a) H -θ H + θ H -θ • (-i) H -θ • i H -θ • (-1 + i) H -θ • (1 -i) H -θ • (1 + i) H -θ • (-1 -i) (b) H -θ H -θ • (-ω) H + θ H -θ • ω H -θ • (-ω) H -θ • (-ω) (c)

Set of Neighborhood Motion Maps

From the above discussion, it is plain that a partition of the remainder range given by C 1 (0) ∩ H depends on the rotation angle θ = arg(θ). In order to detect the set of all neighborhood motion maps for r = 1, 2, i.e. equivalence classes of rigid motions U |Nr(p) , we need to consider critical angles i.e., angles that lead to topological changes of C 1 (0) ∩ H. Indeed, from Proposition 3.5, we know that this is equivalent to computing all different frames in the remainder range. Such changes occur when at least one frame has a null area i.e., when at least two parallel line segments which bound a frame have their intersection equal to at least a line segment. To illustrate this issue, let us consider the minimal distance among the distances between all pairs of the parallel line segments in the remainder range. Thanks to rotational symmetries by an angle of π k -where k = 4 for the square and k = 6 for the hexagonal grids-and based on the above discussion, we can restrict, without loss of generality, the parameter space of (x, y, θ) to C 1 (0) × 0, π k . and hexagonal (c) grids for rotation angle θ = π 12 . The partitions presented in (a) and (c) are for N 1 (0), and in (c) for N 2 (0). Each frame-border color corresponds to the color of each neighbor in the corresponding label maps (see Figure 3.2).

Then, our goal is to observe the set of all distinct neighborhood motion maps

M r = U∈U p∈Z[κ κ κ] G U r (p) .
x + u cos θ -v sin θ = k x + 1 2 (3.2) y + u sin θ + v cos θ = k y + 1 2 (3.3)
where k x , k y ∈ Z. Indeed, critical angles are such angles for which at least two critical lines are coincident.

Then, in the case of r = 1 there is only one critical angle π 6 , and for r = 2 and θ ∈ 0, π 4 we have to consider four critical angles α n , n ∈ {1, 2, 3, 4}, each inducing change of the order of critical lines. Note that, α 0 = 0 and α 5 = π 4 are also critical angles. U, except for finitely many critical angles. For instance, we have

p∈Z[i] G U 1 (p) = 1
for θ = 0, 16 for θ = π 6 , and 9 for θ = π 4 .

Such elements of sets M 1 and M 2 are presented in Appendix A and Appendix B, respectively. Each neighborhood motion map given in the appendices can be identified thanks to indexes of associated frames of the remainder range. We can remark that neighborhood motion maps are symmetric with respect to the origin-the frame of the index (0, 0). For example, the neighborhood motion map of the index (-3, 4) is symmetric to Hexagonal grid. In the case of r = 1 there exist two critical angles between 0 and π 6 , denoted by α 1 and α 2 , with 0 < α 1 < α 2 < π 6 . Note that the angles 0 and π 6 are also critical and are denoted α 0 and α 3 , respectively. On the one hand, Figure 3.7 provides a plot of minimal distances between parallel line segments in the remainder range. A critical angle happens when such a minimal distance is equal to zero. On the other hand, Figure 3.5(c) presents a partition of the remainder range for an angle θ ∈ (α 0 , α 1 ). The cardinality of M 1 is equal to 67, and we note that hexagonal lattice and each can be identified thanks to its axial coordinates [START_REF] Middleton | Hexagonal Image Processing: A Practical Approach[END_REF]. We note that in such an arrangement neighborhood motion maps are symmetric with respect to the origin-the frame of the index (0, 0). For example, the neighborhood motion map of the index (-4, 3) is symmetric to that of the index (4, -3) (see Figure C.1).

p∈Z[ω] G U 1 (p) is constant: 49 for any U, except for θ = α i , i ∈ {0, 1, 2, 3}. Indeed, we have p∈Z[ω] G U 1 (p) = 1 for θ = α 0 ,

Neighborhood Motion Maps Graph

Let us consider as well the dual of the remainder range partitioning-presented in Fig-

Non-surjectivity and Non-injectivity of Digitized Rigid

Motions

In this section, we identify zones of the remainder range (unions of frames) which exhibit non-injectivity and non-surjectivity of the corresponding digitized rigid motions. This allows us to compare the loss of information induced by digitized rigid motions defined on the square and hexagonal grids. ρ(p) is in one of the zones f 0 $ (union of frames themselves) defined as follows:

f 0 ↑ = 1 2 -cos θ, sin θ - 1 2 ⊕ 3 2 (-cos θ -sin θ) , 1 2 i, f 0 → = 3 2 -cos θ -sin θ, 1 2 ⊕ 1 2 -sin θ , cos θ - 1 2 i, f 0 ↓ = 1 2 -sin θ, cos θ - 1 2 ⊕ - 1 2 , cos θ + sin θ - 3 2 i, f 0 ← = - 1 2 , cos θ + sin θ - 3 2 ⊕ 1 2 -cos θ , sin θ - 1 2 i,
where $ ∈ {↑, →, ↓, ←} and d ↑ = (0, 1),

d → = (1, 0), d ↓ = (0, -1), d ← = (-1, 0).
The non-surjective zones are defined by three critical lines given by N 1 (0) and one given by N 2 (0). if and only if ρ(p) is in one of the zones f 2 $ defined as follows:

Neighborhood motion maps which present non-injectivity can be observed in Ap

f 2 ↑ = sin θ - 1 2 , 1 2 ⊕ - 1 2 , 1 2 -cos θ i, f 2 → = - 1 2 , 1 2 -cos θ ⊕ - 1 2 , 1 2 -sin θ i, f 2 ↓ = - 1 2 , 1 2 -sin θ ⊕ cos θ - 1 2 , 1 2 i, f 2 ← = cos θ - 1 2 , 1 2 ⊕ sin θ - 1 2 , 1 2 i.
We can characterize the non-surjectivity and non-injectivity of a digitized rigid motion by the presence of ρ(p) in these specific zones. Both types of zones are presented in In accordance with the discussion in Chapter 2 and the similar discussion for the square grid in [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Berthé | Discrete Rotations and Symbolic Dynamics[END_REF], the density of images of the remainder map ρ in the non-injective zones is related to the cardinality and the structure of the group Ḡ = G \ Z[κ κ κ] of the images of ρ. On the one hand, when Ḡ is dense, it is considered as the ratio between the area of non-injective zones c k (f ), k = 1, . . . , 6 (resp. f 2 $ ), and the area of the remainder range [START_REF] Berthé | Discrete Rotations and Symbolic Dynamics[END_REF]. On the other hand, when Ḡ forms a lattice, it is estimated as

(cos θ -1) + cos θ √ 3 i, 1 √ 3 i, 1 2 2 -cos θ - √ 3 sin θ + 1 6 √ 3 cos θ + 3 sin θ i, 1 2 cos θ - √ 3 sin θ + 1 6 f 2 ↓ f 2 ↑ f 2 → f 2 ← f 0 ↑ f 0 → f 0 ↓ f 0 ← (a) f c 1 (f ) c 2 (f ) c 3 (f ) c 4 (f ) c 5 (f ) (b)
| Ḡ∩c k (f )| c , k = 1, . . . , 6 (resp. | Ḡ∩F| c , F = f 2 ↑ ∪ f 2 → ∪ f 2 ↓ ∪ f 2 ← )
, where c is an element of a primitive Eisenstein (resp. Pythagorean) triple i.e., | Ḡ| [START_REF] Berthé | Discrete Rotations and Symbolic Dynamics[END_REF].

Nevertheless, to facilitate, our study we will consider the ratio between the areas as an approximation of the information loss measure. Indeed, the rotations induced by primitive Eisenstein (resp. Pythagorean) triples are dense; one can always find a relatively near rotation angle such that c is relatively high. The area-ratio density measure can be then seen as a limit for the cardinality based ratio. Figure 3.9 presents curves of the area ratios for the square and hexagonal grids.

We also measure the loss of information for different sampled rotations and the following finite sets

S κ κ κ = Z[κ κ κ] ∩ [-100, 100] ⊕ [-100, 100]i. In this setting, we use 1 -|U (Sκ κ κ )| |Sκ κ κ |
as a measure of the information loss. They are plotted in Figure 3.9. We note that the experimental results follow the area-ratio measure, that provides consequently a good approximation 1 . The obtained results allow us to conclude that digitized rigid motions 1 Similar attempt was made in [START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF], but with a different approach of measuring. Comparison of the loss of information induced by digitized rigid motions on the hexagonal and square grids. The red and blue curves correspond to the ratios between areas of non-injective zones and the remainder range for the square and hexagonal grids, respectively. The "x" (resp. "o") markers correspond to the values of the information loss rate 1-

|U (S i )| |S i | (resp. 1-|U (Sω)| |Sω| ).
on the hexagonal grid preserve more information than their counterparts defined on the square grid.

Future Work and Conclusion

In the chapter, we have extended the notion of neighborhood motion maps to rigid motions and any neighborhood defined on either the regular hexagonal or the square grid. The framework was previously proposed by Nouvel and Rémila [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF] for digitized rotations and 4-neighborhood defined on the square grid. In the next chapters we have shown that these notions are useful to characterize the bijectivity of rigid motions on

Z[κ κ κ].
One problem which we have not yet tackled is related to a use of neighborhood motion maps in image processing applications in order to speed up digitized rigid motions. The principal of such an idea is based on an observation that having computed a neighborhood motion map of p ∈ Z[κ κ κ] we known, once and for all, the relative positions of the points in N r (p) under U . Therefore, having computed the set M 2 and representing it as a lookup table will allow us to reduce the number of points of such digital sets to which it is necessary to directly apply a digitized rigid motion. The position of the remaining points can be then obtained via neighborhood motion maps. We call this approach Nozick motions2 . In the current stage, we are working on an optimal implementation of the Nozick motion algorithm.

As a part of our future research we also plan to extend the study of non-surjective digitized rigid motions to the hexagonal grid. Indeed, if the same approach as for the square grid is followed, this would require to compute the neighborhood motion maps

of N 4 (p), p ∈ Z[ω].
Finally, for a sake of completeness of the study we would like to provide an extended comparison of the information loss between digitized rigid motions defined on the all three regular grids, i.e. the triangular, the square and the hexagonal grids.

Chapter 4

Bijective Digitized Rigid Motions on Square Grid

Due to digitization, digitized rigid motions do not preserve distances and bijectivity is generally lost. Nevertheless, some of them are globally bijective or bijective when restricted to some finite digital sets.

In this chapter we first extend the characterization of bijective digitized rotations [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF] to the case of digitized rigid motions i.e., rotations followed by translations and a digitization operation. We restrict then to the practical problem of verifying whether a prescribed subset of Z[i] is transformed bijectively (or more precisely injectively) by a digitized rigid motion. To this end, the local approach of neighborhood motion maps is well suited and leads to an algorithmic answer. More concretely, two different algorithms are proposed. The performance of each depends on the ratio of the finite set size to the complexity of the rigid motion, measured by the integers of the Pythagorean triples.

This algorithmic approach can be extended for finding, for a given subset S ⊂ Z[i] and an injective rigid motion on S, a range of nearby parameter values ensuring injectivity, thereby offering a stability result. This is done by extending the concept of hinge angles of digitized rotations [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF][START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF][START_REF] Thibault | Computing Upper and Lower Bounds of Rotation Angles from Digital Images[END_REF] to digitized rigid motions.

Globally Bijective Digitized Rigid Motions

A digitized rigid motion is bijective if and only if there is no ρ(p) for all p ∈ Z[i] in non-surjective and non-injective zones of C 1 (0). In this section, we characterize bijective rigid motions on Z[i] while investigating such local conditions.

Let us start with the rotational part of the motion. When the group G (see Chapter 2)

is not a lattice, then we have the following.

Lemma 4.1. If G is not a lattice then the corresponding digitized rotation given by θ is not bijective.

Proof. Since G is dense then an intersection of Ḡ = G \ Z[i] with non-injective (resp.

non-surjective) zones of the remainder range is nonempty.

In the other words, for rotations with angles of irrational sine or cosine ∃p ∈ Z[i] such that ρ(p) lies in a non-surjective and/or non-injective zone of C 1 (0). This result is also applied to U , whatever translation part is added. Therefore, we focus on rigid motions which are given by Pythagorean rational rotations discussed in Chapter 2.

When U contains a translation part, the images of ρ in C 1 (0), which we denote by Ḡ , is obtained by translating Ḡ (modulo Z[i]), and | Ḡ | is equal to the order of Ḡ -its underlying group. Then, we state the following proposition.

Proposition 4.2. A digitized rational rotation is bijective (the intersection of Ḡ with non-injective and non-surjective regions is empty) if and only if its angle comes from a

twin Pythagorean triple, i.e. a primitive Pythagorean triple (see Lemma 2.1) with the additional condition on the generators that p = q + 1.

For more information about the bijective digitized rotations and their characterization we encourage readers to consult Nouvel and Rémila [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF], or more recent results by Roussillon and Coeurjolly [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF].

Our question is then if a digitized rigid motion can be bijective, even though the corresponding rotation is not. In order to answer this question we use the following equivalence property.

Property 4.3 (Nouvel and Rémila [22]). Digitized rational rotations are bijective if they are surjective or injective.

Indeed, Property 4.3 allows us to focus only on non-surjective zones; since they are squares, they provide symmetry and then present interesting properties in terms of exact computing.

Proposition 4.4. A digitized rigid motion whose rotational part is given by a non-twin

primitive Pythagorean triple is always non-surjective.

Proof. We show that no translation factor can prevent the existence of an element of Ḡ in a non-surjective zone. We consider the length of a side of f 0 $ , given by L 1 = 2q(p-q) c , and the side of the bounding box of a fundamental square in Ḡ, given by L 2 = p+q c (see [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF]), where p and q are generators of the corresponding primitive Pythagorean triple (see Lemma 2.1). Note that any non-surjective zone f 0 $ also forms a square. Then by comparing L 1 with L 2 , we have that, as p > q + 1, L 2 < L 1 , and thus Ḡ ∩ f 0 $ = ∅ (see Figure 4.1(a)).

If, on the contrary, the rotational part of the rigid motion is given by a twin Pythagorean triple, i.e. is bijective, then the rigid motion is also bijective, under the following condition. Note that ψ ψ ψ and φ φ φ are the same as in Corollary 2.5.

Proposition 4.5. A digitized rigid motion is bijective if and only if it is composed of a rotation by an angle defined by a twin Pythagorean triple and a translation

t = t + Zψ ψ ψ + Zφ φ φ, where t ∈ -1 2c , 1 2c ⊕ -1 2c , 1 2c i.
Proof. Let us first consider the case t = 0. Since L 2 > L 1 , there exists a fundamental square in Ḡ, i.e. a square whose vertexes are (nφ φ φ+mψ ψ ψ), ((n+1)φ φ φ+mψ ψ ψ), ((n+1)φ φ φ+(m+

1)ψ ψ ψ), (nφ φ φ + (m + 1)ψ ψ ψ),
where n, m ∈ Z. Note that the vertexes lie outside of f 0 ↓ , at N ∞ distance 1 2c (see Figure 4.1(b) and the proof of Theorem 5 in [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF]). Now, let us consider the case t = 0. The above four vertexes are the elements of Ḡ closest to f 0 ↓ , therefore if N ∞ ({t}) < 1 2c , where {.} stands for the fractional part function, then Ḡ ∩ f 0 ↓ = ∅. Moreover, if N ∞ ({t}) is slightly above 1 2c , then it is plain that some element of Ḡ will enter the frame f 0 ↓ . But Ḡ is periodic with periods φ φ φ and ψ ψ ψ, so that the set of admissible vectors t has the same periods. Then, we see that the admissible vectors form a square (i.e. a N ∞ ball of radius 1 2c ) modulo Zψ ψ ψ + Zφ φ φ (see Figure 4.1(c)).

Locally Bijective Digitized Rigid Motions

As seen above, the bijective digitized rigid motions, though numerous, are not dense in the set of all digitized rigid motions. Thus, we may generally expect defects, such as Gaussian integers with two preimages. However, in practical applications, the bijectivity of a given U on the whole Z[i] is not the main issue; rather, one usually works on a finite subset of the plane e.g., a square digital image. The relevant question is then: "given a finite subset S ⊂ Z[i], is U restricted to S bijective?". Actually, the notion of bijectivity in this question can be replaced by the notion of injectivity, since the surjectivity is trivial, due to the definition of U that maps S to U (S). The basic idea for such local bijectivity verification is quite natural. Because of its quasiisometric property, a digitized rigid motion U can send at most two 4-neighbors-two Gaussian integers such that their digitization cells share an edge-onto the same point.

2q(p-q) c (p+q) c 2q(p-q) c (p+q) c 1 -3i 2 -i -3i 1 -2i -1 + i -1 1 -i -2 -2 -i 2 -2i -2i -2 -2i -3 -2 + i 2 -3i -3 -2i 3 1 -i -1 -i -3 -i -1 -2i 2 3 + 2i i 1 + i 2 + i 3 + i -2 + 2i -1 + 2i 2i 1 + 2i 2 + 2i -2 + 3i -1 + 3i 3i (a) 2q(p-q) c (p+q) c 2q(p-q) c (p+q) c w s r c 1 + i) -2 + 2i -1 -2i 2 + i 1 + 2i -2 -2i -i 1 -i -1 + i -2 + i 1 2 -1 2i i -3i 3i -3 3 (b) f 0 ↓ (c)
Thus, the lack of injectivity is a purely local matter, suitably handled by the neighborhood motion maps via the remainder map. Indeed, in accordance with Lemma 3.7, U is non-injective, with respect to S if and only if there exists p ∈ S such that ρ(p)

lies in the union F = f 2 ↓ ∪ f 2 ↑ ∪ f 2 ← ∪ f 2
→ of all non-injective zones. We propose two algorithms making use of the remainder map information, as an alternative to a brute force verification.

The first-forward-algorithm, checks for each p ∈ S, the inclusion of ρ(p) in one of the non-injective zones of F. The second-backward-algorithm first finds all w in Ḡ ∩ F, called the non-injective remainder set, and then verifies if their preimages ρ -1 (w) are in S.

Both algorithms apply to rational motions i.e., with a Pythagorean angle given by a primitive Pythagorean triple (see Chapter 2) and a rational translation t = t 1 + t 2 i with t 1 , t 2 ∈ Q. We capture essentially the behavior for all angles and translation vectors, since rational motions are dense and S is finite, so that a close-enough angle yields an identical result. These assumptions guarantee the exact computations of the algorithms, which are based on integer numbers. Methods for angle approximation by Pythagorean triples up to a given precision may be found in [START_REF] Anglin | Using Pythagorean Triangles to Approximate Angles[END_REF][START_REF] Ostromoukhov | Reproduction Couleur par Trames Irrégulières et Semi-régulières[END_REF].

Forward Algorithm

The strategy consists of checking whether the image of each p ∈ S under the remainder map ρ(p) belongs to one of the non-injective zones f 2 $ defined in Lemma 3.7; if this is the case, we check additionally if p + d $ ∈ N

B ← ∅ foreach p ∈ S do foreach $ ∈ {→, ↓} do if p + d $ ∈ S and ρ(p) ∈ f 2 $ then B ← B ∪ {{p, p + d $ }} S ← S \ {p, p + d $ } break return B
The main advantage of the forward algorithm lies in its simplicity. In particular, we can directly check which neighbor p + d $ of p has the same image under a digitized rigid Remark 4.6. The forward algorithm can be used with non-rational rigid motions, at the cost of a numerical error.

(a) (b) (c)

Backward Algorithm

In this section, we consider a square finite set S as the input; this setting is not abnormal, as we can find a square bounding box for any finite set. The strategy of the proposed backward algorithm consists of: Step 1: for a given U , i.e. a Pythagorean triple and a rational translation, enumerate all the elements w ∈ Ḡ in the non-injective zones and

obtain W = {w | w ∈ Ḡ ∩ F};
Step 2: compute the set of all the preimages, i.e.,

W -1 = {ρ -1 (w) | w ∈ W };
Step 3: determine among them those in S, i.e. S ∩ W -1 .

Step 1

As explained in Chapter 2, the cyclic group Ḡ is generated by ψ ψ ψ = p c + q c i and φ φ φ = -q c + p c i, and Ḡ is its translation (modulo Z[i]). Therefore, all the points in Ḡ can be expressed as {Zψ ψ ψ + Zφ φ φ + t}, where {.} stands for the fractional part function defined on C. To find these elements of Ḡ in the non-injective zones, let us focus on f 2 ↓ , which was given in Lemma 3.7. (Note that a similar discussion is valid for any other non-injective zones given by Lemma 3.7). The set of remainder points {Zψ ψ ψ + Zφ φ φ + t} lying in f 2 ↓ is then formulated by the following four linear inequalities-critical lines bounding f 2 ↓ -and we define the non-injective remainder index set C ↓ such that

C ↓ =    (u, v) ∈ Z 2 -1 2 < { p c u -q c v + (t)} < 1 2 -2pq p 2 +q 2 , p 2 -q 2 p 2 +q 2 -1 2 < { q c u + p c v + (t)} < 1 2    . (4.1)
Solving the system of inequalities in Equation (4.1) consists of finding all pairs (u, v) ∈ Z 2 inside the given rectangle. This is carried out by mapping {Zψ ψ ψ + Zφ φ φ + t} to Z 2 using a similarity, denoting by f 2 ↓ the image of f 2 ↓ under this transformation (Figure 4.3).

To determine all the integer points in (u, v) ∈ C ↓ , we first consider the upper and lower corners of the rectangular region f 2 ↓ given by Equation (4.1), i.e. p-3q 2 , p-q 2 and q-p 2 , p+q

2

. Then, we find all the horizontal lines v = k where k ∈ Z ∩ p-q 2 , p+q The complexity of this step depends on the number of integer lines crossing f 2 ↓ , which is q, and thus it leads to O(q). Step 2

u -2 -3 1 -1 2 1 4 5 v (a) (b)
We seek the set of all preimages of {uψ ψ ψ + vφ φ φ + t} for each (u, v) ∈ C ↓ , or equivalently, preimages of uψ ψ ψ + vφ φ φ by the translationless remainder map (the fact that this point is in f 2 ↓ plays no role in this step). This is a Diophantine system (modulo Z 2 ), and the set of preimages of a point {uψ ψ ψ + vφ φ φ + t} is given by a sublattice of Z 2 . Lemma 4.7. Let (u, v) stands for the index of an element of Ḡ. Then all preimages of uψ ψ ψ + vφ φ φ form a lattice

T(u, v) = p µ -v 2 (u + vi) + Z(b + ai) + Z(σ + τ i)c, (4.2)
where µ and ν are Bézout coefficients of the identity µp 2 + νq 2 = 1 such that µ ± ν ≡ 0 (mod 2), and σ and τ are Bézout coefficients of the identity aσ + bτ = 1.

Proof. First, we start by looking for preimages of ψ ψ ψ = p c + q c i, and by using the fact that Ḡ is cyclic we consider x ∈ Z and try to solve

     a c x ≡ p c (mod 1) b c x ≡ q c (mod 1) or      ax ≡ p (mod c) bx ≡ q (mod c) .
The first equation is solved using Bézout identity. Then, using the fact that c -a = 2q 2 , c + a = 2p 2 , and µp 2 + νq 2 = 1 since gcd(p 2 , q 2 ) = 1, we find that

1 = µp 2 + νq 2 = µ c + a 2 + ν c -a 2 ,
and we observe that by rearranging the terms of the right-hand side we obtain

1 = a µ -ν 2 + c µ + ν 2 .
Next, ax ≡ p (mod c) if and only if ax + cz = p for some z ∈ Z, and then the solutions are of the form x = p µ-ν 2 + kc, for some k ∈ Z with µ = µ 0 + ck and ν = ν 0 -ak. Where µ 0 and ν 0 are some initial coefficients found using Extended Euclidean Algorithm. Here we assume that µ and ν are odd thus µ ± ν ≡ 0 (mod 2). We can make this assumption because (i) p -q ≡ 1 (mod 2), and (ii) because the Bézout coefficients are not unique and if µ and ν are not both odd we can replace them with a pair (µ + q 2 , ν -p 2 ).

Then we check the second equation bx ≡ q (mod c). The solution is then p µ-ν 2 + kc. In a similar way it can be verified for φ φ φ = -q c + p c i and ȳi, ȳ ∈ Z.

bx ≡ 2p 2 q µ -ν 2 = q(p 2 µ -p 2 ν) = q(1 -q 2 ν -p 2 ν) = q -cν ≡ q (mod c).

Second, we solve for

     ax -bȳ ≡ 0 (mod c) bx + aȳ ≡ 0 (mod c) .
We have that gcd(a, b) = 1 and therefore the following Bézout identity aσ + bτ = 1 has solutions, and we have that x = σck and ȳ = -τ ck. Therefore, the second equation is satisfied modulo c. But we want both of them to be satisfied, i.e. we want ax -bȳ = ck to be also true. Let us focus on ax = bȳ. This is true when x = bz and ȳ = az. By putting all together we obtain x = σck + bz and ȳ = -τ ck + az. We then check a(σck + bz) -b(-τ ck + az) = aσck + abz + bτ ck -baz = aσck + bτ ck, and we see that the right-hand side is satisfied due to Bézout identity and b(σck

+ bz) + a(-τ ck + az) = bσck + b 2 z -aτ ck + a 2 z = ck(bσ -aτ ) + c 2 z,
is also satisfied indeed modulo c. This leads us to the result.

The time complexity of finding µ and ν (resp. σ and τ ) is O(log q) (resp. O(log min(a, b)) [START_REF] Hunter | Essentials of Discrete Mathematics[END_REF]. As the Bézout coefficients are computed once for all (u, v) ∈ C ↓ , the time complexity

of Step 2 is O(log q) + O(log min(a, b)) = O(log min(a, b)).
Step 3

We now consider the union of lattices T(u, v) for all couples (u, v) in C ↓ obtained in

Step 1. To find their intersection with S, we apply to each an algorithm similar to

Step 1 -with an affine transformation mapping the basis b + ai, c(σ + τ i) to 1, i and p µ-v 2 (u + vi) to 0, respectively. Thus, a square S maps to a quadrangular Ŝ after such an affine transformation, and we find the set of Gaussian integers in Ŝ. Note that the involved transformation is the same for all the lattices, up to a translation.

The complexity of listing all the preimages is given by |C ↓ | times the number of horizontal All the steps together allow us to state that the backward algorithm, whose time complexity is O(q + log min(a, b) + |S|), identifies non-injective Gaussian integers in finite square sets.

lines v = k, k ∈ Z, intersecting Ŝ, denoted by K. The cardinality of C ↓ is related to the area of f 2 ↓ given by 2q 2 (p-q) 2 (p 2 +q 2 ) 2 , which cannot be larger than 3 2 - √ 2. As | Ḡ | = c and |C ↓ | = | Ḡ ∩ f 2 ↓ |, |C ↓ | ≤ ( 3 2 - √ 2)c.
Remark 4.9. Even though the backward algorithm works with squares, one can approximate any set S by a union of squares and run the backward algorithm on each of them.

There can be false positives; however these can be discarded one-by-one by verifying whether they lie in S or not.

The proposed algorithms differ from a simple injectivity verification, which can be implemented using a multimap as a data structure such that each key represents a point of the transformed space and each value associated with a single key represents a set of its preimages. Since the usual complexity of operations defined on a multimap is O(log n)-n standing for the number of keys-this strategy provides a linear time complexity with respect to the size of the input digital set; nevertheless, it requires more memory than the forward or backward algorithms. Note that from a practical point of view the choice between the forward and the backward algorithm depends on the size of the input digital set S and the parameters' values of the rational rotation. Indeed, when the cardinality of S is relatively low and the cardinality of Ḡ (actually Ḡ ∩ F) is relatively high, the forward algorithm is usually a better choice than the backward algorithm and vice versa1 .

Finding a Local Bijectivity Angle Interval

The algorithms discussed in the previous section can verify if a digitized rigid motion restricted to a finite digital set S ⊂ Z[i] is bijective. Such a digitized rigid motion is

given by a triplet of parameters (t 1 , t 2 , θ)-where θ is a Pythagorean angle and t 1 , t 2 ∈ Q represent a rational translation. In this section, we consider the problem of finding a range of parameters such that the corresponding digitized rigid motions remain bijective when restricted to S. More precisely, we start with a given digitized rigid motion which is bijective when restricted to S, and we focus on finding neighboring values around the triplet (t 1 , t 2 , θ) under the condition that each digitized rigid motion from this range ensures bijectiviy on S.

Such a problem can be seen as an optimization problem, namely, finding a maximal ball B ((t 1 , t 2 , θ)) of radius , centered at a point (t 1 , t 2 , θ) and placed in the space

-1 2 , 1 2 2
× 0, π 4 with a restriction that any digitized rigid motion represented by a point of parameters w ∈ B ((t 1 , t 2 , θ)) remains bijective when restricted to a given finite set S. More formally, we look for the maximum such that for any w ∈ {w | w -(t 1 , t 2 , θ) ≤ } the corresponding digitized rigid motion is bijective restricted to

S.

Instead of solving this problem that requires to consider the three parameters simultaneously, in this section, we consider a simpler, yet practically relevant, problem by separately considering the translation and rotation parts. First, we fix the translation given by t, and find which nearby angles of rotation preserve bijectivity, by using the notion of hinge angles [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF][START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF][START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF][START_REF] Thibault | Computing Upper and Lower Bounds of Rotation Angles from Digital Images[END_REF]. More precisely, we compute the largest open interval of angles which contains the initial angle θ, such that for any angle θ in this interval, the digitized rigid motions given by θ and t remain injective on S. In particular, we show how such an interval can be computed from an extended version of the forward algorithm presented in Section 4.2. We also compute, in such an interval, angles that correspond to a change in the neighborhood motion map i.e., the local behavior of U (so that U changes but is still locally injective).

Second, one can also find, for a given angle θ, a range of translations t guaranteeing that the corresponding rigid motions remain bijective. Such a strategy consists of measuring, for each Gaussian integer p ∈ S, the distance between ρ(p) and non-injective frames f 2 $ , and returning the lowest distance. This problem is rather simple; therefore, hereafter we only consider the first problem, namely, we search for angles with a fixed translation.

Hinge Angles for Rigid Motions

In his PhD thesis [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF], Fredriksson considered digitized rotations and the transition angles which correspond to a shift in the image of a Gaussian integer p from one digitization cell to another. These special angles were further studied-and named hinge angles-by

Nouvel and Rémila [START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF] and by Thibault et al. [START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF][START_REF] Thibault | Computing Upper and Lower Bounds of Rotation Angles from Digital Images[END_REF]. In the sequel, we extend the notion of hinge angles to the case of rigid motions with a given translation.

cos α = p 1 (p 1 -t 1 ) + p 2 (p 2 -t 2 ) p 2 1 + p 2 2 (4.3)
and, in particular, when (p 1 , p 2 ) = (λ, k + 1/2),

cos α = p 1 λ + p 2 k -t 2 + 1 2 p 2 1 + p 2 2 , ( 4.4)
where

λ = p 2 1 + p 2 2 -k -t 2 + 1 2 2
. Similarly, sin α (resp. cosine/sine for (p 1 , p 2 ) = (k+1/2, λ)) can be obtained from the sum-difference identity of trigonometric functions. Proof. We give a proof similar to the one given by Thibault [START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF]Theorem 3.8]. Let α = (p 1 , p 2 , k, s) be a hinge angle and θ be an angle associated with a Pythagorean primitive triple (a, b, c), both in 0, π 2 . Also let rational translation. Then we consider

t = t 1 u 1 + t 2 u 2 i, t 1 , t 2 , u 1 , u 2 ∈ Z be a
cos α -cos θ = p 1 λ + p 2 k -t 2 u 2 + 1 2 p 2 1 + p 2 2 - a c .
We have that if θ > α then cos α -cos θ > 0. From that we have

cp 2 ((2k + 1)u 2 -2t 2 ) -2au 2 p 2 1 + p 2 2 > -2cλp 1 u 2 . (4.5)
From Inequality (4.5) we see that the right-hand side is always negative so if the lefthand side is positive we can conclude immediately. When this is not the case i.e., both sides of Inequality (4.5) are negative then we square on both sides and obtain

cp 2 ((2k + 1)u 2 -2t 2 ) -2au 2 p 2 1 + p 2 2 2 < 4c 2 λ 2 p 2 1 u 2 2 . (4.6)
We then notice that 4λ Proof. We give a proof similar to the one given by Thibault [15, Theorem 3.9]. Let α = (p 1 , p 2 , k, s) and β = (q 1 , q 2 , r, s ) be hinge angles both in 0, π 2 . Also let t =

t 1 u 1 + t 2 u 2 i, t 1 , t 2 , u 1 , u 2 ∈ Z be a rational translation. Then we consider cos α -cos β = p 1 λ + p 2 k -t 2 u 2 + 1 2 p 2 1 + p 2 2 - q 1 λ + q 2 r -t 2 u 2 + 1 2 q 2 1 + q 2 2 . (4.7)
We have that if β > α then cos α -cos β > 0. For simplicity, let

A = (q 2 1 + q 2 2 )p 2 2k -2t 2 u 2 + 1 , B = (p 2 1 + p 2 2 )q 2 2r -2t 2 u 2 + 1 , C = (p 2 1 + p 2 2
)q 1 and D = (q 2 1 + q 2 2 )p 1 . From that we can rewrite (4.7) by

u 2 (A -B) > 2u 2 Cλ -Dλ . (4.8)
On the one hand, if the left-hand side of Inequality (4.8) is negative and the right-hand side is positive then α > β. On the other hand, if the left-hand side is positive and the right-hand side is negative we have α < β.

If both signs are the same then first we compute the square of each side. On one hand, if both side are positive then by taking squares of Inequality (4.8) we obtain

u 2 2 (A -B) 2 -4u 2 2 D 2 λ 2 + C 2 λ 2 > -8u 2 2 CDλλ . ( 4.9)
On the other hand, if both side are negative then taking squares of Inequality (4.8) gives is nonnegative, then β > α. Otherwise, i.e. if both sides are negative we square the inequalities once again to obtain

-2u 2 2 AB < 4u 2 2 Cλ -Dλ 2 -u 2 2 (A 2 + B 2 ). ( 4
u 2 2 (A -B) 2 -4u 2 2 D 2 λ 2 + C 2 λ 2 2 < 64u 4 2 C 2 D 2 λ 2 λ 2 (4.11) and 4u 4 2 A 2 B 2 > u 4 2 4 Cλ -Dλ 2 -(A 2 + B 2 ) 2 , ( 4.12)
respectively. Then, Inequalities (4.11-4.12) can be verified with only integer computations.

Remark 4.13. Nouvel and Rémila proved that for t = 0, the intersection between hinge and Pythagorean angles is empty [START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF]. This property is generally lost for t = 0.

Let E t (p) = {ζ(p 1 , p 2 , k, s) | k ∈ Z, s ∈ {0, 1}}

An Algorithm for Finding the Local Bijectivity Angle Interval

Let us define an ordered set C p ⊂ E t (p) such that for any hinge angle α ∈ (inf(C p ), sup(C p )), where sup(C p ) and inf(C p ) stand for supremum and infimum of C p , the corresponding digitized rigid motion is bijective when restricted to N 1 (p), and ∃j ∈ N + such that ((

α j < θ < α j+1 ) ∧ (α j , α j+1 ∈ C p )).
We shall now build iteratively, for a given Pythagorean angle θ and a fixed rational translation t, an ordered set of hinge angles

C = p∈S E t (p) p∈S [inf(C p ), sup(C p )] ,
such that (inf(C), sup(C)) is the largest open angle interval containing θ, guaranteeing that the digitized rigid motions represented by such angles and the translation vector t are bijective while restricted to S. Let γ < t = inf(C) (resp. γ > t = sup(C)); then we initialize the angle γ < t (resp. γ > t ) with -2π (resp. 2π). To verify if the digitized rigid motion corresponding to a hinge angle α is non-injective, let cl(f 2 $ ) stands for the closure of a non-injective zone f 2 $ and let ρ α (p) stands for the remainder map such that the initial angle θ has been substituted with the angle α. Then, as α is a hinge angle, ρ α (p) is on the border of the remainder range.

To efficiently build the ordered set C, let ρ α (p) stands for the remainder map, where the initial angle θ has been substituted with an angle α. Then, the strategy consists of iterative verifying if any point p ∈ S belongs to a non-injective mapping under U . If so, we return an empty ordered set C (this is just for the sake of completeness, since we want to apply the extended algorithm to the case when U maps S injectively). Otherwise, 4 , 0, arccos 35 37 , where θ = arccos 35 37 is given by the Pythagorean triple [START_REF] Gilder | Integer-sided Triangles with an Angle of 60 •[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF][START_REF] Ngo | Topology-preserving Conditions for 2D Digital Images under Rigid Transformations[END_REF], the extended forward algorithm gives C = {(3, 5, 1, 0), (7, 7, 4, 0)}. This process is summarized in the extended forward algorithm, below. The time complexity of this algorithm is given by the number of hinge angles for the furthest Gaussian integer from the origin p = p 1 + p 2 i ∈ S which, for a given t, is lower than n = p 2 1 + p In (b-c) the Gaussian integer in the middle of the blue square has coordinates 3 + 5i and it is an image, under U , of the Gaussian integer 1 + 6i, which is at the center of the red square in (a). Please, note that the parameters were obtained with a very experimental implementation of the presented algorithm. Therefore, they may not be complete or correct. )) are marked by the gray triangles (resp. the red circles) and their digitization cells are depicted as black (resp. red dotted) line segments. The arrows which correspond to bijective and non-bijective mappings are marked in blue and green (resp. brown), respectively. (see Formula (5.1)). [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF]:

the
= {γ < t = α 0 , α 1 , . . . , α n-1 , γ > t = α n }. γ < t ← -2π γ > t ← 2π C ← {γ < t , γ > t } foreach p ∈ S do if ForwardAlgorithm(N 1 (p) ∩ S, θ, t) = ∅ then return ∅ foreach # ∈ {<, >} do α ← h # t (p, θ) while α ∈ (γ < t , γ > t ) do if (p + d → ∈ S and ρ α (p) ∈ cl(f 2 → )) or (p + d ↓ ∈ S and ρ α (p) ∈ cl(f 2 ↓ )) then γ # t ← α else C ← C ∪ {α} α ← h # t (p, α) C ← C \ {α | α ∈ C, α / ∈ (γ < , γ > )} return C (a) (b) (c)

Roussillon and Coeurjolly

     ∀λ ∈ Z[ω], ∃κ ∈ Z[ω], U(κ) ∈ C 1 (λ) ∀κ ∈ Z[ω], ∃λ ∈ Z[ω], λ ∈ C θ |θ| (U(κ)).
(5.1) Instead of studying the whole source and target spaces, we study the set of remainders defined by the map

S θ : Z[ω] × Z[ω] → C (κ, λ) → κ•θ |θ| -λ.
Then, (5.1) can be rewritten as and thus c = 3|ν| 2 , which means that 3 divides c. From [34, Theorem 1], we know that 3 does not divide c for a valid prime Eisenstein triple, which contradicts the hypothesis that ν exists.

     ∀λ ∈ Z[ω], ∃κ ∈ Z[ω], S θ (κ, λ) ∈ C 1 (0) ∀κ ∈ Z[ω], ∃λ ∈ Z[ω], S θ (κ, λ) ∈ C θ |θ| (0) , (5.2) provided that S θ (Z[ω], Z[ω]) ∩ C 1 (0) = S θ (Z[ω], Z[ω]) ∩ C θ |θ| (0). In other words S θ (Z[ω], Z[ω]) ∩ ((C 1 (0) ∪ C θ |θ| (0)) \ (C 1 (0) ∩ C θ |θ| (0))) = ∅.

Factorization of Primitive Eisenstein Integers

θ = γ • γ, (5.3)
|θ| = c = γ • γ, (5.4)
To prove (5.6), let us consider prime factors {π i } n of γ (resp. {π i } n of γ). We have

γ = π 1 • π 2 . . . π n (resp. γ = π1 • π2 . . . πn )
. Such prime factors are uniquely defined up to their associates. From (5.5) and Lemma 5.1, prime factor decomposition of γ and γ have no common factor (beside units) and thus gcd(γ, γ) = 1.

Finally, the statement (5.7) follows from Equations (5.3-5.4) and (5.6).

Reduced Set of Remainders

Z[ω] × Z[ω] → Z[ω] (κ, λ) → κ • θ -|θ|λ .
(5.8) Indeed, Formula (5.2) is rewritten by

     ∀λ ∈ Z[ω] ∃κ ∈ Z[ω], Šθ (κ, λ) ∈ C |θ| (0) ∀κ ∈ Z[ω] ∃λ ∈ Z[ω], Šθ (κ, λ) ∈ C θ (0) .
(5.9)

Let us consider γ ∈ Z[ω] such that θ = γ 2 ∈ Z[ω] + ρ and |θ| = γ • γ (see Lemma 5.
2). We then see that the terms of Formulae (5.8) and (5.9) are multiples of γ. Since division by γ removes the common multiple while ensuring results to stay in Z[ω], let us define

S γ : Z[ω] × Z[ω] → Z[ω] (κ, λ) → κ • γ -γ • λ.
Then, the bijectivity of U is ensured when

     ∀λ ∈ Z[ω], ∃κ ∈ Z[ω], S γ (κ, λ) ∈ C γ (0) ∀κ ∈ Z[ω], ∃λ ∈ Z[ω], S γ (κ, λ) ∈ C γ (0), (5.10)
provided that S γ (Z[ω], Z[ω]) ∩ C γ (0) = S γ (Z[ω], Z[ω]) ∩ C γ (0) ⇔ S γ (Z[ω], Z[ω]) ∩ ((C γ (0) ∪ C γ (0)) \ (C γ (0) ∩ C γ (0))) = ∅.

Characterization of Bijective Digitized Rotations

In this section we provide sufficient and necessary conditions for bijectivity of U . Our goal is to prove that the bijectivity of U is ensured if and only if θ is given by a primitive Eisenstein triple such that its generators s, t are of the form s > 0, t = s + 1

or s = 1, t > 1.
Before going into the main discussion of this section, we note that the vertexes of C γ (0) and that of C γ (0) lie on the same circle and their order does not depend on γ. It is due to the fact that |γ| = |γ| and arg(γ) = -arg(γ). Also, the vertexes of the hexagonal cells C γ (0) and C γ (0) are not in Z[ω]. Indeed, as it can be noted in Figure 5.2, the vertexes of C 1 (0) have modulus equal to

(0) = γ • C 1 (0) (resp. C γ (0) = γ • C 1 (0)) are not in Z[ω].
For the simplification of the following discussion we scale the cells C γ (0) and C γ (0) by 2 + ω so that the vertexes are in Z[ω] (see Figure 5.2).

Lemma 5.3. If

s = 1 or t = s + 1, then ∃φ ∈ S γ (Z[ω], Z[ω]) such that φ ∈ (C γ (0) ∪ C γ (0)) \ (C γ (0) ∩ C γ (0)).
Proof. Thanks to the symmetry, we focus on one of the vertexes of C γ•(2+ω) (0), γ. Then we consider the two closest elements of C γ•(2+ω) (0) ∩ Z[ω] to γ which are ζ = γ -1 and ζ = γ + ω. Note that we need to consider only this case since we have 0 < s < t. To verify if ζ and ζ lay on the left-hand side of , we then need to verify the following inequalities obtained from the respective line equations multiplied by -

We now show that if

t = s + 1 or s = 1 then ζ / ∈ C γ•(2+ω) (0) or ζ / ∈ C γ•(2+ω) (0).
√ 3 2
s 2 -st + t < 0, (5.11)

s 2 -st + s + t < 0, (5.12)
respectively. Then by substituting t with s + e, Inequalities (5.11 -5.12) are rewritten by e(s -1) > s, (5.13) e(s -1) > 2s, (5.14) respectively. We notice that Inequalities (5.13 -5.14) are violated when s = 1 or when s > 1 and e = 1.

We then show that either

ζ 2+ω or ζ 2+ω , is an element of S γ (Z[ω], Z[ω]). First, we have that ζ 2 + ω = - e + 1 3 + (1 -2e) 3 -s ω (5.15) and ζ 2 + ω = - e -1 3 + 2(1 -e) 3 -s ω, (5.16)
where e = t -s. We notice that Formula (5.15) (resp. Formula (5.16)) has integer values when e = 3n + 2 (resp. e = 3n + 1), n ∈ Z. We note that from Lemma 2.2, e ≡ 0 Finally, since gcd(γ, γ) = 1, there exist κ ∈ Z[ω] and λ ∈ Z[ω] such that either

ω- ω 3 1- ω 3 1-ω 3 ω-ω 3 ω-1 3 ω-1 3 ω - ω 1 -ω ω -1 0
S γ (κ, λ) = ζ 2+ω or S γ (κ, λ) = ζ 2+ω . Lemma 5.4. If s = 1, t > 1 or s > 0, t = s + 1 we have that S γ (Z[ω], Z[ω]) ∩ ((C γ (0) ∪ C γ (0)) \ (C γ (0) ∩ C γ (0))) = ∅.
Proof. Thanks to the symmetry of C γ•(2+ω) (0) and C γ•(2+ω) (0), we focus on a pair of consecutive vertexes of C γ•(2+ω) (0), for example, γ and -ω • γ, and those of

C γ•(2+ω) (0), (i) γ and -ω • γ if s > 0, t = s + 1; (ii) ω • γ and -ω • γ if s = 1, t > 0.
Then we consider the distances between the pair of parallel lines, which are defined by Since the parallel lines go through points of Z[ω] and are (i) parallel and (ii) orthogonal to the hexagonal grid edges, the space between the parallel lines does not contain points of

Z[ω] -except on the boundary. This implies that ∀ζ ∈ Z[ω], ζ ∈ C γ (0) ⇔ ζ ∈ C γ (0). (-ω) • γ ω • γ γ + ω γ -1 γ (a) ω • γ (-ω) • γ γ + ω γ -1 γ (b)
(-ω) • γ ω • γ -γ ω • γ (-ω) • γ γ γ (-ω) • γ ω • γ -γ ω • γ (-ω) • γ (a) (-ω) • γ ω • γ -γ ω • γ (-ω) • γ γ γ (-ω) • γ ω • γ -γ ω • γ(-ω) • γ (b)

Density of bijective digitized rotations

Even though rational rotations are dense in the hexagonal and the square grids (see Lemma 2.8), bijective digitized rotations are not dense, as illustrated in Figure 5.5, where some of the greatest bijective angles are presented on the unit circle. We also state the following proposition related to the asymptotic convergences of angles, which lead to bijective digitized rotations. Note that, the respective limits are multiples of π 2 and π 3 for the square and hexagonal lattices, respectively.

Proposition 5.6. The asymptotic speeds of angles, which lead to the bijective digitized rotations are 1 p for the square lattice, and

√ 3 t and √ 3
3t for the hexagonal lattice and the generators s = 1, t > 0 and t = s + 1, respectively.

Proof. We focus on arctan θ where θ is an angle which leads to a bijective digitized rotation. Le us then start with the hexagonal lattice cases.

We have that θ = arctan √ 3a 2b-a , and by substituting a, b for the generators of positive Eisenstein primitive triples (see Lemma 2.2) we obtain

θ = arctan √ 3(s 2 + 2st) 2(t 2 + 2st) -s 2 -2st . ( 5.17)
Then, by developing Equation 5.17 with s = 1, t > 0 we obtain arctan

√ 3(2t + 1) 2t 2 + 2t -1 ∼ arctan √ 3 t .
On the other hand, in the case of t = s + 1, θ → π 3 and tan θ → √ 3, and a substitution of s for t -1 in Equation 5.17 leads to a constant, indeed

√ 3 3t 2 -4t+1 3t 2 -1 ∼ √ 3.
Let us consider then θ = π 3 + ε, where ε stands for infinitesimally small value different than 0. We then have that

tan ε = tan θ - π 3 = tan θ - √ 3 1 + √ 3 tan θ , ( 5.18)
and by substitution of tan θ in Equation (5.18) we arrive at

√ 3(1 -2t) 1 -6t + 6t 2 ∼ - √ 3 3t
.

Finally, let us focus on the square grid case. We have arctan p 2 -q 2 2pq , and by setting Note that, in the hexagonal grid case, angles of the family generated by s = 1, t > 0, are asymptotically three times as frequent as the angles given by generators s > 0, t = s + 1.

q = p -1 we obtain arctan 2p -1 2p 2 -2p ∼ arctan 1 p .
From the frequencies point of view we can see that angles for which bijective rotation exist cover more frequently the unit circle than in the square grid case. Some examples of bijective and non-bijective digitized rotations on the hexagonal grid are presented in Figure 5.6.

Introduction

Digitized rigid motions defined on Z 3 are simple yet crucial operations in image processing applications involving 3D data, e.g. image segmentation [START_REF] Bazin | Digital Topology in Brain Image Segmentation and Registration[END_REF], image registration [START_REF] Zitova | Image Registration Methods: A Survey[END_REF] and motion tracking [START_REF] Yilmaz | Object Tracking: A Survey[END_REF], to name some. One way of designing rigid motions on Z 3 is to combine continuous rigid motions defined on R 3 with a digitization operator that maps the result back into Z 3 . However, digitized rigid motions, though close to their continuous sibling, often no longer satisfies the same properties. In particular, due to digitization, such transformations do not preserve distances, and bijectivity and point connectivity are generally lost.

In this context, first, we study at a local scale the geometric and topological defects of digital sets induced by digitized rigid motions. For such a local analysis, one wishes to generate all possible images of a finite digital set under digitized rigid motions. Such a problem amounts to computing an arrangement of hypersurfaces in a 6D parameter space. However, the state-of-the-art techniques such as cylindrical algebraic decomposition or critical point method [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] are respectively burdened by double exponential [START_REF] Collins | Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition[END_REF] and exponential [START_REF] Renegar | On the Computational Complexity and Geometry of the First-order Theory of the Reals. Part I: Introduction. Preliminaries. The Geometry of Semialgebraic Sets. The Decision Problem for the Existential Theory of the Reals[END_REF] complexity, with respect to the number of variables. Therefore, their direct application to the problem of decomposition of the six dimensional parameter space of 3D digitized rigid motions are practically inefficient. Indeed, high dimensionality and existence of cases such as asymptotic critical values [START_REF] Kurdyka | Semialgebraic Sard Theorem for Generalized Critical Values[END_REF]-e.g., a plane orthogonal to a coordinate axis is tangent to a hypersurface in a point at infinity-make computations of such an arrangement difficult.

Next, we focus on characterizing the 3D digitized rotations that are bijective. "Simple" 3D digitized rotations, in particular those around one of the coordinate axes, possess the same properties as 2D digitized rotations. Therefore, an obvious subset of 3D bijective digitized rotations consists of the 2D bijective digitized rotations embedded in Z 3 .

Nevertheless, the question of determining whether a non-simple 3D digitized rotation is bijective has remained open.

To our knowledge, a few efforts were devoted to understand 3D digitized rigid motions.

To name some: Toffoli and Quick proposed 3D digitized rotations represented by a sequence of shears [START_REF] Toffoli | Three-dimensional Rotations by Three Shears[END_REF], which were then studied by Chen and Kaufman [START_REF] Chen | 3D Volume Rotation Using Shear Transformations[END_REF]; Fredriksson [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF] considered digitized rotations, and the transition angles which correspond to a shift in the image of an integer point from one digitization cell to another. These special angles (called by some hinge angles) were further studied by Thibault et al. [START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF][START_REF] Thibault | 3D Discrete Rotations Using Hinge Angles[END_REF].

Within Part II our contributions amounts to.

1. In the context of computing all possible images of a finite digital set under digitized rigid motions, we first show that the 6D parameter space can be split into two 3D spaces by uncoupling the parameters. Then, we propose an algorithm to compute at least one sample point for each 3D connected component in an arrangement of second degree polynomials. The proposed algorithm is capable of handling degenerate cases such as asymptotic critical values. Our implementation together with sets of different images of 6-, 18-and 26-neighborhoods under 3D digitized rigid motions are provided. These contributions were published in [START_REF] Pluta | Quadric Arrangement in Classifying Rigid Motions of a 3D Digital Image[END_REF].

2. We then focus on answering, which 3D digitized rotations are bijective. In our attempt we consider an approach similar to that used in Chapter 5 of Part I, and by Roussillon and Coeurjolly [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF] to prove the conditions for bijectivity of 2D digitized rotations on the regular hexagonal (resp. integer) lattice using arithmetic properties of Eisenstein (resp. Gaussian) integers. In our work, we partially extend these results to 3D digitized rotations employing Lipschitz quaternions. However, due to the non-commutative nature of quaternions the former approach has not succeeded yet to fully characterize the bijective digitized rotations. Nevertheless, we propose an algorithm which answers whether a given digitized rotation-defined by a Lipschitz quaternion-is bijective. Our implementation together with a list of Lipschitz quaternions, which induce 3D non-trivial bijective digitized rotations is provided. We published this work in [START_REF] Pluta | Bijectivity Certification of 3D Digitized Rotations[END_REF]. This part of the manuscript is organized as follows. In Chapter 7 we provide basic notations, notions related to 3D digital geometry and 3D digitized rigid motions. Then, in Chapter 8 we discuss the issue of bijectivity of 3D digitized rotations and we provide a characterization algorithm, i.e. an algorithm such that given a Lipschitz quaternion, it provides an answer whether the respective digitized rotation is bijective. Finally, in Chapter 9 we discuss the classification problem of a finite digital set under digitized rigid motions.

Chapter 7

Basic Notions

The purpose of this chapter is to introduce notions and notations used within Part II of the manuscript.

Rotations in Three Dimensions

Rigid motions on R 3 are bijective isometric maps defined as

U : R 3 → R 3 x → Rx + t (7.1)
where t = (t 1 , t 2 , t 3 ) ∈ R 3 is a translation vector and R is a rotation matrix. Note that the matrix R representing a 3D rotation by an angle θ around a rotation axis ω, can be obtained from: Rodrigues' rotation formula [START_REF] Murray | A Mathematical Introduction to Robotic Manipulation[END_REF][START_REF] Vince | Quaternions for Computer Graphics[END_REF][START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics[END_REF], a quaternion [START_REF] Vince | Quaternions for Computer Graphics[END_REF][START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics[END_REF] or by applying the Cayley transform.

Spatial Rotations and Quaternions

Quaternions are four dimensional counterparts of complex numbers, i.e. these are the elements of the set H = {w + ai + bj + ck | w, a, b, c ∈ R} where the elements i, j, k have the following properties:

i 2 = -1, j 2 = -1, k 2 = -1, jk = -kj = i, ki = -ik = j, ij = -ji = k .
Similarly to the set of complex numbers, H possesses a division ring structure, albeit a non-commutative one. More precisely, for p, q, r ∈ H:

• the conjugate of q = w + ai + bj + ck is defined as q = w -ai -bj -ck;

• the product of two quaternions, defined as

q • p =(w 1 + a 1 i + b 1 j + c 1 k)(w 2 + a 2 i + b 2 j + c 2 k) =w 1 w 2 -a 1 a 2 -b 1 b 2 -c 1 c 2 + (w 1 a 2 + a 1 w 2 + b 1 c 2 -c 1 b 2 )i +(w 1 b 2 -a 1 c 2 + b 1 w 2 + c 1 a 2 )j + (w 1 c 2 + a 1 b 2 -b 1 a 2 + c 1 w 2 )k,
is not commutative, i.e. q • p = p • q, in general, although real numbers, i.e.

quaternions such that q = q do commute with all others;

• the modulus of q is defined as

|q| = √ q • q = √ q • q = √ w 2 + a 2 + b 2 + c 2 ;
• any nonzero quaternion q possesses a right and left inverse, given by q -1 = q |q| 2 , so that q • q -1 = q -1 • q = 1.

Any point in R 3 is represented by a pure imaginary quaternion: x = (x 1 , x 2 , x 3 ) [START_REF] Vince | Quaternions for Computer Graphics[END_REF][START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics[END_REF]. The quaternion q is uniquely determined up to multiplication by a nonzero real number, and if |q| = 1, up to a sign change: q • x • q -1 = (-q) • x • (-q) -1 ; hence the correspondence between unit quaternions and rotation matrices is two-to-one. Note that, for any unit quaternion q = w + ai + bj + ck, a rotation angle θ and an axis of rotation ω ω ω are given as θ = 2 arccos(a) = 2 arcsin( √ a 2 + b 2 + c 2 ), and ω ω ω = (a,b,c) √ a 2 +b 2 +c 2 , respectively. We refer readers unfamiliar with quaternions to [START_REF] Vince | Quaternions for Computer Graphics[END_REF][START_REF] Kanatani | Understanding Geometric Algebra: Hamilton, Grassmann, and Clifford for Computer Vision and Graphics[END_REF][START_REF] Conway | On Quaternions and Octonions[END_REF].

x 1 i + x 2 j + x 3 k. Then, any rotation U can be written as x → q • x • q -1

Spatial Rotations and Cayley Transform

Let A be the skew-symmetric matrix

A =      0 c -b -c 0 a b -a 0     
where a, b, c ∈ R and I be the 3 × 3 identity matrix. Then almost any rotation can be represented by a matrix R obtained from the Cayley transform [START_REF] Cayley | The Collected Mathematical Papers of Arthur Cayley[END_REF]:

R = (I -A)(I + A) -1 = 1 1 + a 2 + b 2 + c 2      1 + a 2 -b 2 -c 2 2(ab -c) 2(b + ac) 2(ab + c) 1 -a 2 + b 2 -c 2 2(bc -a) 2(ac -b) 2(a + bc) 1 -a 2 -b 2 + c 2      . (7.2)
Indeed, rotations by angle π around any axis can only be obtained by the Cayley transform as a limit: angles of rotation converge to π when a, b, c tend to infinity [START_REF] Singla | Multi-resolution Methods for Modeling and Control of Dynamical Systems[END_REF]. In practice, this constraint is negligible and does not affect generality of our study. Using this formula, a rigid motion can be parametrized by the six real parameters (a, b, c, t 1 , t 2 , t 3 ).

The rotation matrix obtained from Cayley transform corresponds to a rotation by a quaternion q = 1 + ai + bj + ck. Note that, the matrix obtain from Cayley transform (see Equation 7.2) has only rational terms.

Digitized Rigid Motions in Three Dimensions

In general, we have that U(Z 3 ) Z 3 . As a consequence, to define digitized rotations as maps from Z 3 to Z 3 , we usually consider Z 3 as a subset of R 3 , then we apply U, and finally we combine the real results with a digitization operator.

To define such a digitization operator let us first define a digitization cell centered at

x = (x 1 , x 2 , x 3 ) ∈ Z 3 C(x) = x 1 - 1 2 , x 1 + 1 2 × x 2 - 1 2 , x 2 + 1 2 × x 3 - 1 2 , x 3 + 1 2 . (7.3)
The digitization operator is then defined as a function

D : R 3 → Z 3 , such that ∀x ∈ R 3 , ∃!D(x) ∈ Z 3 and x ∈ C(D(x)).

Transformation Models

In order to explain the motivation for Chapter 9, here, we briefly discuss two transformation models used in applications of digitized rigid motions to image processing. In Each small, blue sphere corresponds to an integer point in a digitization cell. assigned to U (x). The Lagrangian model suffers from (i) undefined values when no point is mapped onto y in the transformed space Z 3 -when U is non-surjective, and (ii) conflicting values when more than one point is mapped onto the same C(y), i.e. when U is non-injective.

The second model, called Eulerian (presented in Figure 7.3(b)), consists of computing D • U -1 (y) for each point y of the transformed space Z 3 . Note that Eulerian model does solve the problem of non-surjectivity but not that of non-injectivity. Indeed, we can still have a point in the initial space Z 3 such that two points in the target space have it as their preimage.

Point Status After Digitized Rigid Motions

In this section we study the number of possible preimages of y ∈ Z 3 under a digitized rigid motion U . The discussion provided in this section was mainly developed by the author during his master studies. Let us start by stating the following definition of a point status. and θ = 14 25 (b). The gray spheres (resp. white circles) represent points of U(Z 3 ) while the green digitization cells correspond to 0-points. an infinite straight line, for example, with ω = (0, 0, 1) and θ = π 12 . Also, according to Figure 7.4 a distance between two 0-points can be 1. This stands in contrast to 0-points in 2D for which distance is at least √ 2 [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF].

1-point. Some digitized rigid motions are bijective and even preserve distances as their continuous siblings. For example, the translation by t = 2 5 , -2 5 , 0 , or rotation around ω = (0, 0, 1) by an angle equal to a multiple of π 2 can be considered. It may also happen for more complex motions as showed in Chapter 8.

2-point.

The existence of 2-points is a consequence of the following results. Lemma 7.2. Let p, q ∈ Z 3 such that |p -q| ≥ √ 3. Then for any rigid motion U we have y ∈ Z 3 such that U(p) ∈ C(y) and U(q) ∈ C(y).

Lemma 7.2 can be verified by applying the definition of the digitization cells (see Equation (7.3)).

In accordance with Lemma 7.2, there are only two types of distances between two integer points p and q leading to 2-points under a digitized rigid motion, namely |p -q| ∈ {1, √ 2}.

3-point.

To find an answer to the question if three points p, q, r ∈ Z Lemma 7.3. For p, q, r ∈ Z 3 whose product of all the Euclidean distances is more than

2 √ 2 we have that x ∈ Z 3 such that U(p), U(q), U(r) ∈ C(x).
Proof. Let us consider three points

x = (x 1 , x 2 , x 3 ), y = (y 1 , y 2 , y 3 ), z = (z 1 , z 2 , z 3 ) ∈ R 3
located in the digitization cell C(0). In order to find the mean distance between these points we use the following inequality relation between the geometric and the arithmetic

means 3 |x -y| 2 |x -z| 2 |y -z| 2 ≤ |x -y| 2 + |x -z| 2 + |y -z| 2 3
and we maximize the sum |x -y| 2 + |x -z| 2 + |y -z| 2 , under the constraints -1 2 ≤ x i , y i , z i ≤ 1 2 , for i = 1, 2, 3.

Without loss of generality we focus on a convex function

L(x 1 , y 1 , z 1 ) = (x 1 -y 1 ) 2 + (y 1 -z 1 ) 2 + (x 1 -z 1 ) 2 .
From the convexity of L, we see that L(x 1 , y 1 , z 1 ) = 0 is the unique minimum which is reached when

x 1 = y 1 = z 1 .
By the convexity and symmetry of L, its level set must be centered along the line

x 1 = y 1 = z 1
, which under the above constraints is equal to the diagonal of C(0).

Therefore, the value of L depends on the distance from the line x 1 = y 1 = z 1 . As the digitizetion cell is convex, the maximum of L have to be achieved on the boundary of the digitization cell.

Consequently, under the constraints L reaches the maximum when

x 1 = -1 2 , y 1 = -1 2 , z 1 = 1 2 or x 1 = -1 2 , y 1 = 1 2 , z 1 = -1 2 or x 1 = -1 2 , y 1 = 1 2 , z 1 = 1 2 or x 1 = 1 2 , y 1 = -1 2 , z 1 = -1 2 or x 1 = 1 2 , y 1 = -1 2 , z 1 = 1 2 or x 1 = 1 2 , y 1 = 1 2 , z 1 = -1 2 .
Then we note that the maximum of L is equal to 2, which concludes that the maximum of |x -y| 2 + |x -z| 2 + |y -z| 2 is equal to 6.

Finally, the geometric mean must be ≤ 2, and then the product of distances ≤ 2 √ 2. In other words, if a triple of points whose product of Euclidean distances is > 2 √ 2, then at least one of them must lie outside the digitization cell C(0).

The proof idea was given by André Nicolas [START_REF] André | Largest Triangle with Vertices in the Unit Cube[END_REF].

Lemma 7.4. For any triple of points x, y, z ∈ R 3 whose product of all the Euclidean distances is equal to 2 √ 2, there exists a digitization cell on whose boundary lie x, y, z.

Proof. From the proof for Lemma 7.3 we have that the sum |x -

y| 2 + |x -z| 2 + |y -z| 2
has its maxima on the boundary of a digitization cell.

The configuration presented in Figure 7.5(b) can not then lead to a 3-point since the product of its sides is equal to 2 √ 2.

Proposition 7.5. A triple of points p, q, r ∈ Z 3 that form a right triangle of sides

1, 1, √ 2
, can lead to a 3-point under a digitized rigid motion.

From Proposition 7.5 we have that the configuration presented by Proof. Let us consider the triangle pqr of sides p = (0, 1, 0); q = (0, 0, 0); r = (1, 0, 0).

According to Lemmas 7.2 and 7.4, the only point which we can add to pqr is s = (1, 1, 0).

Consequently, the polygon pqrs is a unit square. Then, we know that the maximal square inscribed on a unite cube has a side length equal to

3 4 √ 2 > 1 [57].
Only the configuration presented in Figure 7.6(d) may create a 4-point. We finally obtain the following theorem which gives the upper bound of possible point statuses.

Theorem 7.7. There is no s-point for which s > 4.

C(p) C(q) (a)
C(p) spanned exactly on a unit cube face, any new point must belong to the opposite face or must be collinear with two distinct points from the configuration. However, adding such a point creates a pair of points between which a Euclidean distance is not lower than √ 3. Ipso facto, we show that we cannot obtain any new point configuration generated from more than four points such that it can be placed in a digitization cell.

C(q) (b) C(p) C(q) (c)

Connected Digital Sets and Neighborhood

Digitized rigid motions are not isometric transformations and may lead to splitting or merging of digital connected components.

Definition 7.8. Let p, q ∈ Z 3 , p = q then we say that p and q are face-, edge-or vertex-adjacent when the digitization cells C(p) and C(q) have a common face, an edge or a vertex (see Figure 7.7).

Then using Definition 7.8 we define digital connected sets.

Definition 7.9. We call a digital set S ⊂ Z 3 face-connected (resp. edge-, or vertexconnected) if between any distinct points p, q ∈ S, there exists a sequence of points of S such that any two consecutive points from the sequence are face-adjacent (resp. edge-, or vertex-adjacent).

We also define a neighborhood of p ∈ Z 3 , which is an analogue definition to the one introduced for p ∈ Z 2 in Chapter 2.

Definition 7.10. The neighborhood of p ∈ Z 3 (of squared radius r ∈ R + ), denoted N r (p), is defined as

N r (p) = p + d ∈ Z 3 | d 2 ≤ r .
Chapter 8

Characterizing the Bijectivity of

3D Digitized Rotations

Digitized rigid rotations are neither surjective nor injective, in general. In this context, it is useful to understand which 3D digitized rotations are indeed bijective. "Simple" 3D digitized rotations, in particular those around one of the coordinate axes, possess the same properties as 2D digitized rotations. Therefore, an obvious subset of 3D bijective digitized rotations consists of the 2D bijective digitized rotations embedded in Z 3 . Nevertheless, the question of determining whether a non-simple 3D digitized rotation is bijective has remained open. Indeed, Éric Andres in his habilitation wrote:

"une question qui demeure à ce jour ouverte est la question de l'existance d'autres AQA (Applications Quasi Affines) non-triviales bijectives. Existe-t-il une AQA équivalente en dimension 3 ? Nous avons quelques raisons de penser qu'il n'en existe pas en dimension 3 mais peut-être en dimension 4." [21, pages 83-84]. This can be translated as: "an open question is whether there exist other types of bijective quasi-affine transformations. Do they exist in 3D? We have reasons to think that there are not such quasi-affine transformations in 3D but maybe in 4D." In this chapter, we show that such non-trivial digitized rigid motions-which belong to a subset of quasi-affine transformations-do exist.

Our, approach is similar to that used to prove the conditions for bijectivity of 2D digitized rotations based on arithmetic properties of Gaussian (resp. Eisenstein) integers (see Chapter 5). In the context of 3D digitized rotations, we partially extend the 2D results to 3D by employing Lipschitz quaternions, which play a similar role to Gaussian and Eisenstein integers. However, due to the non-commutative nature of quaternions the former approach has not succeeded yet to fully characterize the bijective digitized rotations. Nevertheless, we propose an algorithm which tells whether a given digitized rotation, defined by a Lipschitz quaternion, is bijective. As a consequence, we cover all the rational rotations i.e., those whose corresponding matrix representation contains only rational elements -they do correspond to rotations given by Lipschitz quaternions. From the point of view of the applications, excluding a rotation whose matrix has irrational elements is a minor issue, since computers are mainly carried out with rational numbers. Moreover, using rational numbers ensures the exactness of the proposed characterization algorithm. We conjecture, as in 2D (see Chapter 4 in Part I), that non-rational rotations are not bijective.

Bijectivity Characterization

Set of Remainders

Let us compare the grid Z 3 and the rotated grid U(Z 3 ). The digitized rotation U = D •U is bijective if and only if each digitization cell C(x) of x ∈ Z 3 contains one and only one rotated point of q • Z 3 • q -1 ; in other words, ∀y ∈ Z 3 , |M U (y)| = 1. Instead of studying the whole source and target spaces, we study-as in Chapter 5-the set of remainders defined by the map

S q : Z 3 × Z 3 → R 3 (x, y) → q • x • q -1 -y.
Then, the bijectivity of U can be expressed as

∀y ∈ Z 3 ∃!x ∈ Z 3 , S q (x, y) ∈ C(0),
which is equivalent to the "double" surjectivity relation, used by Roussillon and Coeurjolly [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF]:

   ∀y ∈ Z 3 ∃x ∈ Z 3 , S q (x, y) ∈ C(0) ∀x ∈ Z 3 ∃y ∈ Z 3 , S q (x, y) ∈ qC(0)q -1 (8.1)
provided that

S q (Z 3 , Z 3 ) ∩ C(0) = S q (Z 3 , Z 3 ) ∩ qC(0)q -1 .
In other words,

S q (Z 3 , Z 3 ) ∩ ((C(0) ∪ qC(0)q -1 ) \ (C(0) ∩ qC(0)q -1 )) = ∅.
Hereafter, we shall rely on Formula (8.1), and in the study of the bijectivity of digitized rotation U , we focus on the images of S q . More precisely, we study the group G q spanned by images of the map S q :

G q = Zq 1 0 0 q -1 ⊕ Zq 0 1 0 q -1 ⊕ Zq 0 0 1 q -1 ⊕ Z 1 0 0 ⊕ Z 0 1 0 ⊕ Z 0 0 1 . (a) (b) σ σ σ φ φ φ ψ ψ ψ (c)
Figure 8.1: A mock-up illustration of a part of G q that: is dense (a); has a dense subgroup -the set of points at each plane is dense while the planes are spaced by a rational distance (b); is a lattice (c). In the case of (a) and (b), only some random points are presented, for the sake of visibility. In (c), vectors σ σ σ, φ φ φ, ψ ψ ψ are marked in red, blue and green, respectively.

Henceforth, we will assume that G q is generated by rational vectors, and forms therefore a lattice (see Figure 8.1(c)). In other words, corresponding rotations are considered as rational. The question now remains of comparing the (finitely many) points in

S q (Z 3 , Z 3 ) ∩ C(0) and S q (Z 3 , Z 3 ) ∩ qC(0)q -1 .

Lipschitz Quaternions and Bijectivity

For representing 2D rational rotations, in Part I, we used Gaussian and Eisenstein integers. In R 3 , rational rotations are characterized as follows [START_REF] Cremona | Letter to the Editor[END_REF].

Proposition 8.5. There is a two-to-one correspondence between the set of primitive

Lipschitz quaternions

L = {a + bi + cj + dk | a, b, c, d ∈ Z, gcd(a, b, c, d) = 1}
and the set of 3D rational rotations.

Working in the framework of rational rotations allows us to turn to integers, i.e. |q| 2 G q is an integer lattice. As integer lattices are easier to work with from the computational point of view, we do scale G q by |q| 2 in order to develop a characterization algorithm.

Similarly to the former discussion after scaling G q by |q| 2 , we consider the finite set of remainders, obtained by comparing the lattice qZ 3 q with the lattice |q| 2 Z 3 , and applying the scaled version of the map S q defined as Šq :

Z 3 × Z 3 → Z 3 (x, y) → q • x • q -q • q • y. (8.2)
Indeed, Formula (8.1) is rewritten by

   ∀y ∈ Z 3 ∃x ∈ Z 3 , Šq (x, y) ∈ |q| 2 C(0) ∀x ∈ Z 3 ∃y ∈ Z 3 , Šq (x, y) ∈ qC(0)q. (8.3)
Note that the right-hand sides of Formulae (8.2) and (8.3) are left multiples of q. As a consequence, we are allowed to divide them by q on the left side, while keeping integervalued functions. Let us define

S q : Z 3 × Z 3 → Z 4 (x, y) → x • q -q • y.
Then, bijectivity of U is ensured when

   ∀y ∈ Z 3 ∃x ∈ Z 3 , S q (x, y) ∈ qC(0) ∀x ∈ Z 3 ∃y ∈ Z 3 , S q (x, y) ∈ C(0)q, (8.4)
provided that

S q (Z 3 , Z 3 ) ∩ qC(0) = S q (Z 3 , Z 3 ) ∩ C(0)q.

An Algorithm for Bijectivity Characterization

In this section we present an algorithm which indicates whether a digitized rational rotation given by a Lipschitz quaternion is bijective. The strategy consists of checking if there exists w ∈ ((qC(0) ∪ C(0)q) \ (qC(0) ∩ C(0)q)) such that w = S q (x, y). If this is the case, then the rotation given by q is not bijective, and conversely.

Because q is a Lipschitz quaternion, the values of S q span a sublattice Ǧq ⊂ Z 4 . Therefore, given a Lipschitz quaternion q = a + bi + cj + dk, solving S q (x, y) = w with

x, y ∈ Z 3 for w ∈ Ǧq leads to solving the following linear Diophantine system Az = w (8.5) where z t = (x, y) ∈ Z 6 and

A =           b c d -b -c -d a -d c -a -d c d a -b d -a -b -c b a -c b -a          
.

To find points of Ǧq that violate Formula (8.4), we consider points w ∈ Z 4 ∩ qC(0) (resp. w ∈ Z 4 ∩ C(0)q) such that w / ∈ C(0)q (resp. w / ∈ qC(0)). Then, we verify if w belongs to Ǧq . The membership verification can be done in two steps.

Step 1: we check if q • w ∈ Z 3 , i.e. we check if w lies in the starting hyperplane. This is always the case when the following equation holds

aw 1 -bw 2 -cw 3 -dw 4 = 0,
where q = a + bi + cj + dk and w = (w 1 , w 2 , w 3 , w 4 ), which is identified with a Lipschitz quaternion w = w 1 + w 2 i + w 3 j + w 4 k. This is equivalent to checking if the real part of q • w is equal to zero.

Step 2: we check if Equation (8.5) has integer solutions. This can be done by reducing the matrix A to its Smith normal form.

Proposition 8.6. The system Az = w has integer solutions if and only if the system Sz = w has integer solutions, where S = UAV is the Smith normal form of A, z = V -1 z and w = Uw. Then, the system has integer solutions if and only if the elements of w are integer multiples of the diagonal (or pseudo-diagonal for non-square matrices) elements of S.

Proof. First we note that the systems Sz = w = UAVV -1 z = Uw which is equivalent to UAz = Uw Then, we note that the matrices U and V correspond to unimodular rows and columns operations, respectively. The key observation is that, since V corresponds to unimodular columns operations, therefore, the system has integer solutions if and only

if ∀i ∈ [1, n], (Uw) i S i,i ∈ Z,
where n is the row number of A.

Using the result of Proposition 8.6 we can verify if Equation (8.5) has integer solutions by checking if

w i = k i S i,i
where k i ∈ Z, i ∈ [START_REF] Fredriksson | Rotation Invariant Template Matching[END_REF][START_REF] Ostromoukhov | Rotated Dispersed Dither: A New Technique for Digital Hhalftoning[END_REF], namely elements of w are integer multiples of the diagonal elements of S. Note that Schrijver provided similar-but computationally less efficient-conditions for full-rank matrices [58, page 51].

Notice that, before iterating over points w ∈ Z 4 ∩ qC(0) (or w ∈ Z 4 ∩ C(0)q), we can first reduce a priori the matrix A to its Smith normal form S and then multiply w by the unimodular matrix U.

All the steps are summarized in Algorithm 3. Figure 8.2 presents sets of points q • w ∈ qC(0)q ∪ |q|2 C(0) for some Lipschitz quaternions, which induce bijective digitized rational rotations, while Figure 8.3 presents non-bijective cases. Finally, Table 8 Result: True if the digitized rotation given by q is bijective and false otherwise.

U, S, V ← SmithDecomposition(A) foreach w = (w 1 , w 2 , w 3 , w 4 ) ∈ Z 4 ∩ qC(0) do if aw 1 -bw 2 -cw 3 -dw 4 = 0 and ∀i ∈ [1, 4], (Uw) i
S i,i ∈ Z then if w / ∈ C(0)q then return false return true
The time complexity of Algorithm 3 is given as follows.

Step 1: reduction of the matrix A to the Smith normal form can be done while applying twice an algorithm for computing Hermite normal form. This can be done in a polynomial time [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF].

For instance, one can apply the algorithm proposed by Micciancio and Warinschi [START_REF] Micciancio | A Linear Space Algorithm for Computing the Hermite Normal Form[END_REF] or its more recent, optimized version proposed and implemented in SageMath 2 by Pernet and Stein [START_REF] Pernet | Fast Computation of Hermite Normal Forms of Random Integer Matrices[END_REF], whose running time complexity for full row rank matrices-with some slight modifications it can handle non-full row rank matrices-is O(mn

4 log 2 N (A)),
where n is the number of rows, m the number of columns and N (A) stands for a bound on the entries of the matrix A [START_REF] Micciancio | A Linear Space Algorithm for Computing the Hermite Normal Form[END_REF]. Here n = 4 and m = 6. Thus, the time complexity

of Step 1 is O(log 2 N (A)).
Step 2: the number of points in Z 4 ∩ qC(0) (resp. Z 4 ∩ C(0)q) is bounded by |q| 3 . For each point w, the time needed to check if ∀i ∈ [1, 4], (Uw) i S i,i ∈ Z is constant. Therefore, the time complexity of Step 2 is O(|q| 3 ). Note that determining for each w if w / ∈ C(0)q (resp. w / ∈ qC(0)) can be done in a constant time while checking a set of inequalities.

-5 Finally, we can conclude that the time complexity of the algorithm is O(|q| 3 +log 2 N (A)).

+ 3i + 5j + 5k θ ≈ 246.1 • , ω = 3 √ 59 , 5 √ 59 , 5 √ 59 5 -4i + -5j + 5k θ ≈ 116.8 • , ω = -2
-10 + 9i -9j -10k θ ≈ 243.4 • , ω = 9 √ 262 , -9 √ 262 , -5 2 131 2 + 2i + j + 2k θ ≈ 112.6 • , ω = 2 3 , 1 3 , 2 3 -2 -2i -j + k θ ≈ 258.5 • , ω = -2 3 , -1 √ 6 , 1 √ 6

Future work and conclusion

In this chapter, we showed the existence of non-simple 3D bijective digitized rotationsones for which a given rotation axis does not correspond to any of the coordinate axes.

Our approach is similar to that used to prove the conditions for bijectivity of 2D digitized rotations based on arithmetic properties of Gaussian (resp. Eisenstein) integers (see Chapter 5). In our work, we used arithmetic properties of Lipschitz quaternions, which play a similar role to Gaussian (resp. Eisenstein) integers. Due to the non-commutative nature of quaternions, the approach has not succeeded yet to fully characterize the set of 3D bijective digitized rotations. Nevertheless, we proposed an algorithm that answers whether a digitized rotation given by a Lipschitz quaternion q is bijective.

As a part of our future work, we would like to prove Conjecture 8. of 3D rigid motions, and can be formulated as an arrangement of hypersurfaces given by polynomials of degree two with integer coefficients. Our goal is to compute for each full-dimensional open cell at least one representative point, called a sample point. The state-of-the-art techniques such as cylindrical algebraic decomposition or critical point method [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] are respectively burdened by double exponential [START_REF] Collins | Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition[END_REF] and exponential [START_REF] Renegar | On the Computational Complexity and Geometry of the First-order Theory of the Reals. Part I: Introduction. Preliminaries. The Geometry of Semialgebraic Sets. The Decision Problem for the Existential Theory of the Reals[END_REF] complexity with respect to the number of variables. Therefore, their direct application to the problem of decomposition of the six dimensional parameter space of 3D digitized rigid motions are practically inefficient. Indeed, high dimensionality and existence of degenerate cases such as asymptotic critical values [START_REF] Kurdyka | Semialgebraic Sard Theorem for Generalized Critical Values[END_REF]-e.g., a plane orthogonal to a coordinate axis is tangent to a hypersurface in a point at infinity-make a computation of such an arrangement difficult.

In this chapter, we discuss an ad hoc method introduced by us in [START_REF] Pluta | Quadric Arrangement in Classifying Rigid Motions of a 3D Digital Image[END_REF]. The method is as follows. We first show that the problem can be simplified by uncoupling the six parameters of 3D rigid motions to obtain two systems in three variables. These two systems correspond to the rotational and translational parameters of rigid motions.

Then we study an arrangement of second degree polynomials-called hereafter quadrics.

In order to detect all the topological changes along a non-generic direction in such an arrangement of quadrics we use a sweeping a plane. We then compute all critical points, including asymptotic critical values, of the arrangement. Moreover, we compute at least one sample point for each open full dimensional cell in the arrangement -sample points of full dimensional components provide information used to generate different images of a digital set under digitized rigid motions. Our strategy is similar to the one proposed by Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF] where the main differences are: we do not use generic directions; we handle asymptotic cases and give new criteria to compute critical values in polynomials of degree two; we compute and store at least one sample point for each full dimensional open cell where Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF] compute full adjacency information for all cells in an arrangement; moreover, we precompute all critical values a priori where in the former approach only one type of critical values needs to be computed before the main algorithm. Those sample points are then used to decompose the other three dimensional parameter space.

Motivation: Connectivity Alterations

In this section we provide the motivations and the origins of the study provided in the chapter. [START_REF] Bazin | Digital Topology in Brain Image Segmentation and Registration[END_REF][START_REF] Bazin | Digital Homeomorphisms in Deformable Registration[END_REF].

In the case of the 2D digitized rigid motions it can be shown that if S is regular (see [START_REF] Ngo | Topology-preserving Conditions for 2D Digital Images under Rigid Transformations[END_REF]Definition 12]), then S satisfies Bazin's conditions but not vice versa. Also, we found that a straightforward extension of the Ngo's regularity definition to 3D digital face-connected sets is not sufficient to ensure that the connectivity property is always preserved under 3D digitized rigid motions. around one of the main axes e.g., σ : (x, y, z) → (-y, x, z). Then, applying σ to q we obtain q = 1 -bi + aj + ck and σ -1 maps q onto q. We observe that, if a, b, c are negative then we can always find a series of σ rotations which map a, b, c to nonnegative values and back.

Studying the non-continuous evolution of a neighborhood N r (p) is equivalent to study the discontinuities of U (d) for every d ∈ N r (p) \ {p}. This occurs when U(d) is on the half-grid plane, namely a boundary of a digitization cell. This is formulated by

R i d + t i = k i - 1 2 (9.1)
where R i is the i-th row of the rotation matrix for i ∈ {1, 2, 3},

k i ∈ H(N r (p)) = Z ∩ [-r , r ],
and r is the greatest radius of U(N r (p)) for all U, so that r = r + √ 3.

Arrangement of Quadrics

The Problem as Arrangement of Hypersurfaces

For any neighborhood N r (p), the parameter space Our goal is to compute for each 6D open cell in Ω at least one representative point, a sample point. The direct application of the cylindrical algebraic decomposition or critical points method to this problem is practically inefficient -due to the high dimensionality and existence of degenerate cases that make computation of the arrangement difficult.

Ω = (a, b, c, t 1 , t 2 , t 3 ) ∈ R 6 | 0 ≤ a, b, c, - 1 2 < t i < 1 2 for i = 1, 2,
For these reasons, in the following discussion we develop an indirect but still exact strategy.

Uncoupling the Parameters

The first idea of our strategy consists of uncoupling the parameters of the six dimensional parameter space Ω. Namely, we show that by considering the differences between the hypersurfaces given in Equation ( 9 Let us consider a rigid motion defined by R and t. The condition for having

U (d) = k = (k 1 , k 2 , k 3 ) ∈ Z 3 where d ∈ N r (p) is k i - 1 2 < R i d + t i < k i + 1 2 for i = 1, 2, 3. Equivalently, k i - 1 2 -R i d < t i < k i + 1 2 -R i d. (9.2)
Let us call as a configuration a list of couples (d, k), which describe how the neighborhood N r (p) is transformed. This configuration can be described as a function

F : N r (p) → H(N r (p)) 3 d = (d 1 , d 2 , d 3 ) → k = (k 1 , k 2 , k 3 ).
We want to ascertain whether a given configuration F arises from some digitized rigid motion U , which corresponds to some parameters a, b, c, t

F (d) i - 1 2 -R i d < min d∈Nr(p) F (d) i + 1 2 -R i d (9.3)
which gives a range on t such that all configuration (d, k) are valid under some Uassuming once again that (a, b, c) are known. Equivalently we consider the following list of inequalities

∀d, d ∈ N r (p), F (d ) i - 1 2 -R i d < F (d) i + 1 2 -R i d, (9.4)
where d and d correspond to the ones which maximize and minimize the left and right sides of Inequality (9.3), respectively. The key observation is that we have eliminated the variables t 1 , t 2 , t 3 and have reduced to a subsystem of inequalities in a, b, c. Moreover, due to the rational expression in the Cayley transform (7.2), we may use the following integer-valued polynomials of degree 2:

q i [d, k i ](a, b, c) = (1 + a 2 + b 2 + c 2 )(2k i -1 -2R i d), (9.5)
for i = 1, 2, 3, namely Inequality (9.4) can be rewritten as the quadratic polynomial inequalities

q 1 [d, k 1 ](a, b, c) = -2(1+a 2 -b 2 -c 2 )v 1 -4(ab-c)v 2 -4(b+ac)v 3 +(1+a 2 +b 2 +c 2 )(2k 1 -1), q 2 [d, k 2 ](a, b, c) = -4(ab+c)v 1 -2(1-a 2 +b 2 -c 2 )v 2 -4(bc-a)v 3 +(1+a 2 +b 2 +c 2 )(2k 2 -1), q 3 [d, k 3 ](a, b, c) = -4(ac-b)v 1 -4(a+bc)v 2 -2(1-a 2 -b 2 +c 2 )v 3 +(1+a 2 +b 2 +c 2 )(2k 3 -1).
∀d, d ∈ N r (p), Q i [d, d , F (d) i , F (d ) i ](a, b, c) > 0,
where

Q i [d, d , k i , k i ](a, b, c) = q i [d, k i ](a, b, c) + 2(1 + a 2 + b 2 + c 2 ) -q i [d , k i ](a, b, c), ( 9.6)
for i = 1, 2, 3. The set of quadratic polynomials for our problem is then given by

Q = {Q i [d, d , k i , k i ](a, b, c) | i = 1, 2, 3, d, d ∈ N r (p), k i , k i ∈ H(N r (p))}. Figure 9.3
illustrates the zero sets of some quadratic polynomials in Q.

Computing Arrangement of Quadrics in 3D

In this section we discuss how to compute the arrangement of quadrics Q(a, b, c) = 0 for Q ∈ Q given by Equation (9.6). Our strategy is similar to one proposed by Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF]. The main differences are that we store only sample points of full dimensional connected components and we precompute and sort all event points-points which induce changes of topology in an arrangement of quadrics-a priori. Moreover, we consider cases such as asymptotic critical values. In short, our method is as follows:

Step 1: detect and sort all the events in which the topology of an arrangement changes;

Step 2: sweep by a plane the set of quadrics along a chosen direction. The sweeping plane stops between two event points and we intersect the quadrics related to them with the sweeping plane. This reduces to the problem of 2D arrangement of conics in each of such points. After this procedure, for each sample point we recover the translation part of the parameter space of digitized rigid motions. The description of this last part will be given in the next section. Note that the proposed approach could be also applied to solve a similar problem in 2D, i.e. generation of the different images of a 2D neighborhood under 2D digitized rigid motions -a solution to this problem was already proposed by Ngo et al. [START_REF] Ngo | Combinatorial Structure of Rigid Transformations in 2D Digital Images[END_REF].

Bifurcation and Critical Values

In [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF], the authors show how to describe an arrangement of quadric by sweeping a plane along a generic direction. Using the theory of generalized critical values [START_REF] Kurdyka | Semialgebraic Sard Theorem for Generalized Critical Values[END_REF][START_REF] Rabier | Ehresmann Fibrations and Palais-Smale Conditions for Morphisms of Finsler Manifolds[END_REF][START_REF] Jelonek | Quantitative Generalized Bertini-Sard Theorem for Smooth Affine Varieties[END_REF] we show how to compute a point per open connected component of an arrangement of quadrics using a projection along a non-generic direction. Hereafter, we consider the direction of the a-axis. Then by critical values we denote values a at which the topology of the arrangement changes.

We consider an arrangement of smooth quadrics defined by zero sets of the all respective polynomial for Q. Note that, if quadrics have isolated singularities then the bifurcation set (see Definition 9.1) is still well defined and includes projections of these singularities.

In the following, for p, q, r ∈ Z, we denote by: S p the surface given by Q p (a, b, c) = 0; C p,q the curve defined by Q p = Q q = 0 and P p,q,r the points obtained as

Q p = Q q = Q r = 0.
We assume that each S p is a smooth surface of dimension two, each C p,q is a smooth curve of dimension one. Also, we denote by A the set of maximally connected components of

R 3 \ p S p .
Let C be an open cell of A. We can associate to C the extremal values C inf = inf({a | (a, b, c) ∈ C}) and C sup = sup({a | (a, b, c) ∈ C}). We will show in this section that these values are included in a bifurcation set. Furthermore, we consider that a projection map on the first coordinate a is denoted by ρ, and its restriction to a submanifold M ⊂ R 3 is denoted by ρ |M . Moreover, for a 0 ∈ R we denote by M a 0 the set ρ -1 |M (a 0 ). Similarly, for an open interval (a 0 , a 1 ) ⊂ R we denote by M (a 0 ,a 1 ) the set ρ -1 |M ((a 0 , a 1 )).

We are interested in computing the set of values a above which the topology of the cells of A changes. We show in Lemma 9.2 that this set is included in the finite bifurcation set [START_REF] Jelonek | On Asymptotic Critical Values of a Complex Polynomial[END_REF] of the projections on the first axis restricted to different manifolds. fibrations. In (a), the topology of the arrangement above the interval (a 0 , a 1 ) is constant, while in (b) it is not, i.e. in (b) there is an element a * of the bifurcation set B in the interval (a 0 , a 1 ). Note that in (a) a 0 , a 1 ∈ B while in (b) a 0 , a 1 / ∈ B.

More specifically, for all a 0 ∈ R \ B(ρ |M ), there exists > 0 and a homeomorphism

ψ : (a 0 -, a 0 + ) × M a 0 → M (a 0 -,a 0 + ) ,
such that ρ • ψ(x, p) = x for all (x, p) ∈ (a 0 -, a 0 + ) × M a 0 . Figure 9.4 illustrates a 2D trivial and a 2D nontrivial fibrations.

In the following, we will consider the finite set B ⊂ R defined as the union of the bifurcation sets of ρ |Sp and ρ |Cp,q and the projections of P p,q,r [START_REF] Jelonek | On Asymptotic Critical Values of a Complex Polynomial[END_REF]. More precisely, we define: Proof. Let p ∈ J C and let p be a point on S p ∩ ∂C v that does not belong to any surface S q for q = p. Let α ≤ C inf be the maximal element of B p lower than v. Then ρ |Sp and the ρ |Cp,q are trivial fibrations above (α, β) and ρ(P p,q,r ) ∩ (α, β) = ∅ for q = p and r = p different integers. In particular, the points of the curves C p,q never cross above (α, β).

B p = B(ρ |Sp ) ∪ q =p B(ρ |Cp,q ) ∪ q =p,

More formally, there exists a continuous function

φ : (α, β) → S p such that φ(v) = p, ρ • φ(x) = x and Q q (φ(x)) = 0 for all q = p.
Let T be an open ball of radius centered at φ(v) and defined as T = {y = (a, b, c) ∈ and(a, b, c) -φ(v) < }. We now prove by contradiction that α = C inf . If α < C inf , then there exists a sufficiently small > 0 such that the respective intersections of T with Q p < 0 and Q p > 0 are connected and such that T does not intersect any S q for q = p. Since p ∈ T , the intersection of T with C is not empty. Moreover, C is a maximally connected component in the complement of the union of S j , such that one of the two connected components of T \ S p is included in C. Thus, the ball T intersects C a for all a ∈ [C inf , v]. In particular, C C inf is not empty, which is a contradiction with the definition of C inf . In particular, C inf = α, which allows us to conclude that α = C inf and C inf ∈ B p .

R 3 | v ∈ [C inf , v]
C ∈ A J C inf such that C a ⊂ C a .
Proof. According to Lemma 9.2, C inf is contained in all B p such that S p intersects the border of C a with dimension one. In particular, one of the cells of

A J C inf ∩ ρ -1 (a) is included in C a .
From a constructive point of view, the authors of [START_REF] Jelonek | Quantitative Generalized Bertini-Sard Theorem for Smooth Affine Varieties[END_REF] showed that the bifurcation set is included in the union of the critical and asymptotic critical values. More specifically, given a polynomial map f : M → R, we have B(f

) ⊂ K(f ) ∪ K ∞ (f ), where K(f ) are
the critical values of f and K ∞ are its asymptotic critical values. In [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF], the authors called the points of K(ρ |Sp ) events of type A, the points of K(ρ |Cp,q ) events of type B and the points ρ(P p,q,r ) events of type C. We extend their classification for degenerate projections, and say that the points of K ∞ (ρ |Sp ) are events of type A ∞ and the points of K ∞ (ρ |Cp,q ) are events of type B ∞ .

From a computational point of view, we recall in the next section how to compute the critical values of types A, B and C. For the types A ∞ and B ∞ , we use the results from [START_REF] Jelonek | Quantitative Generalized Bertini-Sard Theorem for Smooth Affine Varieties[END_REF] and simplify them for the case of quadrics.

Finally, as described in Section 9.4.4, our strategy will be to compute the generalized critical values a and for each value, to store also J a the set of indexes i such that either:

• a ∈ K(ρ |Sp ) ∪ K ∞ (ρ |Sp ) • a ∈ K(ρ |Cp,q ) ∪ K ∞ (ρ |Cp,q ) for q = p
• a ∈ ρ(P p,q,r ) for q = p, r = p and q = r This allows us to reduce the number of quadrics to consider in the intermediate steps of our sweeping plane algorithm. Type B. This type corresponds to the case s ∈ K(ρ |Cp,q ). Such an event corresponds to an a-critical value for which there are solutions to the system

Detection of Critical Values

Q p (s, b, c) = Q q (s, b, c) = (∇Q p ×∇Q q ) 1 (s, b, c) = 0. In other words, a curve defined by Q p (s, b, c) = Q q (s, b, c) = 0,
is tangent to a plane orthogonal to the a-axis.

Type C. There are values s ∈ ρ(P p,q,r ) above which the topology of the open connected components in A changes. An a-critical value is such that there are solutions to the

system Q p (s, b, c) = Q q (s, b, c) = Q r (s, b, c) = 0.
In other words, the quadrics intersect in a point. Note that it can happen that an intersection between three quadrics is a curve. This issue can be solved if a curve projects on a point, thanks to the elimination theory and use of resultants or Gröbner basis. Indeed, we can compute a univariate polynomial which vanishes on the projection of the curve [START_REF] Cox | Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF].

For more information about events of the types A, B and C we refer readers to [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF]. the matrix

  ∂ 2 Q ∂b 2 ∂ 2 Q ∂b ∂c ∂Q ∂b (a, 0, 0) ∂ 2 Q ∂c ∂b ∂ 2 Q ∂c 2 ∂Q ∂c (a, 0, 0)   that depends only on a, K ∞ (ρ |S ) ⊂ {a | M (a) has rank at most 1}.
Proof. Consider the mapping f :

R 3 → R 2 such that (a, b, c) → (a, Q(a, b, c)). The definition of K ∞ implies K ∞ (ρ |S ) = K ∞ (f ) ∩ R × {0}. Let q(a, b, c) = max(| ∂Q ∂b |,| ∂Q ∂c |) max(| ∂Q ∂a |,| ∂Q ∂b |,| ∂Q ∂c |)
.

Then

∂ 2 Q ∂c 2 ∂Q ∂b -∂ 2 Q ∂b ∂c
∂Q ∂c is a linear function that depends only on b. Then this function converges toward 0 if and only if the coefficient in front of b in the function and its constant coefficient are 0. In particular, from the minorrank relation and the symmetry of the second order partial derivatives we have that if

∂ 2 Q ∂c 2 or ∂ 2 Q
∂b ∂c is non-zero, the matrix M (a) has rank 1. If both are 0, then with similar arguments, we can see that M (a) is the null matrix. Thus, K ∞ is a subset of a such that M (a) has a rank less than or equal to 1.

The algorithm to detect this type of events is as follows. Step 2: let v stands for the cross product of v b = (u, v, wa + t) and v c = (u , v , w a + t ).

Note that the vectors v b and v c represent the rows of M (a). Finally, we solve for a such that all the elements of v are equal to 0, i.e. all the second minors of M (a) are equal to 0, in other words when the rank of M (a) is lower than 2.

Type B ∞ . In this case we are considering the asymptotic critical points of the projection restricted to a curve defined by the intersection of two quadrics Q p , Q q ∈ Q, p, q ∈ Z and p = q. Using [69, Proposition 4.2], these correspond to the a-coordinate of the sweeping planes that cross the projective closure of the curve at infinity. More formally, we In particular, this set is also the set of values a such that either the projection of C p,q on the (a, b)-plane or the projection of C p,q on the (a, c)-plane has an asymptote in a.

According to [START_REF] Jelonek | Quantitative Generalized Bertini-Sard Theorem for Smooth Affine Varieties[END_REF]Proposition 4.2], these are the elements of a non-properness set of a projection map. More formally, we say that p belongs to a non-properness set of a projection map π if for each neighborhood Y of p we have that π -1 (Y ) is not bounded. The properties of this set and the algorithms to compute it have been studied notably in [START_REF] Jelonek | Topological Characterization of Finite Mappings[END_REF][START_REF] El Din | Properness Defects of Projections and Computation of at Least One Point in Each Connected Component of a Real Algebraic Set[END_REF][START_REF] Moroz | Properness Defects of Projection and Minimal Discriminant Variety[END_REF]. In our case the non-properness set of the projection restricted to C p,q is the set of a-coordinates of the sweeping planes that cross at infinity the projective closure of C p,q , i.e., the smallest projective algebraic variety containing C p,q .

To detect such a case we apply the following steps. We have an asymptote in the (a, c)-plane for 2a -1 = 0, i.e. when a = 1 2 -which is marked by a pink vertical line.

Indeed, there is an asymptote for a = 1 2 . Figure 9.8 illustrates an event of B ∞ type and Figure 9.9 the corresponding projections.

Recovering Translation Parameter Values

The algorithm proposed in the previous section gives us the set R of rational sample points (a, b, c) ∈ Q 3 , which correspond to the rotation parameters. In this section we discuss how to obtain sample points (t 1 , t 2 , t 3 ) of the translation part for each (a, b, c) ∈ R and how to generate different images of N r (p) under rigid motions.

Let us first note that Equation (9.1) under the assumption of t ∈ - For the sake of visibility three types of orthogonal critical planes are presented separately.

Case Study

In this section we would like to address some practical issues of the proposed algorithm while considering a particular neighborhood, i.e. we consider N 1 (p).

Combinatorial Issue

The number of quadrics obtained directly from Equation (9.6) for N 1 (p) is 1260. In this section we show that this number is reduced to 81 by discarding those which are always strictly positive (resp. negative) and ones which are redundant. Note that similar studies remain valid for different neighborhoods. Indeed, for N 2 (p) and N 3 (p) we have 513 and 741 quadrics, respectively2 .

Let us consider N 1 (p) and vectors u 1 = (1, 0, 0) (resp. u 2 = (0, 1, 0), u 3 = (0, 0, 1)), and h = 1 2 , 1 2 , 1 2 . Then we rewrite (9.4) as 1. when v = 0, then there is no q ∈ Z ∩ [-1, 3] satisfying (9.8), 2. when v = 1, then there are 6 different pairs of (d, d ) and we obtain q ∈ {0}, 3. when v = 2, then there are 6 different pairs of (d, d ) and we obtain q ∈ {-1, 0, 1}, 4. when v = √ 2, then there are 12 different pairs of (d, d ) and we obtain q ∈ {-1, 0, 1}.

u i • (k -h -Rd ) < u i • (k + h -Rd) (9.
Therefore, the number of valid quadrics Q[d, d , k i , k i ] for each case is 0 (case 1), 6 (case 2), 18 (case 3) and 36 (case 4). Note that case 2 is included in case 3 up to a constant, as that we can ignore the 6 quadrics. This finally gives us 18+36 2 = 27 quadrics per direction and thus 81 in total.

Implementation and Experiments

We have implemented the proposed algorithm in Maple 2015 (or later) and our code can be downloaded from https://github.com/copyme/RigidMotionsMapleTools. In In such an arrangement, each sample point (t 1 , t 2 , t 3 ) of a full dimensional cell bounded by planes gives the translation part of rigid motions. Using this information, we generate an image of N r (p) by applying to it a digitized rigid motion given by the value of (a, b, c, t 1 , t 2 , t 3 ). Note that we observe that for different sample points (a, b, c) that belong to the same full dimensional component, planes illustrated in Figure 9.12 change their positions but not their order.

Future Work and Conclusion

In this chapter, we proposed a method to decompose the 6D parameter space of 3D rigid motions for a given 3D finite digital set. We first uncoupled the six parameters of 3D rigid motions to end up with two systems in three variables, and started by studying an arrangement of quadrics in R 3 .

Our approach to compute an arrangement of quadrics in 3D is similar to the one proposed by Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF] where the main differences are: we do not use generic directions; we handle asymptotic cases and give new criteria to compute critical values in polynomials of degree two; we compute and store at least one sample point for each full dimensional open cell where Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF] compute full adjacency information for all cells in an arrangement. Moreover, we precompute all critical values a priori where in the former approach only one type of critical values needs to be computed before the main algorithm. Those sample points are then used to decompose the other three-dimensional parameter space. We also provided our implementation.

There are four main issues-listed below-on which we have been working since the publication of [START_REF] Pluta | Quadric Arrangement in Classifying Rigid Motions of a 3D Digital Image[END_REF]. at the starting polynomial. Our observation is that the polynomials can be split into sets with respect to their orbits and each set can be stored as only one representative polynomial per such a set. Then, instead of computing B and C events while using all the polynomials, we would use only the representatives from each set. Indeed, from the symmetry if two polynomials, each from a different set, should generate an event then each permutation of them generates an event above the same critical value.

Issue 2.

In the current version of the algorithm, we compute, per a set of conics obtained from an intersection of a plane with quadrics at a midpoint, sample points of all the connected components. This lead to a high number of sample points, in general. In order to reduce the number of sample points, we expect that it is, in general, sufficient to compute (b, c) sample points only for bounded connected components in such arrangements of conics. This claim still requires to be confirmed.

Issue 3. Until now, our focus was related to a very specific application of the algorithm.

Nevertheless, we would like to generalize it in order to solve more general problems involving arrangement of quadrics. Our algorithm can deal with relatively high number of polynomials, therefore, we hope that making it more general would attract other communities to use it.

Issue 4. We would like to use the neighborhood motion maps of N 3 to study alterations of connectivity induced by digitized rigid motions in the Eulerian model.

  In this place I acknowledge comments and help from: my supervisors Yukiko Kenmochi and Pascal Romon from whom I learned what does it mean to be a scientist. I am also very thankful for their patience and friendship; Nicolas Passat of the University of Remis Champagne-Ardenne who provided me with many invaluable comments, I think Nicolas should be called my unofficial adviser; Guillaume Moroz of INRIA Nancy thanks to whom I gained my interest in algebraic geometry, and from whom I learned a lot about it; Éric Andres of the University of Poitiers and Victor Ostromoukhov of the University of Lyon 1 for pointing out bugs in our implementation of the algorithm for characterizing bijective digitized rotations; Hugues Talbot of ESIEE Paris and David Coeurjolly of the University of Lyon 1 who helped by allowing us to ran computations on blade machines owned by ESIEE Paris and CC-IN2P3 cluster in Lyon; Bruno Jartoux who has been a

Figure 2 .+ √ 3 2

 23 1(a)). The elements of Z[i] are called Gaussian integers. Similarly, we have the hexagonal lattice Z[ω] = Z ⊕ Zω where ω = -1 2 i is a third root of unity (see Figure 2.1(b)). The elements of Z[ω] are called Eisenstein integers; which are-similarly to Gaussian integers-complex numbers of the form x = a + bω, where a, b ∈ Z.

Figure 2 . 1 :

 21 Figure 2.1: The square grid (a) and the hexagonal pointy topped grid (b). The arrows represent the bases of the underlying lattices.

Lemma 2 . 1 .

 21 Positive integers a, b and c form a primitive Pythagorean triple (a, b, c) if

Figure 2 . 2 :

 22 Figure 2.2: Visualization of Z[i] + ρ (a) and Z[ω] + ρ (b), for 0 < a, b ≤ 2000.Note that, the axes were scaled for a better visualization effect and the distance between two consecutive axes' ticks is 30.

Figure 2 . 3 :

 23 Figure 2.3: Geometric interpretation of: a Pythagorean triple (a = 3, b = 4, c = 5) (a) and a pair of Eisenstein triples, (a = 5, b = 8, c = 7) and (b -a = 3, b = 8, c = 7) (b). Note that the marked angles are: θ = arctan b a , θ = arctan a b

Figure 2 .

 2 Figure 2.5 illustrates digitization cells, i.e. ξ = 1, of Z[i] and Z[ω]. The digitization operator is then defined as a function D : C → Z[κ κ κ], such that ∀x ∈ C, ∃!D(x) ∈ Z[κ κ κ]

Figure 2 . 4 :

 24 Figure 2.4: Visualization of the digitization of a ball B r (0) of the radius r = 2 and centered at the origin with respect to Gaussian (a) and Eisenstein (b) integers. The ball is marked in red and the corresponding sets of digitization cells are filled with a green hatched pattern.

Figure 2 . 5 :

 25 Figure 2.5: Visualization of digitization cells C 1 (0) for: Gaussian (a) and Eisenstein (b) integers. The dashed lines and the white balls represent elements which do not belong to a digitization cell.

Figure 2 . 6 :

 26 Figure 2.6: Examples of three different mappings induced by a rigid motion U: digitization cells corresponding to zero and two preimages are marked by green hatched and red dotted patterns, with their status numbers, respectively. White dots indicate the positions of the images of the points of the initial set Z[κ κ κ] under U.

. 5 )

 5 and we study Ǧ = ŘZ ( 1 0 ) ⊕ ŘZ ( 0 1 ) ⊕ Z ( 1 0 ) ⊕ Z ( 0 1 ), instead of G. The generators of Ǧ are given by the columns of the rational matrix B = Ř I 2 where I 2 stands for the 2 × 2 identity matrix. As B is a rational, full row rank matrix, it can be brought to its Hermite normal form H = [T | 0 2,2 ]. The problem of computing the Hermite normal form H of the rational matrix B reduces to that of computing the Hermite normal form of an integer matrix: c ∈ Z is the least common multiple of all the denominators of B; compute the Hermite normal form H for the integer matrix cB; finally, the Hermite normal form H of B is obtained by c -1 H . The columns of H are the minimal generators of Ǧ. The rank of B is equal to 2. Therefore, H gives a base (κ, λ), so that Ǧ = Zκ⊕Zλ. As H gives an integer base, c Ǧ is an integer lattice. Finally, G = ZX -1 κ ⊕ ZX -1 λ. Conversely, let us prove that G is dense if (a, b, c) is not an Eisenstein primitive triple (up to scaling). Again, we consider Ř = [b 1 | b 2 ], and we prove that for any ε > 0 there exist e, e ∈ Ǧ, linearly independent, such that e < ε, e < ε. Let {.} stand for the fractional part function defined on R 2 . We study the images of {Zb 1 } ∈denotes the first column of Ř. If b 1 contains irrational elements, then {Zb 1 } contains infinitely many distinct points. By compactness ofsubsequence ({n k b 1 }) k∈N , converging to some point in -

Corollary 2 . 7 .

 27 If cos θ = 2a-b 2c and sin θ = √ 3b 2c where (a, b, c) is a primitive Eisenstein triple, the group Ḡ = G/Z[ω] is cyclic and | Ḡ| = c.

Figure 3 . 1 :Figure 3 . 2 :Definition 3 . 4 .

 313234 Figure 3.1: The reference label maps L 1 and L 2 for neighborhoods defined on Z[i] (a-b) and L 1 on Z[ω] (c).

Figure 3 . 3 :Proposition 3 . 5 .

 3335 Figure 3.3: Critical cases: U(p + d) is located on a horizontal line of the square grid (a) and a line segment of the hexagonal grid (b) i.e., a boundary of digitization cells.

Figure 3 . 4 :

 34 Figure 3.4: The remainder range C 1 (0) intersected with the translated (a-b) square and (c) hexagonal grids H -θ • d, d ∈ N r , r ∈ {1, 2}, for rotation angle θ = π 12 . Each grid H -θ • d is colored with respect to each d ∈ N r (0) in the reference label map L r (see Figure 3.2).

Figure 3 . 5 :

 35 Figure 3.5: Three different partitions of the remainder range C 1 (0), square (a-b) and hexagonal (c) grids for rotation angle θ = π12 . The partitions presented in (a) and (c) are for N 1 (0), and in (c) for N 2 (0). Each frame-border color corresponds to the color of each neighbor in the corresponding label maps (see Figure3.2).

Square grid.

  As explained in the former sections the discontinuities of U (p+d) occur when U(p + d) is on the boundary of a digitization cell, as illustrated in Figures 3.3. Setting ρ(p) = x + yi ∈ C 1 (0) and d = u + vi ∈ N r (0), this is formulated by one of the following two equations

  For given d = u + vi and k x (resp. k y ), Equation (3.2) (resp. (3.3)) defines a vertical (resp. horizontal) line in the remainder range C 1 (0), called a vertical (resp. horizontal) critical line.

Figure 3 Figure 3 . 6 :

 336 Figure 3.6: Partitions of the remainder range C 1 (0) by vertical critical lines for N 1 (0) (a) and N 2 (0) (b), and 0 ≤ θ ≤ π 4 . For a better visualization effect, critical lines are projected on the (t 1 , θ)-plane.

that of the index ( 3 ,

 3 -4) (see Figure B.1 in Appendix B).

  43 for θ = α 1 , 37 for θ = α 2 and 30 for θ = α 3 . Such elements of the set M 1 are presented in Appendix C. Note that neighborhood motion maps in Figure C.1 are arranged with respect to the

Figure 3 . 7 :

 37 Figure 3.7: Visualization of minimal Euclidean distances between parallel line segments in the remainder range for N 1 (0) and Z[ω].

ure 3 . 5 .

 35 Figure C.1 the neighborhood motion maps of the indexes (-1, 2) and (0, 2).

Square grid.Lemma 3 . 6 .

 36 Having computed the sets M 1 and M 2 we can observe that some frames of the remainder range correspond to neighborhood motion maps that exhibit nonsurjectivity or non-injectivity of corresponding digitized rigid motions. Let us first provide some important details about the remainder range frames.Neighborhood motion maps for N 2 (p) defined on the square grid, which present nonsurjectivity can be found in Appendix B. As can be noted from the figures in Appendix B, such neighborhood motion maps possess at least one non-labeled Gaussian integer w (white square) that is surrounded by four labeled Gaussian integers at N 1 (w), whose preimages form a 2 × 2 square (see the neighborhood motion map of the frame (0, 0) for their preimages). For example, see the frames (2, -3), (3, -3), (2, -4) and (3, -4), depicted in Figure B.1. Using this observation and Equations (3.2-3.3) we state the following lemma. Let us consider the square grid, U (p) + d $ has no preimage if and only if

Lemma 3 . 7 .

 37 pendix A. They have two labels at the center. For instance, see the frames of the indexes (2, 2), (2, 1) and (2, 0) in Figure A.1. Using this observation and Equations (3.2-3.3) we state the following lemma. U (p) has two preimages which are p and p + d $ , i.e. U (p) = U (p + d),

Figure 3 . 8 .Conjecture 3 . 8 .

 3838 Figure 3.8. For proofs of Lemmas 3.6 and 3.7 we refer to Nouvel and Rémila [22].

Figure 3 . 8 :

 38 Figure 3.8: Examples of remainder range partitioning. The square remainder range together with non-injective zones f 2 $ and non-surjective zones f 0 $ which are illustrated by the red and brown rectangles, respectively (a). The hexagonal remainder range together with non-injective zones c k (f ) marked by hatched zones (b).

Figure 3 . 9 :

 39 Figure 3.9: Comparison of the loss of information induced by digitized rigid motions on the hexagonal and square grids. The red and blue curves correspond to the ratios between areas of non-injective zones and the remainder range for the square and hexagonal grids, respectively. The "x" (resp. "o") markers correspond to the values of the information loss rate 1-|U (S i )| |S i | (resp. 1-|U (Sω)| |Sω| ).

Figure 4 . 1 :

 41 Figure 4.1: Examples of non-surjective frames in the remainder range together with Ḡ obtained for rotations by Pythagorean angles. (a) The non-bijective digitized rotation defined by the primitive Pythagorean triple[START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF][START_REF] Gilder | Integer-sided Triangles with an Angle of 60 •[END_REF][START_REF] Berthé | Discrete Rotations and Symbolic Dynamics[END_REF], and (b) the bijective digitized rotation defined by the twin Pythagorean triple[START_REF] Middleton | Hexagonal Image Processing: A Practical Approach[END_REF][START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF][START_REF] Nouvel | Incremental and Transitive Discrete Rotations[END_REF]. The non-surjective zones are illustrated by brown rectangles. (c) a fundamental square in Ḡ whose vertexes are (nφ φ φ + mψ ψ ψ), ((n + 1)φ φ φ + mψ ψ ψ), ((n + 1)φ φ φ + (m + 1)ψ ψ ψ), (nφ φ φ + (m + 1)ψ ψ ψ), represented by black circles, and f 0 ↓ in brown. The union of the areas filled with a hatched pattern forms a square (i.e. a N ∞ ball of radius 1 2c ) of the admissible translation vectors modulo Zψ ψ ψ + Zφ φ φ. Note that c, r, s, w are elements of Ḡ which surround a non-surjective zone of the remainder range.

Algorithm 1 :

 1 1 (p) belongs to S; otherwise, there is no non-injective mapping involving p under U |S . This leads to the forward algorithm (see Algorithm 1), which returns the set B of all pairs of points having the same image. We can then conclude that U |S is bijective if and only if B = ∅; in other words, U is injective on S \ B. The break statement on line 7 comes from the fact that, in accordance with Remark 2.3, a Gaussian integer can have at most two preimages. Using the same argument, we also restrict the internal loop to the set {→, ↓}. An element-wise injectivity verification of U |S . Data: A finite set S ⊂ Z[i]; a digitized rigid motion U . Result: The subset B ⊆ S whose points are not injective under U .

Figure 4 . 2 :

 42 Figure 4.2: (a) an initial finite set S ⊂ Z[i], colored in black and red. (b) the remainder map image of S, i.e. ρ(p) for all p ∈ S, under U -given by parameters 1 4, arccos35 37 . Since no point ρ(p) lies within the non-injective zone F, we have a visual proof that U restricted to S is injective. (c) the image of S under the digitized rigid motion colored in black and blue. In (c) the Gaussian integer in the middle of the blue square has coordinates 3 + 5i and it is an image, under U , of the Gaussian integer 1 + 6i, which is at the center of the red square in (a).

Figure 4 .

 4 2 illustrates the forward algorithm.

2 .

 2 Foreach line v = k, we obtain the two intersections with the boundary of f 2 ↓ as the maximal and minimal integers for u (see Figure4.3(a)).

Figure 4 . 3 :

 43 Figure 4.3: (a) geometric interpretation of the system of linear inequalities in Equation (4.1), in the (u, v)-plane for (p, q) = (7, 2). The region surrounded by the four lines is f 2 ↓ , and the integer points within are marked by black circles. (b) The remainder range, Ḡ and f 2 ↓ , with the later illustrated by a red square, which corresponds to f 2 ↓ in (a).

Figure 4 . 4 :

 44 Figure 4.4: Visualization of T for u = 1, v = 0 (green points) and p = 2, q = 1. The blue and black arrows represent c(σ, τ ) t and (b, a) t , respectively.

Definition 4 . 10 .

 410 Given a translation t, an angle α = arg(α) is called a hinge angle if there exists at least one Gaussian integer in Z[i] such that its image by a rigid motionrotation by α followed by the translation-has a half-integer part. A hinge angle is represented by an integer quadruple (p 1 , p 2 , k, s) ∈ Z 3 × {0, 1}, where p 1 = (p) and p 2 = (p), p ∈ Z[i] and k + 1 2 stands for a half-grid line and s is a binary flag which allows us to distinguish between different directions of a half-grid line, namely, s = 0 stands for the vertical direction and s = 1 for the horizontal one. Let p = U(p) and p 1 = (p ), p 2 = (p ); then, in accordance with Figure 4.5(b), we obtain

Figure 4 .Lemma 4 . 11 .

 4411 Figure 4.5 illustrates some hinge angles of an integer point. Moreover, we consider a function ζ such that for a quadruple (p 1 , p 2 , k, s) it returns the corresponding angle.

Figure 4 . 5 :

 45 Figure 4.5: Examples of rigid motions which induce transition of p = 7 + 5i between digitization cells; (a) α represented by (7, 5, 7, 1), t = 0 and (b) α represented by (7, 5, 9, 1), t = 7 5 + 13 10 i.

. 10 )

 10 If the sign of the left-hand (resp. right-hand) side of Inequality (4.9) (resp. (4.10))

Figure 4 .

 4 Figure 4.7 presents different images of some finite set S under digitized rigid motions represented by parameters obtained from the extended forward algorithm. Note that for the example represented by Figure 4.2 i.e., the finite set S (see Figure 4.2(a)) and initial parameters 14 , 0, arccos35 37 , where θ = arccos35 37 is given by the Pythagorean triple[START_REF] Gilder | Integer-sided Triangles with an Angle of 60 •[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF][START_REF] Ngo | Topology-preserving Conditions for 2D Digital Images under Rigid Transformations[END_REF], the extended forward algorithm gives C = {(3, 5, 1, 0), (7, 7, 4, 0)}. This

Figure 4 . 7 :

 47 Figure 4.7: (a) an initial finite set S ⊂ Z[i], colored in black and red. (b-c) represent images of S under digitized rigid motions for parameters obtained by the extended forward algorithm for the initial parameters (0, 0, arccos 35 37 ), i.e. C = {ζ(6, 7, 3, 0), ζ(5, 7, 2, 0), ζ(8, 9, 4, 0)}. (b) The image of S for α ∈ (ζ(6, 7, 3, 0), ζ(5, 7, 2, 0)) and (c) the image of S for α ∈ (ζ(5, 7, 2, 0), ζ(8, 9, 4, 0)).In (b-c) the Gaussian integer in the middle of the blue square has coordinates 3 + 5i and it is an image, under U , of the Gaussian integer 1 + 6i, which is at the center of the red square in (a). Please, note that the parameters were obtained with a very experimental implementation of the presented algorithm. Therefore, they may not be complete or correct.

Figure 5 . 1 :

 51 Figure 5.1: A visualization of a mapping between Z[ω] and U(Z[ω]). Elements of Z[ω] (resp. U(Z[ω])) are marked by the gray triangles (resp. the red circles) and their digitization cells are depicted as black (resp. red dotted) line segments. The arrows which correspond to bijective and non-bijective mappings are marked in blue and green (resp. brown), respectively. (see Formula (5.1)).

|γ| 2 ≡ 7 )

 27 Proof. Equations(5.3-5.4) are direct consequences of the parameterization given in Lemma 2.2. For Statement (5.5), let us suppose that there exists ν ∈ Z[ω] such that γ = µ • ν with |µ| 2 = 3 and µ ∈ Z[ω]. Since the squared modulus is multiplicative, |γ| 2 = (|µ||ν|) 2

Figure 5 .

 5 Figure 5.3 illustrates examples of such a situation.

Figure 5 . 2 :

 52 Figure 5.2: A unit cell C 1 (0) -the regular pointy topped hexagon marked by the thick black line segments, and its set of vertexes V . The outer hexagon is the result of the multiplication (2 + ω)C 1 (0), namely, C (2+ω) (0), where the red arrows indicate the new position of the vertexes.

  (i) {γ, γ} and {-ω • γ, -ω • γ}; (ii) {γ, -ω • γ} and {-ω • γ, ω • γ} (see Figure 5.4(a) and (b), respectively). These distances are (i)

Figure 5 . 3 :

 53 Figure 5.3: Visualization of C γ•(2+ω) (0) and C γ•(2+ω) (0) for: s = 3, t = 5 (a); s = 4, t = 9 (b), depicted in black and green, respectively. The usual hexagonal grid is depicted in gray, whereas its mapping by 2 + ω is depicted in gray and represented by dashed line segments. Note that, the Eisenstein integers denoted by labels are also marked by red and blue dots. Each such a label corresponds to the closest dot.

Figure 5 . 4 :

 54 Figure 5.4: Visualization of C γ•(2+ω) (0) and C γ•(2+ω) (0) for the case: s > 0, t = s + 1 (a) and s = 1, t > 1 (b). The two parallel lines discussed in the proof of Lemma 5.4 are illustrated by red and blue dashed lines. Note that, the Eisenstein integers denoted by labels are also marked by red and blue dots. Each such a label corresponds to the closest dot.

Figure 5 . 5 :

 55 Figure 5.5: Distribution of angles whose digitized rotations by them are bijective in (a) the square and (b) the hexagonal grids. In (b), angles obtain from generators of the form s > 0 and t = s + 1 are colored in blue, while angles generated by s = 1 and t > 0, are colored in green.

Figure 5 . 6 : 5 √ 3 11 , and s = 1 , 7 √ 3 11

 5653173 Figure 5.6: Visualization of a bicuspid curve together with Gaussian digitization of its interior on the hexagonal grid (a) and its digitized rotations: non-bijective digitized rotation by angle θ = π 9 (b); bijective digitized rotations given by Eisenstein integers generated by s = 1, t = 2 i.e., θ = arctan 5 √ 3 11 , and s = 1, t = 3 i.e., θ = arctan 7 √ 3 11 (c-d), respectively. In (b) digitization cells which correspond to non-injective cases are marked in red.

Figure 7 . 3 2 0 Figure 7 . 1 :

 73071 Figure 7.1: A visualization of the digitization cell C(0). The dashed lines and the white balls at the corners represent elements which do not belong to a digitization cell.

Figure 7 . 2 :

 72 Figure 7.2: A digitization of a ball B r (0) of the radius r = 3 2 centered at the origin. A continuous image of the ball intersected with Z 3 (a). A digital analogue of the ball B r (0), represented by a union of digitization cells (green cubes) (b). Each small, blue sphere corresponds to an integer point in a digitization cell.

Definition 7 . 1 .

 71 Let y ∈ Z 3 be an integer point. The set of preimages of y with respect to U is defined as M U (y) = {x ∈ Z 3 | U (x) = y}, and y is referred to as an s-point, where s is the status number of y, defined by s = |M U (y)|. In this section, for any x ∈ Z 3 and a digitized rigid motions U , we show that |M U (y)| ∈ {0, 1, 2, 3, 4}. Similar results for 2D are discussed in Chapter 2. 0-point. This situation occurs when a rigid motion does not map any integer point into a digitization cell. Figure 7.4 presents possible situations which create a 0-point. It should be noted from the case presented in Figure 7.4(a) that 0-points possibly can create U

Figure 7 . 3 :

 73 Figure 7.3: Two models of transformations: Lagrangian (a), and Eulerian (b). Red dots represents points of S ⊂ Z 3 , while green ones correspond to points of R 3 .

Figure 7 . 4 : 1 √ 2 , 1 √ 2

 741212 Figure 7.4: A visualization of some 0-point cases. A cross-section of the 3D space illustrating U(Z 3 ) -a rotation by θ = π 12 around ω = (0, 0, 1), superposed with the digitization cells of the target space (a). A part of a non-trivial digital line segment composed of 0-points obtained for U(Z 3 ) with ω = 0, 1 √ 2 , 1 √ 2

3 Figure 7 . 5 :

 375 Figure 7.5: Three distinct configurations of three points (up to symmetries) obtained as extensions of the 2-point configurations. Note that, the triangles' vertexes have integer coordinates.

Figure 7 Property 7 . 6 .

 776 Investigation of the existence of 4-point can be initiated in a similar way. In other words, if a 4-point exists, it should be possible to obtain it from the configuration which leads to a 3-point. Indeed, one can start from a configuration which causes a 3point and add a fourth point to it. Figure 7.6 presents all the possible configurations of four integer points obtained in this way. From Lemmas 7.2-7.4, configurations presented in Figures 7.6(a)-7.6(c) can be eliminated. Then we state the following. A 4-point is created only from a four-point configuration which is forming a unit square.

Figure 7 . 6 : 3 .

 763 Figure 7.6: All possible configurations (up to symmetries) created as extensions of the configuration presented in Figure 7.5(c). The red dashed lines have the length equal √ 3. The blue dashed lines represent configurations governed by Lemma 7.4. Note that, the triangles' vertexes have integer coordinates.

Figure 7 . 7 :

 77 Figure 7.7: A visualization of three different adjacency relations between 3D integer points: face (a); edge (b) and vertex (c).

Figure 8 . 2 :

 82 Figure 8.2: Visualization of q • w ∈ qC(0)q ∪ |q| 2 C(0) together with qC(0)q and |q| 2 C(0), for (a) q = 3 + k and (b) q = 3 + 4i + k, each of which induces a bijective digitized rotation. Points q • w are depicted as blue spheres.

  4 and find the general solution to Equation (8.5), which would allow us to characterize the set of 3D bijective digitized rotations. To share the problem of finding the general solution to characterizing 3D bijective digitized rotations, we provide a complete list of Lipschitz quaternions (up to an integer factor) in the range [-10, 10] ⊕ [-10, 10]i ⊕ [-10, 10]j ⊕ [-10, 10]k, such that the corresponding digitized rotations are bijective (https://doi.org/10.5281/ zenodo.814552) and non-bijective (https://doi.org/10.5281/zenodo.814607). The lists were computed with our implementation of Algorithm 3, which can be downloaded from https://doi.org/10.5281/zenodo.814569.

Figure 8 . 3 :

 83 Figure 8.3: Visualization of q • w ∈ qC(0)q ∩ |q| 2 C(0) -depicted as blue points, qw ∈ qC(0)q \ |q| 2 C(0) -depicted as red points, and |q| 2 C(0) \ qC(0)qdepicted as green points, for (a) q = 4 + k and (b) q = 2 -3i -2j -5k, each of which induces a non-bijective digitized rational rotation.

Figure 9 . 9 . 2

 992 1 illustrates an example of a 3D digital face-connected set (N 3 (p)) which fulfill a straightforward extension of the Ngo's regularity definition but it does not preserve its connectivity under a digitized rigid motion. The example presented in Figure9.1 illustrates a case such that a 3D digital face-connected set has been mapped by a digitized rigid motions onto two 3D digital face-connected sets, or one 3D digital edge-connected set.The goal of this chapter is to develop an algorithm to compute the parameters of digitized rigid motions leading to all the distinct images of N 3 (p) under U . Then, as a part of our future research we plan to use these parameters to further study the issue of connectivity alterations under D • U -1 . Neighborhood Alterations Under Digitized 3D RigidMotionsThe digitized rigid motions U = D • U are piecewise constant, and thus non-continuous, which is a consequence of the nature of the digitization operator D. In particular, the image U(p) of a given point p ∈ Z 3 may remains constant as the parameters of U vary, and then suddenly jump from one point of Z 3 to another. In other words, neighborhood N r (p) evolves non-continuously, under digitized rigid motions, in accordance with the parameters of U that underlies U (see Figure9.2). Hereafter, without loss of generality

Figure 9 . 1 :( 1 √ 2 , 1 √ 2 , 1 2 3 .Figure 9 . 2 :

 9112121392 Figure 9.1: Visualization of a case such that the digital set N 3 (0) -which fulfill a straightforward extension of Ngo's regularity conditions and is face-connected, does not preserve its connectivity under a 3D digitized rigid motion. In (a), points of the target space under the digitized rigid motionD • U -1 such that ω = ( 1 √ 2 , 1 √ 2 , 0), θ = 65 and t = (-1 5 , 1 5 , 1 5 ), are represented by gray and red spheres. The transparent-green cubes represent the digitization cells of N 3 (0). The gray spheres represent points which were not mapped under U onto the digitization cells of N 3 (0), whereas the red ones represent the ones which were. In (b) the green and blue cubes represent the digitization cells of points of the target space which were mapped by U onto N 3 (0), i.e. the points represented by the red spheres in (a). The blue digitization cell represents the case in which the connectivity relation of N 3 (0) was not preserved under U . The figures from 1 to 4 represent the corresponding layers of the digital set in (b).

3 ,

 3 is partitioned by a set of hypersurfaces given by Equations (9.1) into a finite number of connected subsets, namely, 6D open cells. In each cell, points induce different rigid motions U |Nr(p) but identical digitized rigid motions U |Nr = D • U |Nr(p) . For a given neighborhood N r (p) of radius r, hypersurfaces (9.1) in Ω are given by the possible combinations of integer 4-tuples (d 1 , d 2 , d 3 , k i ) for i = 1, 2, 3 where d = (d 1 , d 2 , d 3 ) ∈ N r (p) \ {p} and k i ∈ H(N r (p)). Since |N r (p)| -1 is in O(r 3 ) and |H(N r (p))| is in O(r), the number of considerable hypersurfaces is in O(r 4 ), and thus in accordance with [67, Theorem 21.1.4] the overall complexity of the arrangement is theoretically bounded by O(r 24 ).

. 1 )

 1 for different d ∈ N r (p) and k ∈ H(N r (p)) 3 , we can reduce the problem to the study of an arrangement of surfaces in the (a, b, c)-space, and then lift the solution to the six dimensional space.

Figure 9 . 3 :

 93 Figure 9.3: Examples of quadrics of rational coefficients.

Definition 9 . 1 .Figure 9 . 4 :

 9194 Figure 9.4: 2D examples demonstrating a local trivial (a) and a nontrivial (b)fibrations. In (a), the topology of the arrangement above the interval (a 0 , a 1 ) is constant, while in (b) it is not, i.e. in (b) there is an element a * of the bifurcation set B in the interval (a 0 , a 1 ). Note that in (a) a 0 , a 1 ∈ B while in (b) a 0 , a 1 / ∈ B.

Figure 9 . 5 :

 95 Figure 9.5: Visualization of a maximal connected component C bounded by two quadrics: Q 1 = ab + c (the green-orange surface) and Q 2 = a 2 + 4ab + b 2 + c 2 -4c + 1 (the blue surface). The two red curves represent the intersection of the surfaces i.e., Q 1 = Q 2 = 0. The pink curve represents ∂C v . The a-, b-and caxes were re-oriented and the origin changed for a better visualization.

Figure 9 .Figure 9 .Corollary 9 . 3 .

 9993 Figure 9.5 shows a maximal connected component C bounded by two quadrics, and Figure 9.10 illustrates intervals such that the topology of some C a , a ∈ (α, β) remains constant.

Type A .

 . The first type corresponds to values s ∈ K(ρ |Sp ) above which topology of open connected components in A changes. Algebraically, such an event corresponds to a value s ∈ R for which there is a solution to the systemQ p (s, b, c) = ∂ b Q p (s, b, c) = ∂ c Q p (s, b, c) = 0,and s is called a-critical value. In other words, this corresponds to the situation a = s is tangent to a quadric Q p . Note also that, the critical values of the type A include projections of the isolated singularities.

Figure 9 . 6 :

 96 Figure 9.6: Example of events of: type A -a sweeping plane tangent at a point to a quadric (a); type B -a curve of an intersection of two quadrics lays in a sweeping plane (b), and type C -a point of an intersection of three quadrics lays in a sweeping plane (c). Sets of points, which induce an event are depicted in red and a sweeping plane is depicted in green.

Figure 9 .Lemma 9 . 4 .

 994 Figure 9.6 shows examples of events of types A, B and C.

  Step 1: we compute∂ b Q(a, b, c) = ub + vc + wa + t and ∂ c Q(a, b, c) = u b + v c + w a + t , whereu, v, w, t, u , v , w , t ∈Z are coefficients of the corresponding polynomials and Q ∈ Q.

Figure 9 . 7 :

 97 Figure 9.7: Example of asymptotic critical value. A line (in blue) is parallel to b-axis and tangent to an asymptote-the red curves laying on the yellow surface-in a point at infinity. For readability only a part of the yellow surface is presented.

Figure 9 . 8 :

 98 Figure 9.8: Visualization of a critical event of B ∞ type. The intersection of quadrics: Q 1 = bc + a (the orange-green surface) and Q 2 = b 2 -bc + a -1 (the blue surface) leads to the red curves which exhibit an asymptotic behavior at a = 1 2 . The a-, b-and c-axes are re-oriented and the origin is changed for a better visualization effect. The respective projections of C 1,2 onto the (a, b)and (a, c)-plane are illustrated in Figure 9.9.

Figure 9 . 9 :

 99 Figure 9.9: Visualization of the projections of C p,q (the light blue curve) defined by the same quadrics as in Figure 9.8. These projections are P b(a, b) = b 2 + 2a -1, (a) and P c(a, c) = 2ac 2 + a 2 -c 2 , (b).We have an asymptote in the (a, c)-plane for 2a -1 = 0, i.e. when a = 1 2 -which is marked by a pink vertical line.

Figure 9 .

 9 Figure 9.10: A visualization of sweeping of a set of quadrics. Intersection planes at three different midpoints depicted in green. Between the planes we have acritical valuesa values in which topology of an arrangement changes. Conics obtain from quadrics in red and black.

  planes in the range C(0) for each (a, b, c) ∈ R, by setting d ∈ N r (p) and k ∈ H(N r (p)) 3 . These planes divide C(0) into cuboidal regions.Figure 9.12 illustrates an example of such critical planes in C(0).To obtain different images of N r (p) rotated by a given a, b, c ∈ Q, under translations (t 1 , t 2 , t 3 ) ∈ C(0), we compute the arrangement of planes in C(0) which involves sorting of critical planes and finding a midpoint of each cuboidal region bounded by them.

Figure 9 . 11 :Remark 9 . 5 .

 91195 Figure 9.11: The first intersections of 81, 513 and 741 quadrics obtained for N 1 (p), N 2 (p) and N 3 (p), respectively.

Figure 9 . 12 :

 912 Figure 9.12: Visualization of the critical planes for N 1 (p) and some (a, b, c).For the sake of visibility three types of orthogonal critical planes are presented separately.

7 )

 7 for i = 1, 2, 3 where d, d ∈ N 1 (p), k, k ∈ H(N 1 (p))3 . This inducesk i -k i + 1 -u i • R(dd ) > 0,(9.8)where we know that q = k i -k i +1 ∈ Z∩[-1, 3]. We then consider the following different cases of v = dd , and we consider k and k such that for any R Equation 9.8 is valid.

  our implementation we have tried to obtain a good performance. Since the computation of critical values and sample points are not difficult to parallelize, we implemented this part of the algorithm in Maple Grid framework. Moreover, some parts of the algorithm can be run on a POSIX compatible cluster. We have performed some tests on a machine equipped with two processors Intel(R) Xeon(R) E5-2680 v2; clocked at 2.8 GHz, with installed 251.717 GiB of memory and the CC-IN2P3 computational cluster in Lyon, France.After the uncoupling, we obtain 81, 513 and 741 quadrics for N 1 (p), N 2 (p) and N 3 (p), respectively. Then the critical values are computed and sorted. This step takes in our current implementation a few minutes for N 1 (p) and up to a few days for N 2 (p) and N 3 (p) and currently cannot be computed on a cluster. In the next step the sample points (a, b, c) are computed and used to compute the translational sample points. The computation of different images of the image patch N r (p) consists of calculating for each sample point (a, b, c) an arrangement of planes in the (t 1 , t 2 , t 3 )-space (see Figure9.12).

Figure 9

 9 Figure 9.13: A visualization of N 1 (p) (a) and its image under the digitized rigid motion given by a = 137473696921 274877906944 , b =

Issue 1 .

 1 The second degree polynomials discussed in the problem of computing sample points of the rotational part of the rigid motions exhibit interesting properties which may lead to time improvements for computations of the events of B and C types. Indeed, one can notice that having computed quadricsQ i [d, d , k i , k i ](a, b, c), for example for i = 1,it is possible to obtain all the remaining quadrics for i = 2 and i = 3 just by permuting variables a, b, c of the polynomials of the computed set. One can also notice that the different polynomial have different orbits i.e., number of permutations before arriving

Table 2 .

 2

1: Basic properties of Gaussian and Eisenstein integers.

  2 ∈ Z therefore verification of Inequality (4.6) can be done with only integer calculations. Finally, to check if α > θ one has to check at most two

	Inequalities (4.5-4.6).

Lemma 4.12. Let α and β be two hinge angles. We can check if α > β in constant time by using only integer computations.

  can be determined in constant time 2 by considering half-grid lines which bound the closest digitization cell i.e., C 1 (U (p)).

		p p
	θ ( p , θ ) h t > h < t ( p , θ )	p	p
	0
	Figure 4.6: Visualization of different images of the point p = (7, 5) under rigid
	motions given by fixed t = 0 and rotations by angles: θ = 3 100 and hinge angles h <
	Figure 4.6 shows examples of h <

be the ordered set of hinge angles for a given p = p 1 + p 2 i ∈ Z[i], which is different from the origin. Then, using results of Lemmas 4.11 and 4.12, given a Pythagorean (or hinge) angle θ, we define a function

h < t (p, θ) (resp. h > t (p, θ))

which returns, for given p ∈ Z[i] and rational translation t, t (p, θ) = -ζ(7, 5, 4, 1) -clockwise rotation of p, h > t (p, θ) = ζ(7, 5, 5, 1), represented by points p , p and p, respectively. the closest lower (resp. upper) hinge angle to θ in E t (p), namely h < t (p, θ) < θ (resp. θ < h > t (p, θ)). In other words, α ∈ E t (p) such that h < t (p, θ) < α < θ (resp. θ < α < h > t (p, θ)). Note that h < t (p, θ) (resp. h > t (p, θ)) t (p, θ) (resp. h > t (p, θ)) for some p ∈ Z[i] and (t 1 , t 2 , θ).

  Note that at least one coordinate of ρ α (p) is on the border of the remainder range. Moreover, intermediate hinge angles which do not induce non-injectivity are stored in C: these angles induce different images of S under digitized rigid motions. A pseudo-code of the extended forward algorithm is represented by Algorithm 2.

	function h < t (p, θ) (resp. h > t (p, θ)) is applied to update γ < t (resp. γ > t ) by finding a
	hinge angle α ∈ [γ < t , γ >

t ] such that non-injectivity occurs for p ∈ S.

  An algorithm to compute for a finite set S ⊂ Z[i] a bijectively stable ordered set of hinge angles with respect to a given translation t.

	2 2 + 1

2 [15, Chapter 3] and the cardinality of a finite set S, leading to O(n|S|), which is rewritten by O( |S||S|) if we assume that S forms a square. Algorithm 2: Data: A finite set S ⊂ Z[i]; a digitized rigid motion U defined by θ and t. Result: An ordered set of hinge angles C

  Before going further let us state the following results related to factoring of primitive Eisenstein integers and used in the later sections. Let θ be an Eisenstein integer such that θ is not the product of an integer and an Eisenstein unit. Then θ = θ • υ where υ ∈ Υ, if and only if |θ| 2 ≡ 0 (mod 3).

	Lemma 5.1. Proof. Solving θ = θ • υ where υ ∈ Υ, is equivalent to solving θ 2 = |θ| 2 υ, whose
	solutions (in C) are θ = ±|θ| √	υ, where	√	υ means any root. Two possibilities occur:
	(i) υ ∈ {1, ω, ω}, which are squares in Z[ω]; this is the first case in the Lemma 5.1; (ii) υ ∈ {-1, -ω, -ω}, whose roots are not in Z[ω] but in Z[ω]/ √ 3; in order for θ to be an Eisenstein integer, its modulus |θ| must contains a √ 3 factor.

Lemma 5.2. For a given

θ = a + bω ∈ Z[ω] + ρ , considering γ = (s + t) + tω ∈ Z[ω]

where s and t are generators of (a, b, c) (see Lemma 2.2), we then have

  Working in the framework of Eisenstein rational rotations defined by θ ∈ Z[ω] ρ , allows us to turn to Eisenstein integers as |θ|G ⊂ Z[ω]. For the reason that Eisenstein integers are nicer to work with, we do scale G by |θ|. Similarly, to the former discussion, after scaling G by |θ|, we consider the finite set of remainders obtained by comparing the lattice |θ|U(Z[ω]) with the lattice |θ|Z[ω], and applying the scaled version of the map

	S θ defined as
	Šθ :

  1 3 and are not in Z[ω]. Then, since |γ| 2 (resp. |γ| 2 ) is not a multiple of 3 (see Lemmas 5.1 and 5.2), therefore, vertexes of C γ

  An algorithm which checks if a given Lipschitz quaternion is related to a 3D bijective digitized rotation.

	.1
	lists up some examples of Lipschitz quaternions that generate non-simple 3D bijective
	digitized rotations.
	Algorithm 3:

Data: a Lipschitz quaternion q = a + bi + cj + dk s.t. gcd(a, b, c, d) = 1.

Table 8 .

 8 1: Examples of Lipschitz quaternions which generate 3D bijective digitized rotations and their corresponding angel-axis representations.

  Our motivations have their origins in image processing where the Eulerian transformation model (see Chapter 7) is commonly used. It is due to the fact that digitized rigid motions in Eulerian model are surjective. Indeed, to explain the main problem we assume-just in this section-that the Eulerian model is used. Digitized rigid motions may change adjacency relations between points of a digital set S ⊂ Z 3 . As a consequence, an application of a digitized rigid motion to a set of digital connected sets may lead to splitting or merging of these digital connected sets. In this regard, these topological problems have been studied for 2D digitized rigid motions by Ngo et al. [27]. In particular, they have defined a notion of regularity on 2D digital sets and proved sufficient conditions such that 2D digital edge-connected regular sets remain edge-connected under any digitized rigid motion. For the definition of regularity given by Ngo et al. we refer readers to [27, Definition 12]. Note that, a few years earlier a more general-but overlooked by the community-result was stated without a proof by Bazin et al. for 2D and 3D rigid motions

  1 , t 2 , t 3 . Then the inequalities (9.2) state precisely the necessary and sufficient conditions for the existence of the translation part t of such a rigid motion, assuming that a, b, c are already known. Let us now remark that all these inequalities, i.e. all inequalities obtained for each configuration

(d, k

), can be summed up in three inequalities indexed by i:

max d∈Nr(p)

  Then we state the following results which allow us to focus-during Step 2 of the algorithm-on a subset of quadrics of Q, i.e. a subset of quadrics which bound a maximal open connected component. Let C be a maximal open connected cell of R 3 \ p S p . Let β be the lowest value of B such that C inf < β and let v ∈ (C inf , β). Finally, let ∂C v be the boundary of C v defined as an intersection of C with a plane a = v, and let J C be a set of edges. More precisely, J C is the set of indexes p such that the intersection of S p with ∂C v has dimension one. Then C inf ∈ B p for all p ∈ J C .

	Lemma 9.2.

r =p,q =r ρ(P p,q,r ) and B = p B p .

  using [69, Proposition 2.5 and Definition 3.1] with df = ∂Q ∂b and ∂Q ∂c are linear functions, this implies that in the definition of K ∞ , the expression |b n |+|c n | divided by the denominator of q(a n , b n , c n ) is bounded. In particular the numerator of q(a n , b n , c n ) converges toward 0. More specifically, ∂Q ∂b and ∂Q ∂c converge toward 0. On the other hand, either |b n | or |c n | goes toward infinity. Assume without restriction of generality that |b n | goes toward infinity. In this case, the function

	 	1 ∂Q	0 ∂Q	0 ∂Q	  , there
		∂a	∂b	∂c
	exists a sequence (a

n , b n , c n ) ∈ R 3 such that |b n | + |c n | → ∞ and a n → a and (|b n | + |c n |)q(a n , b n , c n ) → 0. In particular, since ∂Q ∂a ,

  org/10.5281/zenodo.573014, https://doi.org/10. 5281/zenodo.573015 and https://doi.org/10.5281/zenodo.802850. Moreover, a visualization tool 3DNMMVierwerDB can be downloaded from https://github.com/ copyme/NeighborhoodMotionMapsTools. Figure 9.13 shows some images of an image patch for fixed (a, b, c) values and different (t 1 , t 2 , t 3 ) values.

https://www.imagemagick.org

http://netpbm.sourceforge.net

A former French type of thesis equivalent, up to some degree, to a habilitation.

sin(θ) + 3 √ 3 cos(θ) -2 √ 3 i.3.6 Preservation of InformationIn this section, we use the result of the previous section in order to compare the loss of information induced by rigid motions on the square and hexagonal grids. Indeed, we aim to determine on which type of grid digitized rigid motions preserve more information.

This is dedicated to Vincent Nozick of the University Paris-Est Marne-la-Vallée who many times asked us interesting questions about possible practical applications of our work.

Our implementation of the forward and backward algorithms can be downloaded from http://doi. org/10.5281/zenodo.248742

In[START_REF] Thibault | Computing Upper and Lower Bounds of Rotation Angles from Digital Images[END_REF], Thibault et al. proposed an algorithm for computing hinge angles h < t (p, θ) and h > t (p, θ)-for t = 0-in a logarithmic time, which can be improved to constant time while considering half-grid lines which bound the closest digitization cell, i.e., C1(U (p)). Notice that the algorithm also needs a modification in the while loop condition, such that kmax -kmin ≤ 1, to avoid an infinite loop for some points, e.g., p = 1.

http://www.sagemath.org

The complete list of the polynomials can be downloaded from https://doi.org/10.5281/zenodo.

Chapter 5

Bijective Digitized Rotations on

Regular Hexagonal Grid

In this chapter, we study the bijectivity of digitized rotations defined on the hexagonal grid and we consider an approach similar to the one proposed by Roussillon and Coeurjolly [START_REF] Roussillon | Characterization of Bijective Discretized Rotations by Gaussian Integers[END_REF]. We prove that there exist two subsets of Eisenstein integers yielding bijective digitized rotations. This differs from the square case, where only one subset is involved.

We also show that bijective digitized rotations on the hexagonal grid are more numerous than their counterparts on the square grid for angles relatively close to multiple of π 3 k, k ∈ Z, angle. This chapter is based on the contribution [START_REF] Pluta | Characterization of Bijective Digitized Rotations on the Hexagonal Grid[END_REF].

Bijectivity of Digitized Rotations

Let us consider the rigid motions defined by Equation (2.1) such that t = 0. Since Lemma 4.1 remains valid for digitized rigid motions defined on Z[ω], within this chapter we consider only rotations by an angle θ = arg(θ) where θ is an Eisenstein integer given by a primitive Eisenstein triple, i.e. θ ∈ Z[ω] ρ (see Chapter 2).

Set of Remainders

We start our study of bijectivity by comparing the rotated lattice U(Z[ω]) with Z[ω].

Then, the digitized rotation U = D • U is bijective if and only if ∀λ ∈ Z[ω] ∃!κ ∈ Z [ω] such that U(κ) ∈ C 1 (λ). This is equivalent to the "double" surjectivity relation used by

Dense Subgroups and Non-injectivity

The key to understanding the conditions that ensure the bijectivity of U is the structure of G q . For this reason, we start by looking at the image G q of S q , and discuss its density. Proposition 8.1. If one or more generators of G q have an irrational term, then G q ∩ Y is dense for some nontrivial subspace Y . We say that G q has a dense factor.

On the contrary, we have the following result. Proposition 8.2. If all generators of G q have only rational terms, then there exist vectors σ σ σ, φ φ φ, ψ ψ ψ ∈ G q which are the minimal generators of G q .

Proof. The generators of G q are given by the rational matrix B = [R | I 3 ] where I 3 stands for the 3 × 3 identity matrix and R is the corresponding rotation matrix. As B is a rational, full row rank matrix, it can be brought to its Hermite normal form

where T is a non-singular, lower triangular non-negative matrix and 0 3,3 stands for 3 × 3 zero matrix, such that each row of T has a unique maximum entry, which is located on the main diagonal 1 [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF]. Note that the problem of computing the Hermite normal form H of the rational matrix B reduces to that of computing the Hermite normal form of an integer matrix: let s stand for the least common multiple of all the denominators of B which is given by s = |q| 2 ; compute the Hermite normal form H for the integer matrix sB; finally, the Hermite normal form H of B is obtained by s -1 H . The columns of H are the minimal generators of G q . Let us remind that the rank of B is equal to 3. Therefore, H gives a base (σ σ σ, φ φ φ, ψ ψ ψ), so that G q = Zσ σ σ + Zφ φ φ + Zψ ψ ψ.

As H gives an integer base, sG q is an integer lattice. Lemma 8.3. Whenever G q is dense, the corresponding 3D digitized rotation is not bijective.

Lemma 8.3 can be proved in a similar way as Lemma 4.1 in Part I.

When G q is dense (see Figure 8.1(a)), the reasoning of Nouvel and Rémila, originally used to discard 2D digitized irrational rotations as being bijective [START_REF] Nouvel | Characterization of Bijective Discretized Rotations[END_REF], enables us to show that a corresponding 3D digitized rotation cannot be bijective as well. What differs from the 2D case is the possible existence of non-dense G q with a dense factor in the 3D case (see Figure 8.1(b)). In this context, we state the following conjecture. Conjecture 8.4. Whenever G q has a dense factor, the corresponding digitized rotation is not bijective. 1 Note that the definition of Hermite normal form varies in the literature.

Chapter 9

Computing 3D Neighborhood

Motion Maps

Rigid motions defined on Z 3 are simple yet crucial operations in many image applications (e.g., image registration [START_REF] Zitova | Image Registration Methods: A Survey[END_REF] and motion tracking [START_REF] Yilmaz | Object Tracking: A Survey[END_REF]). However, it is also known that such operations cause geometric and topological defects [START_REF] Ngo | Topology-preserving Conditions for 2D Digital Images under Rigid Transformations[END_REF][START_REF] Ngo | Topology-preserving Rigid Transformation of 2D Digital Images[END_REF][START_REF] Pluta | Topological Alterations of 3D Digital Images Under Rigid Transformations[END_REF]. As such alterations happen locally, due to digitization, discrete motion maps have been studied for neighborhoods of integer points, in order to understand such defects at local scale [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF][START_REF] Nouvel | On Colorations Induced by Discrete Rotations[END_REF].

For such a local analysis, one wishes to generate all possible images of a neighborhood under digitized rigid motions. In digital geometry and combinatorics, complexity analyses of such a problem have been made for several geometric transformations. The complexities are related to the size of a given finite digital set. To our knowledge such complexities are: O(n 3 ) for 2D rotations [START_REF] Amir | Faster Two-dimensional Pattern Matching with Rotations[END_REF]; O(n 9 ) for 2D rigid motions [START_REF] Ngo | Combinatorial Structure of Rigid Transformations in 2D Digital Images[END_REF] and O(n 18 ) for 2D affine transformations [START_REF] Ch | On the Complexity of Affine Image Matching[END_REF], where n stands for the diameter of a finite digital set.

Later, in this chapter we show that the theoretical complexity of such a problem for 3D rigid motions is O(n 24 ).

There are few algorithms available for generating all the transformed images from a given digital set. Algorithms known to us are: 2D rotations [START_REF] Nouvel | Configurations Induced by Discrete Rotations: Periodicity and Quasi-periodicity Properties[END_REF]; 3D rotations around a given rational axis [START_REF] Thibault | Rotations in 2D and 3D Discrete Spaces[END_REF][START_REF] Thibault | 3D Discrete Rotations Using Hinge Angles[END_REF]; 2D rigid motions [START_REF] Pluta | Bijective Digitized Rigid Motions on Subsets of the Plane[END_REF][START_REF] Ngo | Combinatorial Structure of Rigid Transformations in 2D Digital Images[END_REF] and 2D affine transformations [START_REF] Ch | On the Complexity of Affine Image Matching[END_REF].

However, none of them can be applied to 3D rigid motions.

In this chapter, we formulate this problem on a finite digital image as an arrangement of 3D surfaces given by second degree polynomials, containing many degenerate cases.

We then solve the problem by computing all the 3D open cells in this arrangement. The original problem involves a naive decomposition of the six dimensional parameter space

Sorting Critical Values

In this section we focus on the representation of a-critical values as real algebraic numbers-roots of univariate polynomials-and operations such as comparisons of them, which are necessary to sort a-critical values.

Similarly to Mourrain et al. [START_REF] Mourrain | On the Computation of an Arrangement of Quadrics in 3D[END_REF], we represent a real algebraic number α as a pair: an irreducible univariate polynomial P ∈ Z[a] such that P (α) = 0 and an open isolating interval (g, h), with g, h ∈ Q, containing α and such that there is no other root of P in this interval. Note that the isolation of the roots of an irreducible univariate polynomial can be made using Descartes' rule [START_REF] Rouillier | Efficient Isolation of Polynomial's Real Roots[END_REF].

Let α = (P, (g, h)) and β = (Q, (i, j)) such that P, Q ∈ Z[a] and g, h, i, j ∈ Q, stand for two real algebraic numbers. Then we can conclude if α = β while checking a sign of gcd -a polynomial greatest common divisors of P and Q at an intersecting interval. Note that, when gcd(P, Q) is a polynomial then its roots are the common roots of P and Q.

On the other hand, to conclude if α is greater than β or β greater than α, we apply a strategy which consists of refining the isolating intervals until they are disjoint. When two intervals are disjoint then we can compare their bounds and conclude if α is greater than β (or β greater than α) 1 . To refine an isolating interval of real roots, one can use e.g., bisection of intervals, Newton interval method [START_REF] Hansen | Global Optimization Using Interval Analysis -The Multi-dimensional Case[END_REF], [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF]Chapter 5] or quadratic interval refinement method proposed by Abbot [START_REF] Abbott | Quadratic Interval Refinement for Real Roots[END_REF].

The ability to compare two different algebraic numbers allows us to sort a list of events which can be done with well-known sorting algorithms such as quicksort. Some neighborhood motion maps are symmetric with respect to the origin i.e., a neighborhood motion map of the index (0, 0). 1 (4-neighborhood case) 110

Sweeping a Set of Quadrics

Neighborhood motion maps of G U 1 , as label maps, for θ ∈ 0, π 6 . Each label (p, q) corresponds to the frame f θ p,q . Neighborhood motion maps which correspond to non-injective zones are marked by red dashed frames. The edges of the neighborhood motion maps graph are marked by color line segments which connect different neighborhood motions maps (see Chapter 3 of Part I). 1 (4-neighborhood case) 111 . Some neighborhood motion maps are symmetric with respect to the origin i.e., the neighborhood motion map of the index (0, 0). 2 (8-neighborhood case) 114

(-4,-1) (-3,-1) (-2,-1) (-1,-1) (0,-1) (1,-1) (2,-1) (3,-1) (4,-1)

.1: Neighborhood motion maps of G U 2 , as label maps, for θ ∈ (0, α 1 ). Each label (p, q) corresponds to the frame f θ p,q . Neighborhood motion maps which correspond to non-injective zones are marked by brown dashed frames. The edges of the neighborhood motion maps graph are marked by color line segments which connect different neighborhood motions maps (see Chapter 3 of Part I). 2 (8-neighborhood case) 115

.2: Neighborhood motion maps G U 2 , as label maps, for θ ∈ (α 1 , α 2 ) that differ from those for θ ∈ (0, α 1 ). Each label (p, q) corresponds to the frame f θ p,q . Neighborhood motion maps which correspond to non-injective zones are marked by brown dashed frames.

.4: Neighborhood motion maps G U 2 , as label maps, for θ ∈ (α 3 , α 4 ) that differ from those for θ ∈ (α 2 , α 3 ). Each label (p, q) corresponds to the frame f θ p,q . Neighborhood motion maps which correspond to non-injective zones are marked by brown dashed frames.

(-4,-1) (-3,-1) (-2,-1) (-1,-1) (0,-1) (1,-1) (2,-1) (3,-1) (4,-1) Neighborhood motion maps for G U 1 and their graph 121