Minkowski sum

I geometri er Minkowski- summen en operation på delene af et vektorrum . Med to dele A og B det associerede deres sum sæt , dannet af summerne af et element af A og af et element af B  :

.

Summen af ​​to kompakter er kompakt. Det er således muligt at begrænse operationen til dette sæt, som kan forsynes med en såkaldt Hausdorff- afstand . Minkowski-summen er derefter en kontinuerlig operation. Derudover respekterer den den konvekse , det vil sige, at summen af ​​to konvekse stadig er konveks. Målingen af ​​summen af ​​to konvekse linjer tilfredsstiller en påslag, kaldet Brunn-Minkowski ulighed .

Minkowskis sum er involveret i mange områder af ren og anvendt matematik. Dette værktøj er grundlaget for adskillige beviser for isoperimetriske sætninger , der sigter mod at bestemme den del af rummet med den størst mulige lydstyrke, idet begrænsningen er givet for målene for dets grænse. I euklidisk geometri finder vi kugler med dimension n . Minkowski-summen bruges også til at tælle antallet af ansigter på en polyhedron , til at løse flisespørgsmål eller til at studere geometrien af ​​konvekse. De anvendes for eksempel i krystallografi af grunde til flisebelægning af plads, i økonomi for at optimere de mulige produktioner i en gruppe virksomheder eller for at studere blandinger.

Indledning

Eksempler

Sættet A til venstre er en trekant, hvis toppunktkoordinater er (0, -1), (0,1) og (1,0). Til højre er illustreret en lignende trekant B , orienteret forskelligt. Koordinaterne er (0,0), (1, -1) og (1,1). Hvis sæt A og B er to tripletter, finder vi:

A + B = {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), ( 1, 0), (1, −2)}.

Hvis A og B er trekanterne vist med rødt, er der en sekskant vist i figuren nederst til højre.

Generelt er summen af ​​to polygoner stadig en polygon. Denne egenskab gælder for en polyhedron af enhver dimension.

Vi kan bemærke analogien mellem Minkowski-summen og sammenløbsproduktet . På en billedlig måde kan vi få overfladen af ​​summen A + B af to sæt ved at dække B med maling og ved at få overfladen A til at løbe gennem midten . Af denne grund er det Minkowski sum undertiden kaldes foldning af A og B .

Det er klart, at summen af ​​et sæt A og en singleton { b } svarer til oversættelsen af A med vektoren b .

Det er næppe mere komplekst at indse, at summen af ​​to firkanter stadig er en firkant. Mere generelt, hvis C er en konveks , symmetrisk med hensyn til oprindelsen, er summen C + C lig med den konvekse 2 C , her angiver 2 C homøtheten af forholdet 2. Beviset er lidt mere subtilt, det er analogt til det foreløbige lemma, der blev brugt i beviset for Minkowskis sætning . For at realisere dette kan vi bemærke, at ethvert element i 2C er et element i C + C , omvendt lad u + v være et element i C + C , det er også skrevet som det dobbelte af 1/2 ( u + v ), eller dette element er i C .

Vi kan nævne et sidste eksempel, som vi finder i artiklen isoperimetrisk sætning . Lad C være en konveks kompakt af et euklidisk plan og P en konveks polygon, hvis hjørner alle er på grænsen til C, og hvis største kant har en længde øget med ε. Så summen af P og centrum af disken og nulvektor radius ε indeholder konvekse kompakt C . Denne egenskab er et trin i at fastslå, at der ikke er noget overfladeareal større end disken med den samme omkreds.

Første egenskaber

Denne operation er kommutativ , associativ , har for neutral element den ugifte {0}. Det er også distribuerende med hensyn til mødet

.

Fra et topologisk synspunkt

Bemærk  : Summen af ​​to lukkede dele er ikke nødvendigvis lukket: for eksempel ved at tage linjen af ​​abscissas i planet og hyperbolen xy = 1, danner deres sum det private plan for en linje. Imidlertid er summen af ​​en lukket og en kompakt lukket.

Steiner-Minkowski formel

Dimension 2

Steiners formel blev opdaget for at bevise den isoperimetriske sætning . I dimension 2 angiver det, at hvis C er en overflade med perimeter p , så er dens areal mindre end arealet af disken med perimeter p . Hvis omkredsen p ikke er endelig, som for en kompakt bygget ved hjælp af en Koch-kurve , forbliver formlen nøjagtig, men har ikke længere nogen interesse. Teoremet har følgende form:

,

ligestillingen opnås kun i det tilfælde, hvor compact C er en disk.

For at demonstrere dette, en fremgangsmåde består i at studere det område, som Minkowski sum af en kompakt konveks C og tB , hvor t betegner et positivt reelt tal og B den enhed disk . Følgende ligestilling findes, hvis μ er volumenfunktionen til C kombinerer sit areal, og C er et konveks sæt:

.

Volumenfunktionen μ er defineret på en meget generel måde, den svarer til Lebesgue-målingen , som til et kvadrat af side 1 associerer 1. En kurves perimeter er defineret på samme måde som Jordan , det vil sige at den er lig til den øvre grænse for længderne af polygonale linjer, der tilnærmer grænsen. I denne form svarer bevis for det isoperimetriske sætning til, at det kvadratiske polynom , som forbinder μ ( C + tB ) med t , har en positiv diskriminant , eller at polynomet indrømmer en reel rod.

Denne formel gør det også muligt at få et udtryk for omkredsen p - altid hvis C er konveks - som en funktion af φ:

.

Enhver dimension

Det er fristende at generalisere formlen i et euklidisk rum E med dimension n . Vi kan betragte mål for volumen sC 1 + tC 2 , hvor C 1 og C 2 er to konvekse sammentrykker og s og t to positive reals. Vi opnår et polynomisk udtryk af typen:

.

Koefficienterne V k er kaldes blandede mængder af C 1 og C 2 .

Vi har nogle åbenlyse ligheder:

.

En anden er en smule mere vanskeligt at påvise i det tilfælde, hvor C 2 er lig med B  :

.

Her betegner n –1 ( n - 1) -dimensionalt volumen. Definition af et ( n - 1) -dimensionelt mål bliver subtilt. En første metode består i at generalisere den teknik, der anvendes i dimension 1, til en ensrettet bue . Det skal tilpasses og er specifikt for konvekse. Foranstaltningen af området er derefter den øverste grænse for de polyedriske konvekse flader inkluderet i C 1 . Konveksitet er afgørende, ellers viser modeksemplet til højre, at definitionen ikke giver mening. Overfladen, som vi vil måle, er en cylinder, den anvendte polyhedron er en lanterne, hvis hjørner er placeret på sekskanter hver gang modregnet af en tolvtedel af en omgang. Hvis sekskanterne kommer tættere og tættere op, øges polyhedronens overflade til uendelig. En anden teknik består i at bruge en differentiel form og mere præcist en volumenform . Vanskeligheden ligger så i, at overfladen af ​​en konveks ikke har nogen grund til at være en klasse C 1 manifold . Det bliver nødvendigt at bruge rum, der kan sammenlignes med Sobolevs for at definere overfladen.

Blandede volumener verificerer et mærke, der bruges til at demonstrere den isoperimetriske ulighed for dimensioner større end 2. Det bærer navnet på ulighed Aleksandrov - Fenchel  :

. Demonstrationer

Her betegner E et euklidisk rum med dimension n .

Angiv med M denne foranstaltning. M er summen af ​​målingen μ ( sP ) og skorpen tilføjet med summen af tB . Udtrykket associeret med målingen af ​​μ ( sP ) er en konstant ganget med s n .

På hver flade, finder vi en hyperkubus H i 1 med dimension n , med basen ansigtet pågældende og højde t af dimension n - 1 og måling af produktet af en konstant og s n-1 . Hver af disse ansigter bidrager til volumen μ ( P + tB ) i form af et lineært udtryk i s n-1 . t .

Mellem disse hyperkuber finder vi mellemrum H j 2 , der har form af et prisme, af kanten, der skærer to flader og af dimension n - 2, hvis mål er produktet af en konstant med s n -2 og af siderne to flader af hyperkubusser H i 1 har en kant af en længde t , toppunktet af en forbindelse af produktet af en skive med radius t og en hyperkubus isomorf til kanten. Disse prismer er derfor dele af en cylinder med akse en hyperkube med dimension n - 2 og radius r . Hver af disse cylinderdele bidrager til volumen μ ( P + tB ) i form af et udtryk i s n-2 . t 2 .

Kanterne af dimension n - 2 har som ender hypercubes af dimension n - 3, som giver plads til mellemrum, der efterlades ledige af de faste stoffer H i 1 og H j 2 . Disse mellemrum H k 3 , fyldes ved primtal, af kanter skæringspunkterne mellem de foregående kanter, er af dimension n - 3 og måle produktet af en konstant og s n-3 . Disse præmier svarer til dele af produktet af en kugle med dimension 3 og af kanthyperkuber af dimension n - 3. Deres sum svarer til et udtryk i s n-3 . t 3 .

Vi fortsætter på denne måde op til dimension 1, krydset mellem kanterne er så dimension 0 og svarer til et punkt. Mellemrummet svarer til en del af en kugle, hvis udtryk er et produkt af en konstant ved t n .

Udtrykket i s n svarer til målingen af P , det i s n-1 . t til måling af overfladen af P . Hvis s er lig med 0, bemærker vi, at lydstyrken er den for en kugle med radius t , konstanten er den, der er forbundet med det n- dimensionelle volumen af en kugle.

Eller ( C p ) en faldende sekvens af konvekse Polyhedra hvis grænsen på betyder Hausdorff lig C . Det tætte sæt- afsnit i Hausdorffs Distance- artikel viser, at der findes en sådan sekvens. Lad P p ( s , t ) være det homogene polynom af grad n, som til ( s , t ) associerer μ ( sC p + tB ), målet er at vise, at sekvensen ( P p ) simpelthen konvergerer.

Sekvensen ( sC p + tB ) er en sekvens af kompakter, der falder for inklusion, den er nødvendigvis konvergent i betydningen Hausdorff, lad os vise, at grænsen er lig med sC + tB . Ethvert sæt af sekvensen indeholder sC + tB , så grænsen indeholder dette sæt. Omvendt, hvis y ikke er et element af sC + tB , eksisterer der et strengt positivt reelt tal ε, således at kuglen med centrum y og radius ε har et nulkryds med sC + tB, fordi dette sæt er lukket. Vi udleder, at ethvert element i sC n er i en afstand større end t + ε fra y . Hvis s ikke er nul, betyder det også, at der er en afstand på mere end ( t + ε) / r af C . Fra en bestemt N , som helst værdi af p er større end N , C p er i en afstand fra y strengt større end t / s , og sC p + tB kan ikke indeholde y . Hvis s er nul, er sekvensen sC p + tB konstant lig med tB og er trivielt konvergent.

Da sekvensen ( sC p + tB ) er en strengt faldende sekvens af kompakter, med grænsen sC + tB , og da funktionen μ er højere semikontinuerlig , er sekvensen μ ( sC p + tB ) konvergent (se afsnittet Funktioner fortsætter fra Hausdorffs Distance- artikel ) . Hvilket betyder nøjagtigt, at sekvensen ( P p ) simpelthen konvergerer.

Hver polynomium af sekvensen ( P p ) er en homogen polynomium af grad n , denne sekvens er en del af vektorrum af polynomier med to variabler af grad mindre end n og er af begrænset dimension . På dette rum er topologien for enkel konvergens kompatibel med addition og ekstern multiplikation, hvilket betyder, at disse to operationer er kontinuerlige. Imidlertid er der på et ægte vektorrum med en begrænset dimension kun en topologi, der er kompatibel med dets to operationer (jf. Topologi for et vektorrum med en begrænset dimension ) . Denne topologi er induceret af en hvilken som helst norm , for eksempel for ensartet konvergens på skiven med radius r , hvor r angiver et strengt positivt reelt tal. Vektorrum af polynomier med to homogene variabler af graden n er komplet til denne norm, som viser, at sekvensen ( P p ) konvergerer til en homogen polynomium P af graden n .

Denne grænse P er ved konstruktion den funktion, som ( s , t ) associerer μ ( sC + tB ), hvilket beviser forslaget.

Brunn-Minkowski ulighed

Demonstreret af Hermann Brunn og Hermann Minkowski i det tilfælde, hvor de to kompakter er konvekse, i almindelighed af Lazar Lyusternik  (en) , er Brunn-Minkowski-uligheden en reduktion af volumenet af summen af ​​to kompakte dele af et euklidisk rum :

Lad E et euklidisk rum af dimension n , μ den Lebesguemålet på E og A og B to kompakt ikke-tom E . Følgende ulighed er bekræftet:

. Demonstration

Rummet E er udstyret med en ortonormal base , derefter kvadreres den af ​​et gitter sammensat af hyperplaner, hvis retninger er retvinklede til en af ​​basisvektorerne. Disse hyperplaner er regelmæssigt fordelt med et trin på 1/2 p , hvor p er et strengt positivt heltal. Dette gitter banede rummet ved hjælp af små hyperkubber af kanter 1/2 p . Den valgte Lebesgue-foranstaltning er den, der forbinder en hyperterning af siden af ​​længde 1 med værdien 1.

Disse hyperkubber gør det muligt at tilnærme en kompakt. For eksempel i figuren til højre er en almindelig femkant tilnærmet med blå firkanter . At finjustere gitteret er at vælge en højere værdi for p . Figuren til højre illustrerer også en anden tilnærmelse med små røde firkanter opnået for et trin på 1 af værdien p . Artikel Afstand Hausdorff viser, at denne teknik kan konstruere en sekvens ( A n ) kompakt indeholdende A og tilnærme mere præcist A , i den forstand Hausdorff afstand.

Den her foreslåede demonstration finder sted i tre faser. For det første beviser vi det i det tilfælde, hvor A er en hyperterning af gitteret og B en hyperterning, der er inkluderet i en af ​​dem i gitteret, og hvis kanter er længde a = 1/2 p undtagen dem, der er parallelle med den første vektor af base, der er af længde λ. a . Her betegner λ et strengt positivt reelt tal mindre end 1.

Sagen er enkel nok til at muliggøre en effektiv beregning af de tre mål. At bevise den øvre grænse i dette tilfælde svarer til at vise, at funktionen f af i R , hvor R betegner sættet med reelle tal, er strengt positiv, på og nul i 1. Det er klart, at funktionen f er nul ved punkt 1, det er tilstrækkeligt at vise, at den strengt falder til at konkludere. Funktionen f er differentierbar på , det er tilstrækkeligt at vise, at dets derivat er strengt negativt, hvilket let kan verificeres.

Vi antager nu, at A og B er to endelige forbindelser af det indre af gitterhyperkubber eller dele af åbne hyperkubber, hvis koordinater er mellem 1/2 p . (Δ + λ) og 1/2 p . (Δ + 1). Det vil sige, at hyperkubberne er af typen af ​​det foregående forslag. Værdierne q og r betegne antallet af hyperkubusser hver komponent A og B .

Vi begrunder ved induktion på heltallet s lig med summen af q og r . Hvis s er lig med 2, er resultatet en direkte konsekvens af det foregående forslag. Vi antager, at resultatet er oprettet op til en værdi s 0, og vi antager, at summen af q og r er lig med s 0 + 1. Vi adskiller det euklidiske rum E i to forbundet med et af hyperplanene H A ortogonalt med l 'one af vektorerne på det ortonormale grundlag, der definerer gitteret. Der eksisterer et hyperplan af denne art, som dekomponerer A i to adskilte åbninger A 1 og A 2 , således at A 2 omfatter mindst én hyperkubus og sådanne, at A 1 er ikke den tomme mængde. A 1 og A 2 derpå sammensat af højst q - 1 hyperkubusser. Vi betegner med θ følgende strengt positive reelle tal: Vi separat B i to sæt B 1 og B 2 ved en hyperplan H B parallelt med den foregående, på en sådan måde, at: Hverken B 1 og B 2 indeholder vektorerne hyperplan H B derfor B indeholder, men er ikke nødvendigvis lig med foreningen af B 1 og B 2 , men som en delmængde indbefattet i en hyperplan er nul foranstaltning, den foregående lighed er verificeret. Denne gang, intet beviser, at B 1 og B 2 indeholder færre hyperkubusser end B , men det er sikkert, at de ikke indeholder mere. Egenskaberne for Minkowski-summen viser, at: Overveje vektoren ifølge ortonormalbasis vinkelret på to hyperplaner H A og H B , hvis koordinater på denne vektor af ethvert element af A 1 + B 1 er strengt mindre end dem af vektorerne A 2 + B 2 , som viser, at de to sæt er adskilt og: Som A 1 og A 2 indeholder strengt mindre end q små hyperkubusser og som B 1 og B 2 indeholder ikke mere end r , er det muligt at anvende induktion hypotese: Hvad vi stadig kan skrive: Dette viser markeringen, der afslutter demonstrationen:

Det er nu muligt at bevise Brunn-Minkowski-pålægget i det generelle tilfælde. Til dette anvendes en grænseovergang ved hjælp af Hausdorff-afstanden. Ε er et positivt reelt tal og A og B to kompakte E . Formålet med beviset er at vise, at summen af ​​målingen for A + B og af ε faktisk er det andet medlem af uligheden. Vi bruger tre egenskaber demonstreret i artiklen Hausdorff Distance .

Først bruger vi den øvre semikontinuitet af målefunktionen til Hausdorff-afstanden. Hvis E H angiver sættet af ikke-kompakte komprimeringer af E og d Hausdorff-afstanden: Udfordringen er nu at bygge den rigtige kombination C . Vi bruger eksistensen af ​​to kompakte sæt A ε og B ε strengt indeholdende A og B og sådan, at: De to sæt A ε og B ε er endelige forbindelser af lukkede hyperkubber i gitteret til en tilstrækkelig høj p- værdi . Eksistensen af ​​sådanne sæt kommer fra det faktum, at de endelige forbindelser af lukkede hyperkubber taget i gitteret danner et tæt sæt, hvis p beskriver de positive heltal. Beviset for kontinuiteten af ​​Minkowski-summen for Hausdorff-afstanden (se artiklen Hausdorff Distance ) viser, at: Vi vælger C lig med summen af A ε og B ε , hvilket viser at: Vi fjerner sit sæt A ε + B ε dets skæringspunkt med hyperplanerne i gitteret, som ikke ændrer dets måling. Vi er så i hypoteserne fra det foregående forslag og: Her betegner A oε og B oε sæt A ε og B ε fjernet fra deres kryds med gitterets hyperplaner. Tilføjelse af dette kryds ændrer på ingen måde målingerne, hvilket viser at: Ved antagelse, sættene En -e og B ε indeholde A og B . Deres måling er større, og: Denne stigning gælder for enhver strengt positiv værdi af ε, som viser det ønskede resultat.

Hvis de to kompakter A og B er konvekse og homotetiske, er der lighed.

Noter og referencer

  1. B. Teissier , Mængder af konvekse organer, geometri og algebra , Institute of Mathematics af Jussieu. Lektion givet torsdag den 7. oktober 1999, skrevet af C. Reydy, s.  8 .
  2. Dette eksempel er taget fra Marcel Berger og Bernard Gostiaux , Differentialgeometri: sorter, kurver og overflader [ detaljer i udgaver ] s.  226 .
  3. For detaljer, se (in) Herbert Federer , Geometric Measure Theory , Springer-Verlag 1969 ( ISBN  978-3-540-60656-7 ) , 3.2.37, 3.2.39, 3.2.26.
  4. (in) AD Alexandrov, Selected Works , CRC 2002 ( ISBN  2881249841 ) .
  5. (de) H. Brunn , Über Ovale und Eiflächen , München,1887 (afhandling).
  6. (fra) Hermann Minkowski , Geometrie der Zahlen , Leipzig, Teubner ,1896.
  7. (De) Lazar A. Lyusternik , “  Die Brunn - Minkowskische Ungleichnung für beliebige messbare Mengen  ” , CR Acad. Sci. USSR , vol.  8,1935, s.  55-58.
  8. Bernard Maurey , ”  Brunn-Minkowski-Lusternik ulighed og andre geometriske og funktionelle uligheder  ”, Séminaire Bourbaki , t.  46, 2003-2004, s.  95-114 ( læs online ).
  9. (i) Jiri Matousek , Lectures on Diskret Geometri [ detail udgaver ], s.  297 .
  10. Frank Barthe, "  Brunn-Minkowskis ulighed  ", om billeder af matematik ,2006.
  11. Det er direkte inspireret af en generalisering i dimension n af denne, i dimension 2: (en) A. Treibergs, Inequalities that Imply the Isoperimetric Inequality , University of Utah , s.  16 .
  12. Et bevis i dimension n er givet i: (en) RJ Gardner, "  Brunn-Minkowski ulighed  ", i Bull. (Ny serie) Amer. Matematik. Soc. , flyvning. 39, nr. 3, 2002, s.  363 .

(en) Bernard Dacorogna , Introduction to the Calculus of Variations , Imperial College Press , 2004 ( ISBN  1860945082 )

Se også

Relaterede artikler

Eksternt link

M. Rousset, Minkowski sum of triangles , speciale, Joseph Fourier University , 1996