[PDF] Calculer une enveloppe convexe - webusersimj-prgfr PDF convex.pdf

Préparation à l'agrégation — option Calcul formel Antoine L'enveloppe convexe d'une partie A de Rn sera notée conv(A) ; c'est la plus petite partie convexe de Rn On peut décrire de manière imagée comment énumérer toutes ces paires : on est solution du problème posé (avec poids tous égaux à 1 ; dans le cas de

30 oct 2015 · liser le minimum de poids pour une fatigue maximum déterminée, GÉNÉRALITÉS Lorsqu'une enveloppe cylindrique, de section non cir-

[PDF] guide pratique - BPost

1 jan 2012 · Le poids Le nombre minimal de timbres-poste à acheter pour pouvoir bénéficier du prix le moins cher varie selon le type de timbre-poste

[PDF] Un algorithme linéaire pour le calcul de lenveloppe externe dun

entier à l'extérieur de F Pour calculer l'enveloppe convexe d'une figure est effectuée en ne testant que le bit de poids le plus faible d'une seule des Montrons à présent comment notre algorithme peut être utilisé pour calculer linéaire-

[PDF] Calculer une enveloppe convexe - webusersimj-prgfr

[PDF] D:\My Files\Cours\A - Syllabus\Syllabus RM\RMChap3(Traction)wpd

Calcul d'un assemblage avec boulons haute résistance (HR) Enveloppe mince La contrainte à la base du mur, sous son seul poids propre, vaut : σ =

[PDF] Sélever, prendre de la hauteur

Nous avons fait les calculs pour savoir combien ferait la taille de la montgolfière Le poids de l'air contenu dans l'enveloppe qui est dirigé vers le bas Calculs Nous sommes actuellement en train de comprendre comment une aile d'avion

[PDF] Appareil à pression suivant le CODAP - Eduscol

6 Calcul d'une enveloppe cylindrique soumise à pression intérieure construit n 'importe comment, ou par n'importe qui Il en est pour preuve les actions mécaniques exercées sur l'élément : pression, poids des accessoires, efforts exercés

[PDF] Combien me coûte lenvoi dune lettre ou dun colis? Offres et - Orlee

1 jan 2017 · Il vous suffit d'indiquer l'adresse, de fermer l'enveloppe et votre courrier est prêt à être Poids: 30 kg Format: 60 × 60 × 100 cm Colis standard max 30 kg 60 cm 60 cm 100 cm poste ch/calculer-les-prix Calculer les prix

[PDF] Guide des tarifs – uPs Canada

cALcUL DES TARiFS D'ExPÉDiTion ET D'iMPoRTATion Comment déterminer le poids facturable d'un envoi cALcUL DU PoiDS FAcTURAbLE service de livraison fiable pour vos envois ou enveloppes de routine, UPS Standard est une

[PDF] Informations utiles sur vos tarifs et envois - FedEx

1 jan 2018 · Comment calculer les frais relatifs à votre envoi Déterminez le poids total de votre envoi pour trouver le tarif dans la colonne appropriée suivants: US$ 100 ou US$ 9 07 par livre pour une FedEx® Envelope ou un

Calculer une enveloppe convexe

Préparation à l"agrégation - option Calcul formel Antoine Chambert-Loir (version revue par Michel Coste)1. Introduction SoitAune partie du plan; de nombreux problèmes géométriques requièrent de dé- terminer l"enveloppe convexe deA, de manière aussi efficace que possible. Ce texte se veut une introduction au sujet; il est pour l"essentiel issu du livre de Preparata et Shamos,Computational geometry, an introduction(Springer-Verlag, 1985).

Quelques définitions pour commencer.

L"enveloppe convexe d"une partieAdeRnsera notée conv(A); c"est la plus petite deRnqui contiennentA(Hahn-Banach). SoitCune partie convexe deRn; la dimension deCest par définition la dimension du plus petit sous-espace affineEdeRnqui contientC. De plus,Cest d"intérieur non vide dansE. SoitCune partie convexe deRn. Un pointx?Cest dit extrémal s"il n"existe pas de couple (y,z) de points deCtel quex?]y,z[. Soit?une forme linéaire surRnqui est positive ou nulle surC. L"intersection deCavec l"hyperplan d"équation?=0 est une partie convexe deRndont les points extrémaux sont des points extrémaux deC. Cela permet de démontrer un théorème de Choquet qui affirme qu"une partie convexe compacte deRnest l"enveloppe convexe de ses points extrémaux. Un polytopePest l"enveloppe convexe d"un ensemble finiAde points deRn; c"est une partie compacte deRn. Ses points extrémaux sont appeléssommets; ils appar- tiennent àA. Une faceFdePest une partie non videFdePqui est l"intersection deP avec un demi-espace fermé dont l"intérieur est disjoint deP. C"est une partie convexe. Unsimplexeest l"enveloppe convexe den+1 points deRnqui ne sont pas situés dans un même hyperplan affine. Supposons que dim(P)=n. Pour chaque faceFde dimensionn-1 (facette), soit Fune équation de l"hyperplan?F?qui est positive surP. Alors,Pest l"intersection des demi-espaces?F?0. Inversement, soitPune partie compacte deRn, intersection d"un nombre fini de demi-espaces. On peut démontrer quePest un polytope. Déterminer l"enveloppe convexe d"un ensemble finiAde points deRnsignifiera donc en déterminer les sommets et les faces.

2ANTOINE CHAMBERT-LOIR (VERSION REVUE PAR MICHEL COSTE)

2. Déterminer les sommets de l"enveloppe convexe

SoitAune partie finie deRnet soitCson enveloppe convexe. On supposera à l"oc- casion queCest de dimensionn. Voici un moyen simple, mais pas très efficace, de déterminer les sommets deA. En effet, un pointx?Aest un sommet de conv(A) s"il n"existe pasn+1 points a

0,...,an?A\{x} tels quexappartienne au simplexe conv(a0,...,an). (Démontrer ceci

en utilisant le théorème de Carathéodory.) De plus, cette condition est assez facile à tester, par exemple en résolvant le système linéairex=?n i=0λiai,?n i=0λi=1, enn+1 variablesλ0,...,λn. Dans le cas où lesai sont affinement indépendants, le pointxappartient à leur enveloppe convexe si et seulement si tous lesλisont positifs. Quelle est la complexité de cet algorithme? Supposons queAaitNéléments. Il faut parcourir, pour chaque élémentxdeA, les?N-1 n+1?parties deA\{x}, résoudre le sys- tème linéaire et éliminer le pointxsi ce n"est pas un sommet. C"est donc en gros un algorithme en O(Nn+2).

3. Enveloppe convexe d"une étoile (Graham scan)

Une étoile (centrée en l"origineO) est un polygonea1...aNdu planR2tels que les angles ( ?Ox,Oai) pris dans [0,2π[ forment une suite croissante (à permutation circu- laire desaiprès). Dans la suite de ce paragraphe, on définiraampourm?Zcomme a r, oùrest l"unique entier de {1,...,N} tel quem≡r(modN). Un polygone convexe a

1...aNest une étoile centrée en chacun de ses points intérieurs.

SoitAun ensemble fini du plan; soitOun point de l"intérieur de l"enveloppe convexe deA, par exemple l"isobarycentre des points deA. Quitte à trier les angles ( ?Ox,Oa), poura?A, (voire leurs tangentesya/xa), on peut supposer que A={a1,...,aN}, oùa1...aNest une étoile centrée enO. Notons que l"enveloppe convexe deAest celle de la réunion des trianglesOaiai+1, pour 1?i?N. Alors, l"enveloppe convexe deApeut être déterminée grâce au résultat suivant :si l"angle ai-1aiai+1est saillant, aiappartient au triangle Oai-1ai+1, donc a in"est pas un sommetet l"enveloppe convexe deAest celle deA\{ai}. La méthode consiste à parcourir la listea1,...,aNen partant dei=1. Ensuite, on tente d"enlever a i: si l"angleai-1aiai+1est rentrant, on passe au point suivant; sinon, on enlèveai de la liste et on fait un pas en arrière en revenant au pointai-1. Pour programmer convenablement l"algorithme, il convient de supposer quea1est un sommet; on peut par exemple prendre le point le plus à gauche. La complexité de cet algorithme est linéaire en le nombreNde points, une fois qu"il

est ordonné de sorte à former une étoile. Le tri des angles a quant à lui une complexité

en O(N2) avec un algorithme idiot, ou en O(NlogN) avec un algorithme optimal. Variante.SoitAun ensemble fini du plan; soitCson enveloppe convexe. Soita un point d"abscisse minimale etbun point d"abscisse maximale, choisis d"ordonnée maximale si nécessaire. Ce sont des sommets deC. On trie les points au-dessous de

CALCULER UNE ENVELOPPE CONVEXE3Oa1

a2a3 a4a5 a6a7FIGURE1. Détermination de l"enveloppe convexe d"une étoile (ab) par abscisses croissantes (en gardant le point d"ordonnée maximale si plusieurs tement que la pente de (aiai+1) n"est pas supérieure à celle de (ai-1ai). On détermine ainsi aisément les sommets deCau-dessous de (ab), ordonnés de sorte à former un polygone convexeaai1...aikb. On fait de même avec la partie supérieure. Remarque.Le lien entre le problème de l"enveloppe convexe et celui du tri est bien mis en évidence par cet algorithme, au moins dans un sens : trier permet de calculer l"enveloppe convexe. Inversement, soitx1,...,xnune suite de nombres réels. SoitA l"ensemble des points de coordonnées (xi,x2 i). Quelle est l"enveloppe convexe deA? En déduire que si l"on sait calculer efficacement une enveloppe convexe, on sait trier tout aussi efficacement une suite de nombres réels.

4. Diviser pour régner

Soit encoreAune partie finie du plan et soitCson enveloppe convexe. Un algo- rithme de calcul deCde type "diviser pour régner» se décrirait de la façon suivante : - On décomposeAen deux sous-ensemblesA1etA2qui en forment une partition et on en calcule les enveloppes convexes,C1etC2, de manière récursive; - On calcule l"enveloppe convexe deC1?C2. Les subtilités de l"algorithme proviennent ainsi de deux points : - Trouver une partition efficace. En pratique on choisit les deux partiesA1etA2 approximativement de même cardinal; - Calculer de manière efficace l"enveloppe convexe de la réunion de deux convexes.

4ANTOINE CHAMBERT-LOIR (VERSION REVUE PAR MICHEL COSTE)

Concentrons-nous sur ce dernier aspect. En pratique, déterminer une enveloppe convexeCsignifie avoir calculé unpolygone convexe Pdont l"intérieur estC. En particulier, les sommets deP(donc deC) sont ordonnés de sorte à former une étoile. L"algorithme récursif fournit ainsi des polygonesP1etP2dont les intérieurs sont les enveloppes convexesC1etC2deA1etA2. SoitOun point intérieur àP1; par exemple son centre de gravité. Le pointOsera intérieur àC, mais on doit distinguer deux cas, suivant queOappartient àC2ou pas. Pour décider dans quel cas on se trouve, il faut regarder les angles ( ?Ox,Oa), poura parcourant les sommets deP2dans le sens trigonométrique. (1) S"ils forment une suite croissante (modulo 2π),le point O appartient à C2.On peut alors ordonner la réunion des sommets deP1et deP2de sorte à obtenir une étoileEcentrée enO. Ceci se fait avec une complexité linéaire en le nombre de points (fusion de deux listes triées). L"enveloppe convexe de l"étoileEest égale àC. (2) Sinon,cesanglessontcomprisentredeuxvaleursdifférantd"auplusπetlepoly- goneP sommets deP2tels queP2soit contenu dans le secteur angulaire?aOb. Soit alorsE l"étoile obtenue en parcourant, dans le sens trigonométrique, les sommets deP2entre aetbpuis ceux deP1dans le secteur complémentaire. Son enveloppe convexe estC. Une fois obtenue une étoile, on calcule son enveloppe convexe par la méthode du pa- ragraphe précédent. Une fois obtenusP1etP2, le polygonePest obtenu avec une complexité O(N) pour la fusion des listes et O(N) pour le calcul de l"enveloppe convexe d"une étoile. La com- plexitéT(N) vérifie ainsi l"inégalité

T(N)?2T(N/2)+O(N),

dont la solution estT(N)?O(NlogN).

5. Deux applications

Calcul du diamètre d"une partie du plan.- SoitAune partie finie du plan. Suppo- sons qu"on doive déterminer lediamètredeAet, plus précisément, deux pointsaetb deAdont la distance est maximale. L"approche naïve consiste à parcourir toutes les en O(N2), siNest le nombre de points. Toutefois, la partieAa même diamètre que son enveloppe convexe (le démontrer...). Supposons cette dernière calculée, ce qu"on peut faire en O(NlogN). Le nombrende sommets de l"enveloppe convexe deAest bien sûr majoré parN, et en général beau- coup plus petit. Alors le diamètre du polygone convexe est égal à la distance maximale entre sommets antipodaux. Le nombre total de paires de sommets antipodaux ne peut pas excéder

CALCULER UNE ENVELOPPE CONVEXE5

3n/2. On peut décrire de manière imagée comment énumérer toutes ces paires : on

trouve une première paire de points antipodaux en "posant le polygone sur une droite (en tournant toujours dans le même sens) en "faisant rouler le polygone» sur la droite horizontale. On peut obtenir de la sorte un algorithme déterminant le diamètre du polygone convexe en O(n). De la sorte, on obtient un algorithme en O(NlogN) qui calcule le diamètre d"une partie finie du plan. pouri?{1,...,n}. L"objectif est de déterminer une nouvelle suite (x? i) croissante (au sens large) pour laquelle l"expression?n i=1(xi-x? i)2soit minimale (moindres carrés). Dans certains cas, on peut avoir des poidswi>0 pouri=1,...,net chercher à mini- miser?n i=1wi(xi-x? i)2, toujours avec la condition de croissance sur lesx? i. Ce problème équivaut à la recherche d"une " enveloppe convexe inférieure » telle qu"on l"a expliquée dans la variante duGraham scan. Posonss0=0 etsi=? j?ixj pour 1?i?n. Soit alorsC?l"" enveloppe convexe inférieure » de l"ensembleAdes points de coordonnées (i,si), pour 0?i?n. SoitA??Al"ensemble des sommets deC. La fonction continue affine par morceauxs?qui vautsienisi (i,si) appartient àA?est convexe; Sisest la fonction continue affine par morceaux qui vautsieni pour touti,s?est la plus petite fonction convexe, affine par morceaux et continue qui soit inférieure ou égale às. Pouri=1,...,n, soitx? i=s?(i)-s?(i-1) (c"est la pente du graphe des?sur l"intervalle numéroide l"axe des abscisses). On peut démontrer que la suite (x? i) est solution du problème posé (avec poids tous égaux à 1; dans le cas de poidswiquelconques, il faut remplacer lesnintervalles de longueur 1 sur l"axe des abscisses par des intervalles de longueurswi, et lesx? isont les pentes au-dessus de chacun des intervalles de la fonction convexe affine par morceauxs?). Du point de vue pratique, on peut résoudre le problème de régression monotone avec poids 1 en bouclant la transformation suivante sur les vecteurs (x1,...,xn) deRn: endroit où la condition de croissance est violée se situe entre les paquetsxi=xi+1= ...=xi+p-1etxi+p=xi+p+1=...=xi+p+q-1, on remplace les deux paquets par un seul où toutes les coordonnées valent pxi+qxi+pp+q(cet algorithme est connu sous le nom de PAVA, pour Pool Adjacent Violators Algorithm).quotesdbs_dbs7.pdfusesText_13

[PDF] [PDF] Calculer une enveloppe convexe - webusersimj-prgfr

MÉTHODE GÉNÉRALE DE CALCUL DES ENVELOPPES