Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Géométrie discrète, M2 IGI, 2014.

Tristan Roussillon

24/09/2013

Objets discrets

T. Roussillon Géométrie discrète, M2 IGI, 2014. 1 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Plan

1 Un théorème de Minkowski

2 Convexité discrète et linéarité discrète

3 Droite discrète et algorithmes

4 Droites discrètes et arithmétique

T. Roussillon Géométrie discrète, M2 IGI, 2014. 2 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Réseau (lattice)
{ae~1 + be~2 |a, b ∈ Z} où {e1 , e2 }, base de R2

T. Roussillon Géométrie discrète, M2 IGI, 2014. 3 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Réseau (lattice)
{ae~1 + be~2 |a, b ∈ Z} où {e1 , e2 }, base de R2

T. Roussillon Géométrie discrète, M2 IGI, 2014. 3 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Réseau

Le réseau Λ = Z2 (ensemble des couples d’entiers relatifs) est

appelé réseau fondamental.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 4 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Lemme de l’aire

Enoncé
Considérons une région ouverte RO incluant l’origine O d’un
réseau Λ. Si pour tout couple de points P , Q, les copies de RO
en P et Q ne s’intersectent pas, alors l’aire de RO est inférieure à
1.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 5 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Lemme de l’aire

Enoncé
Considérons une région ouverte RO incluant l’origine O d’un
réseau Λ. Si pour tout couple de points P , Q, les copies de RO
en P et Q ne s’intersectent pas, alors l’aire de RO est inférieure à
1.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 5 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Lemme de l’aire

Preuve
Soient A, l’aire de RO , d la dist. max. entre O et un point de RO .
On considère les (2n + 1)2 régions incluent dans le carré
isothétique de côté (2n + 2d) pour borner supérieurement A
(quand n → ∞) :

2d − 1 2
(2n + 1)2 A ≤ (2n + 2d)2 ⇔ A ≤ (1 + )
2n + 1

2n + 1 2n + 2d

T. Roussillon Géométrie discrète, M2 IGI, 2014. 6 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire

Enoncé
Si l’aire de RO est strictement supérieure à 1, alors il existe un
couple de points P , Q, tel que les copies de RO en P et Q
s’intersectent (preuve par contradiction).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 7 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Théorème de Minkowski

Enoncé
Toute région ouverte convexe, symétrique autour de O, et d’aire
strictement supérieure à 4, inclut des points de Λ autres que O.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 8 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Théorème de Minkowski

Enoncé
Toute région ouverte convexe, symétrique autour de O, et d’aire
strictement supérieure à 4, inclut des points de Λ autres que O.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 8 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Théorème de Minkowski

Enoncé
Toute région ouverte convexe, symétrique autour de O, et d’aire
strictement supérieure à 4, inclut des points de Λ autres que O.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 8 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Exemples particuliers
La région RO est un parallélogramme d’aire 4 dont les sommets
sont des points de Λ.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 9 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Exemples particuliers
La région RO est un parallélogramme d’aire 4 dont les sommets
sont des points de Λ.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 9 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire
Enoncé
Tout parallélogramme dont les sommets sont des points de Λ et
d’aire inférieure ou égale à 1 n’inclut aucun point de Λ autre que
ses sommets.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 10 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 1 : réseaux équivalents

Réseau fondamental

T. Roussillon Géométrie discrète, M2 IGI, 2014. 11 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 1 : réseaux équivalents

Equivalent au réseau fondamental

T. Roussillon Géométrie discrète, M2 IGI, 2014. 11 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 1 : réseaux équivalents

Equivalent au réseau fondamental

T. Roussillon Géométrie discrète, M2 IGI, 2014. 11 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 1 : réseaux équivalents

Différent du réseau fondamental

T. Roussillon Géométrie discrète, M2 IGI, 2014. 11 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 1 : réseaux équivalents

Uni-modularité
Soit un réseau L engendré par les vecteurs ~u(u1 , u2 ) et ~v (v1 , v2 ),
exprimés dans le système decoordonnées  du réseau Λ.
u1 u2
La matrice de passage M = donne les coordonnées
v1 v2
sur Λ de tout vecteur w exprimé sur L.
Il y a bijection entre L et Λ, qui sont deux réseaux équivalents ssi
M est uni-modulaire (|M | = u1 v2 − u2 v1 = ±1).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 12 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Preuve
L’aire A du parallélogramme engendré par les vecteurs ~u(u1 , u2 )
et ~v (v1 , v2 ) se calcule par exemple ainsi :
v1 v2 u1 u2 v1 v2 u1 u2
A= +( + u1 v2 ) − ( + v1 u2 ) − .
2 2 2 2

v2 ~v

u2
~u

u1
v1

Ce qui se simplifie en :
A = u1 v2 − u2 v1 .
Le théorème de Minkowski conclut.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 13 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 2 : Théorème de Pick

Formule
Soit un polygone dont les sommets sont des points de Λ, d’aire
A, contenant J points, dont B se trouvant exactement sur le bord.
B
A=J− − 1.
2
9
Exemple d’un polygone d’aire 17.5 = 23 − 2 − 1.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 14 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Conséquence 2 : Théorème de Pick

Preuve
Par récurrence, on exploite l’additivité de la formule :
formule vraie pour tout triangle d’aire 1/2 (Minkowski).
si la formule est vraie pour un polygone P , alors elle l’est
pour le polygone P 0 = P ∪ T auquel on a joint un triangle.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 15 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Remarque

Les polygones à sommets entiers, c’est-à-dire dont les sommets

sont des points d’un réseau, jouent un rôle important en
géométrie discrète, notamment dans la définition de la convexité
discrète.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 16 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Plan

1 Un théorème de Minkowski

2 Convexité discrète et linéarité discrète

3 Droite discrète et algorithmes

4 Droites discrètes et arithmétique

T. Roussillon Géométrie discrète, M2 IGI, 2014. 17 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Convexité
Soit un sous-ensemble R de points de Λ.

Constat
Les définitions euclidiennes de convexité sont inadaptées.
C’est un problème de définition auquel il est possible de
répondre de différentes manières. Plus d’une dizaine de
définitions existent.
T. Roussillon Géométrie discrète, M2 IGI, 2014. 18 / 52
Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Proposition de définition

Par demi-plans (≈ H-convexité)

Un sous-ensemble R de points de Λ est H-convexe ssi il existe
un ensemble de demi-plans Hi = Hi ∩ Λ dont l’intersection ne
contient que R, ie. R = ∩{Hi }.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 19 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Proposition de définition

Par demi-plans (≈ H-convexité)

Un sous-ensemble R de points de Λ est H-convexe ssi il existe
un ensemble de demi-plans Hi = Hi ∩ Λ dont l’intersection ne
contient que R, ie. R = ∩{Hi }.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 19 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Remarque

Définition analytique
Tout sous-ensemble convexe de Λ peut être défini
analytiquement, c’est-à-dire par un ensemble d’inégalités.
Répartissons l’ensemble des demi-plans en deux groupes de
même orientation. Notons Ni (resp. Nj ) la normale du demi-plan
Hi (resp. Hj ) orienté vers le haut (resp. vers le bas) et ci (resp.
cj ) leur ordonnée à l’origine.


R = {x ∈ Λ|x ∈ (∩i Ni .x ≤ ci ) ∩ (∩j Nj .x ≥ cj ) }.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 20 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Définition équivalente

Par triangles (T-convexité)

Un sous-ensemble R de points de Λ est T-convexe ssi tous les
triangles xyz, tels que x, y, z ∈ R, ne contiennent que des points
de R.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 21 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Définition équivalente

Par triangles (T-convexité)

Un sous-ensemble R de points de Λ est T-convexe ssi tous les
triangles xyz, tels que x, y, z ∈ R, ne contiennent que des points
de R.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 21 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Définition équivalente

Par triangles (T-convexité)

Un sous-ensemble R de points de Λ est T-convexe ssi tous les
triangles xyz, tels que x, y, z ∈ R, ne contiennent que des points
de R.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 21 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Des sous-ensembles convexes particuliers

Définition d’une droite discrète

L’intersection non nulle de deux demi-plans H − = H− ∩ Λ et
H + = H+ ∩ Λ portés par des droites de même pente et
d’orientation opposée est une droite discrète.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 22 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Des sous-ensembles convexes particuliers

Définition d’une droite discrète

L’intersection non nulle de deux demi-plans H − = H− ∩ Λ et
H + = H+ ∩ Λ portés par des droites de même pente et
d’orientation opposée est une droite discrète.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 22 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Des sous-ensembles convexes particuliers

Définition d’une droite discrète

L’intersection non nulle de deux demi-plans H − = H− ∩ Λ et
H + = H+ ∩ Λ portés par des droites de même pente et
d’orientation opposée est une droite discrète.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 22 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Définition analytique

Droite discrète analytique

Un ensemble R de points de Z2 est une droite discrète ssi tous
les points x ∈ Z2 vérifient :

c1 ≤ N.x ≤ c2

où N est la normale des deux demi-plan H− et H+ , c1 et c2 (avec

c1 < c2 ) sont leur ordonnée à l’origine respective.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 23 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Plan

1 Un théorème de Minkowski

2 Convexité discrète et linéarité discrète

3 Droite discrète et algorithmes

4 Droites discrètes et arithmétique

T. Roussillon Géométrie discrète, M2 IGI, 2014. 24 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Définition arithmétique
Droite discrète arithmétique
Un ensemble R de points de Z2 appartient à la droite discrète
arithmétique de pente ab , de borne inférieure µ et d’épaisseur ω
(avec a, b, µ et ω dans Z, b 6= 0 et pgcd(a, b) = 1), ssi tous les
points (x, y) de R vérifient :

0 ≤ ax − by + µ < ω

Cette droite se note D(a, b, µ, ω).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 25 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Périodicité

La droite discrète D(a, b, µ, ω) est invariante par la translation

k.(b, a), k ∈ Z.
En effet, la translation des points est donnée par :

a(x + kb) − b(y + ka) = ax − kab − by + kba

= ax − by

Donc :
0 ≤ a(x + kb) − b(y + ka) − µ < ω

T. Roussillon Géométrie discrète, M2 IGI, 2014. 26 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Etude du cas naïf

Supposons que 0 ≤ a ≤ b (pente entre 0 et 1).

Supposons de plus que ω = b (épaisseur de 1).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 27 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Fonctionnalité
En divisant 0 ≤ ax − by + µ < ω par b, puis en déplaçant les
termes, on obtient :
a µ ω a µ
x+ − <y ≤ x+ .
b b b b b
ω
Comme b = 1, pour chaque abscisse x = x0 , il existe une et une
seule ordonnée y = y0 telle que (x0 , y0 ) ∈ D(a, b, µ, b).
On dit que D(a, b, µ, b) est fonctionnelle en x.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 28 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Discrétisation par défaut

La discrétisation par défaut de la droite d’équation
ax − by + µ = 0, c’est-à-dire l’ensemble des points tel que
 
ax + µ
y= ,
b
qui n’est rien d’autre que l’ensemble des points tel que
ax + µ ax + µ
−1<y ≤ ,
b b
coïncide avec la droite discrète D(a, b, µ, b).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 29 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Discrétisation par défaut et reste

En chaque point (x, y), on a y = b ax+µ
b c.
Si on note r le reste de la division de ax + µ par b, on a :
ax + µ r
=y+ ,
b b
ce qui est équivalent à
r = ax − by + µ.
Comme on peut considérer sans perte de généralité la translation
qui rend µ nul, on appelle aussi reste la quantité ax − by.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 30 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Points consécutifs

Considérons un point (x0 , y0 ) ∈ D(a, b, µ, b) :

r0 = ax0 − by0 + µ, 0 ≤ r0 < b.

Avec le point (x1 , y1 ) ∈ D(a, b, µ, b), suivant (x0 , y0 ), c’est-à-dire

tel que x1 = x0 + 1 (et y1 = y0 + k), on a :

ax1 − by1 + µ = ax0 − by0 + µ + a − bk = r0 + a − bk.

Comme (x1 , y1 ) ∈ D(a, b, µ, b), 0 ≤ r0 + a − bk < b.

Par conséquent,
soit k = 0 (si r0 + a < b),
soit k = 1 (si r0 + a > b, car r0 + a < 2b puisqu’on suppose
que 0 ≤ a ≤ b).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 31 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Représentation par code d’une droite discrète

chain code, crack code, Freeman chain...

0
1
0 0
1
0
1
0 0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 32 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Tracé du code d’un motif de D(a, b, µ, b) (0 < a ≤ b)

a, b et µ les paramètres de la droite

r le reste initialisé à µ
n = 0 la longueur du code
while n ≤ b do
while r + a < b et n ≤ b do
afficher 0
n=n+1
r =r+a
end while
afficher 1
r =r+a−b
n=n+1
end while

T. Roussillon Géométrie discrète, M2 IGI, 2014. 33 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Problème de la reconnaissance

A partir d’un point (x0 , y0 ) appartenant à une droite discrète D

dont les paramètres a, b et µ sont connus, on peut visiter, dans
l’ordre croissant des abscisses, les points suivants (xi , yi ) ∈ D
tels que xi > x0 .

Peut-on résoudre le problème inverse : c’est-à-dire trouver les

paramètres a, b et µ d’une droite discrète dont est issu une suite
de points (xi , yi ) donnée dans l’ordre croissant des abscisses ?

T. Roussillon Géométrie discrète, M2 IGI, 2014. 34 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Reconnaissance d’un segment de droite discrète

Segment de droite discrète

Une suite de points (xi , yi ) est un segment de la droite
D(a, b, µ, b) (0 < a ≤ b) ssi l’ensemble des points de la suite
vérifient :
µ ≤ axi − byi < µ + b.

Points d’appui d’un segment

Soit S un segment de la droite D(a, b, µ, b) d’au moins b points.
On note U et U 0 (resp. L et L0 ) les points de S de reste µ (resp.
µ + b − 1) d’abscisse minimale et maximale. Ils sont appelés
points d’appui supérieurs (resp. inférieurs).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 35 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Reconnaissance d’un segment de droite discrète

Théorème
Étant donné l’ajout d’un point M (x, y) de reste
r = ax − by à droite d’un segment déjà reconnu
S, on a :
si µ ≤ r < µ + b alors M appartient à la
droite D et donc S ∪ M est un segment U’ U’

discret L’ U L’
U

si r > µ + b ou r < µ − 1 alors S ∪ M L

(a)
L
(b)

n’est pas un segment de droite discrète

U’
si r = µ − 1 (uni-modularité) alors M est
L’ U’
faiblement extérieur à la droite discrète D U

et donc S ∪ M est un segment de droite L

U
L’

discrète dont la pente minimale est (c)

L
(d)
−−→
donnée par le vecteur U M
si r = µ + b (uni-modularité) alors M est
faiblement extérieur à D et donc S ∪ M
est un segment de droite discrète dont la
−−→
pente minimale est donnée par LM

T. Roussillon Géométrie discrète, M2 IGI, 2014. 36 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

M (x, y) et M 0 (x0 , y 0 ) sont les deux premiers points de S

a = y 0 , b = 1 et µ = 0
U = L = (0, 0), U 0 = L0 = (1, y 0 )
SEGMENT=Vrai
while S n’a pas été complètement parcouru et SEGMENT do
M (x, y) = point suivant dans S
r = ax − by
if r < µ − 1 ou r > µ + b then
SEGMENT=Faux
else
if r = µ − 1 ou r = µ + b then
if r = µ − 1 then
L = L0 , U 0 = M
a = y − yU
b = x − xU
µ = ax − by
end if
if r = µ + b then
U = U 0 , L0 = M
a = y − yL
b = x − xL
µ = ax − by − b + 1
end if
else
if r = µ then
U0 = M
else if r = µ + b − 1 then
L0 = M
end if
end if
end if
end while
⇒ algorithme incrémental en O(n)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 37 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

S r Cases a b µ U U0 L L0
− Initialization 0 1 0 (0,0) (1,0) (0,0) (1,0)

-1 r =µ−1 1 2 0 (0,0) (2,1) (1,0) (1,0)

1 r =µ+b−1 1 2 -1 (0,0) (2,1) (1,0) (3,1)

2 r =µ+b 1 3 -1 (2,1) (2,1) (1,0) (4,1)

-1 r=µ 1 3 -1 (2,1) (5,2) (1,0) (4,1)

-3 r <µ−1 − − − − − − −

− S is not a DSS − − − − − − −

T. Roussillon Géométrie discrète, M2 IGI, 2014. 38 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Interprétation d’un reste égal à µ − 1 (resp. µ + b)

Supposons sans perte de généralité que µ = 0 (resp.
µ + b − 1 = 0).
Si le reste r = ax − by vaut ±1, c’est-à-dire si l’aire A du
parallélogramme engendré par les vecteurs (b, a) et (x, y)
vaut ±1, alors ce parallélogramme, comme tout
parallélogramme engendré par les vecteurs k(b, a), k ∈ Z2 et
(x, y), ne contient aucun point de Z2 autre que ses sommets
(Minkowski).
Inversement, si l’aire est strictement supérieure à 1, un point
de Z2 n’appartenant pas à S est inclu dans ces
parallélogrammes, ce qui signifie que S n’est pas T-convexe.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 39 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point faiblement extérieur (de reste µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point faiblement extérieur (de reste µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point faiblement extérieur (de reste µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point fortement extérieur (de reste < µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point fortement extérieur (de reste < µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Idée de la preuve

Cas d’un point fortement extérieur (de reste < µ − 1)

T. Roussillon Géométrie discrète, M2 IGI, 2014. 40 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Plan

1 Un théorème de Minkowski

2 Convexité discrète et linéarité discrète

3 Droite discrète et algorithmes

4 Droites discrètes et arithmétique

T. Roussillon Géométrie discrète, M2 IGI, 2014. 41 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Série de Farey
La série de Farey Fm d’ordre m est la suite croissante de fractions
irréductibles comprises entre 0 et 1 dont le dénominateur est inférieur
ou égal à m.
Ex :  
0 1 1 1 2 1 3 2 3 4 1
F5 = , , , , , , , , , ,
1 5 4 3 5 2 5 3 4 5 1

00 0
si hk , hk00 et hk0 sont trois termes successifs de Fm (avec
h h00 h0 h00 h+h0 h00
k < k00 < k0 ), alors k00 = k+k0 . La fraction k00 est appelée médian
h h0
de k et k0 .

Fm+1 est calculée à partir de Fm en ajoutant les médians de

dénominateurs ≤ m de fractions successives de Fm

T. Roussillon Géométrie discrète, M2 IGI, 2014. 42 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Propriété cruciale
0 h0
Si hk et hk0 sont deux termes successifs de Fm (avec h
k < k0 ),
alors kh0 − hk 0 = 1 (Minkowski).
F1

T. Roussillon Géométrie discrète, M2 IGI, 2014. 43 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Propriété cruciale
0 h0
Si hk et hk0 sont deux termes successifs de Fm (avec h
k < k0 ),
alors kh0 − hk 0 = 1 (Minkowski).
F2

T. Roussillon Géométrie discrète, M2 IGI, 2014. 43 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Propriété cruciale
0 h0
Si hk et hk0 sont deux termes successifs de Fm (avec h
k < k0 ),
alors kh0 − hk 0 = 1 (Minkowski).
F3

T. Roussillon Géométrie discrète, M2 IGI, 2014. 43 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Propriété cruciale
0 h0
Si hk et hk0 sont deux termes successifs de Fm (avec h
k < k0 ),
alors kh0 − hk 0 = 1 (Minkowski).
F4

T. Roussillon Géométrie discrète, M2 IGI, 2014. 43 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Séries de Farey

Propriété cruciale
0 h0
Si hk et hk0 sont deux termes successifs de Fm (avec h
k < k0 ),
alors kh0 − hk 0 = 1 (Minkowski).
F5

T. Roussillon Géométrie discrète, M2 IGI, 2014. 43 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Arbre de Stern-Brocot

C’est l’arbre binaire de recherche associé à une série de Farey.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 44 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Interprétation géométrique
Version additive
h
Soit M , un motif de D de pente k
h0
Soit M 0 , un motif de D0 de pente k0
avec kh0 − hk 0 = 1 (uni-modularité)
h+h0
=⇒ M.M 0 est un motif de la droite discrète de pente k+k0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 45 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Interprétation géométrique
Version additive
h
Soit M , un motif de D de pente k
h0
Soit M 0 , un motif de D0 de pente k0
avec kh0 − hk 0 = 1 (uni-modularité)
h+h0
=⇒ M.M 0 est un motif de la droite discrète de pente k+k0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 45 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Interprétation géométrique
Version additive
h
Soit M , un motif de D de pente k
h0
Soit M 0 , un motif de D0 de pente k0
avec kh0 − hk 0 = 1 (uni-modularité)
h+h0
=⇒ M.M 0 est un motif de la droite discrète de pente k+k0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 45 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire
Version multiplicative
Soit M , un motif de D0 de pente h
k
0
Soit M 0 , un motif de D0 de pente hk0
avec kh0 − hk 0 = 1 (uni-modularité)
h+uh0
=⇒ [Link] 0 est un motif de la droite discrète de pente k+uk0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 46 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire
Version multiplicative
Soit M , un motif de D0 de pente h
k
0
Soit M 0 , un motif de D0 de pente hk0
avec kh0 − hk 0 = 1 (uni-modularité)
h+uh0
=⇒ [Link] 0 est un motif de la droite discrète de pente k+uk0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 46 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire
Version multiplicative
Soit M , un motif de D0 de pente h
k
0
Soit M 0 , un motif de D0 de pente hk0
avec kh0 − hk 0 = 1 (uni-modularité)
h+uh0
=⇒ [Link] 0 est un motif de la droite discrète de pente k+uk0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 46 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Corollaire
Version multiplicative
Soit M , un motif de D0 de pente h
k
0
Soit M 0 , un motif de D0 de pente hk0
avec kh0 − hk 0 = 1 (uni-modularité)
h+uh0
=⇒ [Link] 0 est un motif de la droite discrète de pente k+uk0 .

T. Roussillon Géométrie discrète, M2 IGI, 2014. 46 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Un théorème de Klein

Soit L(a, b) une droite d’équation {(α, β) ∈ R2 |aβ − bα = 0} avec

a, b ∈ Z, gcd(a, b) = 1. L sépare le plan discret en
un domaine supérieur, Λ+ (en blanc),
un domaine inférieur, Λ− (en noir).

L
Λ+

Λ−

T. Roussillon Géométrie discrète, M2 IGI, 2014. 47 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une suite bien connue

r(x, y) := ax − by, reste de (x, y) ∈ Z2 par rapport à L(a, b)

v−1 = (0, 1), v0 = (1, 0),

j |r(v )| k
k−2
∀k ≥ 1, r(vk−1 ) 6= 0, vk = vk−2 + vk−1 .
|r(vk−1 )|

v4

v3
v−1 v1
v2
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 48 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Un résultat bien connu

Théorème de Klein
Les points entiers impairs (resp. pairs) vk sont les sommets de
l’enveloppe convexe de Λ+ (resp. Λ− ).

v4
Λ+
v3
v−1 v1
v2
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 49 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

L
Λ+

v−1
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

Λ+

v−1
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

Λ+

v−1 v1
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

Λ+

v−1 v1
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

Λ+

v−1 v1
v2
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une interprétation géométrique

La division entière entre restes est vue comme un lancé de rayon

(exercice : montrer pourquoi).

v4
+
Λ
v3
v−1 v1
v2
Λ−
v0

T. Roussillon Géométrie discrète, M2 IGI, 2014. 50 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Une autre interprétation géométrique

Exercice : montrer que

∀0 ≤ k ≤ n, r(vk )vk−1 + r(vk−1 )vk = (b, a).

T. Roussillon Géométrie discrète, M2 IGI, 2014. 51 / 52

Un théorème de Minkowski Convexité discrète et linéarité discrète Droite discrète et algorithmes Droites discrètes et arithmétique

Bibliographie

[HW78] G. H. Hardy, E. M. Wright.

An Introduction to the Theory of Numbers,
Oxford science publications, 1978 (5eme edition).
[R89] C. Ronse.
A bibliography on digital and computational convexity.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(2) :181–190,
1989.
[E00] U. Eckhardt.
Digital Lines and Digital Convexity.
Digital and Image Geometry, Advanced Lectures, 209–228, 2000.
[R91] J-P. Reveillès.
Géométrie discrète, calculs en nombres entiers et algorithmique.
Thèse d’état, 1991.
[DR95] I. Debled.
Etude et reconnaissance de droite et de plan discret.
Thèse, 1995.

T. Roussillon Géométrie discrète, M2 IGI, 2014. 52 / 52