View
6
Download
1
Category
Preview:
Citation preview
Algorithmes sous-linéaires pourpolygones convexes
Antoine Vigneron
antoine.vigneron@jouy.inra.fr
Departement mathematiques et informatique appliquees
INRA Jouy-en-Josas
Algorithmes sous-lineaires pour polygones convexes – p.1/41
Introduction
Algorithmes sous-lineaires pour polygones convexes – p.2/41
Références
Travail en collaboration avec Hee-Kap Ahn, PeterBrass, Otfried Cheong, Hyeon-Suk Na, Cheong-DaePark, Chan-Su Shin.
Références:Inscribing an axially symmetric polygon and otherapproximation algorithms for planar convex sets.[pdf]Maximizing the overlap of two planar convex setsunder rigid motion. [pdf, anglais]
Algorithmes sous-lineaires pour polygones convexes – p.3/41
Références
Travail en collaboration avec Hee-Kap Ahn, PeterBrass, Otfried Cheong, Hyeon-Suk Na, Cheong-DaePark, Chan-Su Shin.
Références:Inscribing an axially symmetric polygon and otherapproximation algorithms for planar convex sets.[pdf]Maximizing the overlap of two planar convex setsunder rigid motion. [pdf, anglais]
Algorithmes sous-lineaires pour polygones convexes – p.3/41
Plan
Introduction
Calcul exact du diamètre
Algorithmes sous-linéaires
Approximation du diamètre
Généralisation
Algorithmes sous-lineaires pour polygones convexes – p.4/41
Calcul exact du diamètre
Algorithmes sous-lineaires pour polygones convexes – p.5/41
Observation
m′
Pm
P est contenu dans les deux disques de rayon d(m, m′)de centres m et m′.
Algorithmes sous-lineaires pour polygones convexes – p.6/41
Observation
``′
Pm
m′
P est situé entre deux droite parallèles contenant m etm′. On dit que {m, m′} est une paire antipodale.
Algorithmes sous-lineaires pour polygones convexes – p.7/41
Calcul des paires antipodales
`
`′
Algorithmes sous-lineaires pour polygones convexes – p.8/41
Calcul des paires antipodales
`′
`
Algorithmes sous-lineaires pour polygones convexes – p.9/41
Calcul des paires antipodales
Algorithmes sous-lineaires pour polygones convexes – p.10/41
Calcul des paires antipodales
Algorithmes sous-lineaires pour polygones convexes – p.11/41
Finding the antipodal pairs
Algorithmes sous-lineaires pour polygones convexes – p.12/41
Calcul du diamètre
Calcul des paires antipodales en temps O(n)
On peut donc calculer le diamètre en temps O(n).
On peut calculer de la même façon la largeur et lerectangle couvrant minimum.
largeurP
Algorithmes sous-lineaires pour polygones convexes – p.13/41
Calcul du diamètre
Calcul des paires antipodales en temps O(n)
On peut donc calculer le diamètre en temps O(n).
On peut calculer de la même façon la largeur et lerectangle couvrant minimum.
largeurP
Algorithmes sous-lineaires pour polygones convexes – p.13/41
Calcul du diamètre
Calcul des paires antipodales en temps O(n)
On peut donc calculer le diamètre en temps O(n).
On peut calculer de la même façon la largeur et lerectangle couvrant minimum.
largeurP
Algorithmes sous-lineaires pour polygones convexes – p.13/41
Algorithmes sous-linéaires
Algorithmes sous-lineaires pour polygones convexes – p.14/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Entrée: direction ~d, tableau ordonné des sommetsp1, p2 . . . pn d’un polygone convexe P .
Sortie: sommet pi qui maximise ~d.−−→Opi.
Algorithmes sous-lineaires pour polygones convexes – p.15/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Entrée: direction ~d, tableau ordonné des sommetsp1, p2 . . . pn d’un polygone convexe P .
Sortie: sommet pi qui maximise ~d.−−→Opi.
Algorithmes sous-lineaires pour polygones convexes – p.15/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.
−−→p1p2.~d > 0 et −−→p5p6.~d > 0
=⇒ la solution est entre p5 et p10.
Algorithmes sous-lineaires pour polygones convexes – p.16/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.−−→p1p2.~d > 0 et −−→p5p6.~d > 0
=⇒ la solution est entre p5 et p10.
Algorithmes sous-lineaires pour polygones convexes – p.16/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.−−→p1p2.~d > 0 et −−→p5p6.~d > 0
=⇒ la solution est entre p5 et p10.Algorithmes sous-lineaires pour polygones convexes – p.16/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.
−−→p5p6.~d > 0 et −−→p7p8.~d 6 0
=⇒ la solution est entre p5 et p8.
Algorithmes sous-lineaires pour polygones convexes – p.17/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.−−→p5p6.~d > 0 et −−→p7p8.~d 6 0
=⇒ la solution est entre p5 et p8.
Algorithmes sous-lineaires pour polygones convexes – p.17/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
Calcul en temps O(log n) par dichotomie.−−→p5p6.~d > 0 et −−→p7p8.~d 6 0
=⇒ la solution est entre p5 et p8.Algorithmes sous-lineaires pour polygones convexes – p.17/41
Calcul des points extrêmes
~d
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10
−−→p5p6.~d > 0 et −−→p6p7.~d 6 0
=⇒ renvoie p6
Algorithmes sous-lineaires pour polygones convexes – p.18/41
Intersection avec une droite
p7
p6 p5
p4
p3
p2
p1
p8
p9
p10 p11
`
P ∩ `
Le segment ` ∩ P peut être calculé en temps O(log n).
Algorithmes sous-lineaires pour polygones convexes – p.19/41
Autres problèmes
En revanche, les problèmes suivants on pourcomplexité Θ(n):
AireDiamètrePérimètreLargeurDisque (ou rectangle) couvrant minimal
Approximation en temps sous-linéaire?Facteur constant en temps O(log n)
Facteur (1 − ε) en temps O
(
log n√ε
)
Algorithmes sous-lineaires pour polygones convexes – p.20/41
Autres problèmes
En revanche, les problèmes suivants on pourcomplexité Θ(n):
AireDiamètrePérimètreLargeurDisque (ou rectangle) couvrant minimal
Approximation en temps sous-linéaire?
Facteur constant en temps O(log n)
Facteur (1 − ε) en temps O
(
log n√ε
)
Algorithmes sous-lineaires pour polygones convexes – p.20/41
Autres problèmes
En revanche, les problèmes suivants on pourcomplexité Θ(n):
AireDiamètrePérimètreLargeurDisque (ou rectangle) couvrant minimal
Approximation en temps sous-linéaire?Facteur constant en temps O(log n)
Facteur (1 − ε) en temps O
(
log n√ε
)
Algorithmes sous-lineaires pour polygones convexes – p.20/41
Coresets
Objet P
Algorithme Ac
Objet Pc
Approximation de P (coreset)
Algorithme A
Algorithme A
f(P ) 6 f(Pc) 6 cf(P )
f(P )
f(Pc)
Souvent: algorithmes A et Ac connus.
Reste à trouver un coreset Pc plus simple que P , etprouver que f(P ) 6 f(Pc) 6 cf(P ).
Algorithmes sous-lineaires pour polygones convexes – p.21/41
Coresets
Objet P
Algorithme Ac
Objet Pc
Approximation de P (coreset)
Algorithme A
Algorithme A
f(P ) 6 f(Pc) 6 cf(P )
f(P )
f(Pc)
Souvent: algorithmes A et Ac connus.
Reste à trouver un coreset Pc plus simple que P , etprouver que f(P ) 6 f(Pc) 6 cf(P ).
Algorithmes sous-lineaires pour polygones convexes – p.21/41
Approximation du diamètre
Algorithmes sous-lineaires pour polygones convexes – p.22/41
Facteur√
2
Coreset Pc
Objet P
diam(P )
diam(Pc)
c =√
2 diam(P ) 6 diam(Pc) 6√
2 diam(P ).
Pc peut être calculé en temps O(log n): calcul de 4points extrêmes.
coreset de taille O(1).
Algorithmes sous-lineaires pour polygones convexes – p.23/41
Facteur√
2
Coreset Pc
Objet P
diam(P )
diam(Pc)
c =√
2 diam(P ) 6 diam(Pc) 6√
2 diam(P ).
Pc peut être calculé en temps O(log n): calcul de 4points extrêmes.
coreset de taille O(1).
Algorithmes sous-lineaires pour polygones convexes – p.23/41
Facteur√
2
Coreset Pc
Objet P
diam(P )
diam(Pc)
c =√
2 diam(P ) 6 diam(Pc) 6√
2 diam(P ).
Pc peut être calculé en temps O(log n): calcul de 4points extrêmes.
coreset de taille O(1). Algorithmes sous-lineaires pour polygones convexes – p.23/41
Distance
Soient P ⊂ Q ⊂ R2
On définit la distance (de Hausdorff) entre P et Q
dh(P, Q) = maxx∈Q
(
miny∈P
d(x, y)
)
.
P
dh(P, Q)
Q
Algorithmes sous-lineaires pour polygones convexes – p.24/41
Schéma d’approximation
Objet P
L
`
dh(Pε, P ) 6 εL/2 6 ε diam(P )/2
(1 − ε) diam(P ) 6 diam(Pε) 6 diam(P )
Temps de calcul: O
(
log n
ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.25/41
Schéma d’approximation
Objet P
L
`
εL/2
dh(Pε, P ) 6 εL/2 6 ε diam(P )/2
(1 − ε) diam(P ) 6 diam(Pε) 6 diam(P )
Temps de calcul: O
(
log n
ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.25/41
Schéma d’approximation
Objet P
Coreset Pε
L
`
εL/2
dh(Pε, P ) 6 εL/2 6 ε diam(P )/2
(1 − ε) diam(P ) 6 diam(Pε) 6 diam(P )
Temps de calcul: O
(
log n
ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.25/41
Schéma d’approximation
Objet P
Coreset Pε
L
`
εL/2
dh(Pε, P ) 6 εL/2 6 ε diam(P )/2
(1 − ε) diam(P ) 6 diam(Pε) 6 diam(P )
Temps de calcul: O
(
log n
ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.25/41
Schéma d’approximation
Objet P
Coreset Pε
L
`
εL/2
dh(Pε, P ) 6 εL/2 6 ε diam(P )/2
(1 − ε) diam(P ) 6 diam(Pε) 6 diam(P )
Temps de calcul: O
(
log n
ε
)
. Algorithmes sous-lineaires pour polygones convexes – p.25/41
Méthode de Dudley
La méthode de Dudley permet de construire uncoreset pour le diamètre de plus petite taille: c’est unpolygon à O(1/
√ε) faces.
Il peut (facilement) être calculé en temps O
(
log n√ε
)
.
On peut donc calculer une (1 − ε)-approximation du
diamètre en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.26/41
Méthode de Dudley
La méthode de Dudley permet de construire uncoreset pour le diamètre de plus petite taille: c’est unpolygon à O(1/
√ε) faces.
Il peut (facilement) être calculé en temps O
(
log n√ε
)
.
On peut donc calculer une (1 − ε)-approximation du
diamètre en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.26/41
Méthode de Dudley
La méthode de Dudley permet de construire uncoreset pour le diamètre de plus petite taille: c’est unpolygon à O(1/
√ε) faces.
Il peut (facilement) être calculé en temps O
(
log n√ε
)
.
On peut donc calculer une (1 − ε)-approximation du
diamètre en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.26/41
Méthode de Dudley
δ
δδ
δ
δδ
δ
Points verts: δ =√
ε diam(P ).
Il y a O(1/√
ε) points verts.
Algorithmes sous-lineaires pour polygones convexes – p.27/41
Méthode de Dudley
δ′
δ′
δ′
δ′
Points rouges: δ′ = 0.9√
ε.
Il y a O(1/√
ε) points rouges
Algorithmes sous-lineaires pour polygones convexes – p.28/41
Méthode de Dudley
PPε
6 δ′
6 δ
6 δδ′/2
Pε est l’enveloppe convexe des points verts et despoints rouges.
dh(Pε, P ) 6 δ tan(δ′)/2 < ε diam(P )/2 pour ε suffisamentpetit.
Algorithmes sous-lineaires pour polygones convexes – p.29/41
Méthode de Dudley
diam(Pε) > (1 − ε)diam(P )
On peut calculer Pε en temps O
(
log n√ε
)
:
1. Calcul d’une√
2-approximation de diam(P ) entemps O(log n).
2. Calcul de Pε en temps O
(
log n√ε
)
.
Conclusion: on peut calculer une (1 − ε)-approximation
de diam(P ) en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.30/41
Méthode de Dudley
diam(Pε) > (1 − ε)diam(P )
On peut calculer Pε en temps O
(
log n√ε
)
:
1. Calcul d’une√
2-approximation de diam(P ) entemps O(log n).
2. Calcul de Pε en temps O
(
log n√ε
)
.
Conclusion: on peut calculer une (1 − ε)-approximation
de diam(P ) en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.30/41
Méthode de Dudley
diam(Pε) > (1 − ε)diam(P )
On peut calculer Pε en temps O
(
log n√ε
)
:
1. Calcul d’une√
2-approximation de diam(P ) entemps O(log n).
2. Calcul de Pε en temps O
(
log n√ε
)
.
Conclusion: on peut calculer une (1 − ε)-approximation
de diam(P ) en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.30/41
Généralisation
Algorithmes sous-lineaires pour polygones convexes – p.31/41
Autres problèmes
La méthode de Dudley permet aussi d’approximer:Le périmètreLe disque couvrant minimal
mais pasL’aireLa largeurLe rectangle couvrant minimal
On va présenter une modification de la méthode deDudley qui permet de traiter ces problèmes.
Algorithmes sous-lineaires pour polygones convexes – p.32/41
Autres problèmes
La méthode de Dudley permet aussi d’approximer:Le périmètreLe disque couvrant minimal
mais pasL’aireLa largeurLe rectangle couvrant minimal
On va présenter une modification de la méthode deDudley qui permet de traiter ces problèmes.
Algorithmes sous-lineaires pour polygones convexes – p.32/41
Autres problèmes
La méthode de Dudley permet aussi d’approximer:Le périmètreLe disque couvrant minimal
mais pasL’aireLa largeurLe rectangle couvrant minimal
On va présenter une modification de la méthode deDudley qui permet de traiter ces problèmes.
Algorithmes sous-lineaires pour polygones convexes – p.32/41
Largeur directionnelle
`(P, ~u)
P
~u
Largeur directionnelle:
`(P, ~u) = maxx∈P
(−→Ox.~u
)
− minx∈P
(−→Ox.~u
)
Algorithmes sous-lineaires pour polygones convexes – p.33/41
Largeur directionnelle
~u
Pε
On veut trouver Pε ⊂ P tel que
∀~u ∈ R2, ` (Pε, ~u) > (1 − ε) ` (P, ~u) .
Algorithmes sous-lineaires pour polygones convexes – p.34/41
Élargissement
R
Pa
b
d(a, b) > diam(P )/√
2.
Algorithmes sous-lineaires pour polygones convexes – p.35/41
Élargissement
Rba
C
P
d(a, b) > diam(P )/√
2 > longueur(R)/√
2
Algorithmes sous-lineaires pour polygones convexes – p.36/41
Élargissement
ba
C
P ′c
On applique une affinité orthogonale pour transformerR en un carré C.
d(a, b) > c/√
2 > diam(P ′)/2
Algorithmes sous-lineaires pour polygones convexes – p.37/41
Élargissement
C ′
C
c
P ′
a b
P ′ contient un carré C ′ de côté au moins c/4.
=⇒ ∀~u, `(P′, ~u) >
c
4>
1
4√
2diam(P ′)
Algorithmes sous-lineaires pour polygones convexes – p.38/41
Élargissement
P ′
ε′
C
On applique la méthode de Dudley avec ε′ = ε/4√
2.
∀~u, `(P′
ε′ , ~u) > `(P′, ~u) − ε
4√
2diam(P ′) > (1 − ε) `(P
′, ~u).
Algorithmes sous-lineaires pour polygones convexes – p.39/41
Élargissement
Pε
R
On applique l’inverse de l’affinité précédente, et onobtient Pε.
On conclut que ∀~u ∈ R2, `(Pε, ~u) > (1 − ε) `(P, ~u).
Algorithmes sous-lineaires pour polygones convexes – p.40/41
Applications
On peut calculer Pε en temps O
(
log n√ε
)
.
C’est un coreset pour les problèmes suivantsLe périmètreLe disque couvrant minimumL’aireLa largeurLe rectangle couvrant minimum
Conclusion: il existe un algorithme d’approximation
pour ces problèmes en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.41/41
Applications
On peut calculer Pε en temps O
(
log n√ε
)
.
C’est un coreset pour les problèmes suivantsLe périmètreLe disque couvrant minimumL’aireLa largeurLe rectangle couvrant minimum
Conclusion: il existe un algorithme d’approximation
pour ces problèmes en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.41/41
Applications
On peut calculer Pε en temps O
(
log n√ε
)
.
C’est un coreset pour les problèmes suivantsLe périmètreLe disque couvrant minimumL’aireLa largeurLe rectangle couvrant minimum
Conclusion: il existe un algorithme d’approximation
pour ces problèmes en temps O
(
log n√ε
)
.
Algorithmes sous-lineaires pour polygones convexes – p.41/41
Recommended