Bemærkelsesværdige punkter og dele af grænsen til en konveks

Stående over for en konveks polyhedron med dimension 3, uanset om den er kendt som en terning eller mere kompliceret, ved vi spontant, hvordan man genkender de punkter, hvor den konvekse "peges", dens hjørner, og derefter opdeler de resterende punkter mellem punkterne i kanterne og ansigtspunkterne.

Denne artikel præsenterer nogle definitioner, der udvider disse begreber til generelle konvekse sæt , af enhver dimension, med muligvis buet kant. En af disse generaliseringer, begrebet vertex , svarer til den intuition, vi kan have af denne forestilling på en terning (punkterne i en kugle vil ikke være hjørner af kuglen, som den begrænser). De ekstreme punkter kan for deres del være flere, nok til at gøre det muligt at rekonstituere al den konvekse med deres konvekse kuvert, og dette selvom dens form er glat (således er alle punkterne på en kugles kant ekstreme).

Efter at have opregnet tre generaliseringer af en kubes hjørner præsenterer artiklen to varianter af toppunkt-kant-ansigt-hierarkiet, der falder sammen for konveks polyhedra.

De ekstreme punkter

Definition

Lad være en konveks og et punkt af . Vi siger, at er en extremal punkt af når er stadig konveks. $VS$ $vs.$ $VS$ $vs.$ $VS$ ${\ displaystyle C \ setminus \ {c \}}$

Sættet af ekstreme punkter i en lukket konveks lukkes muligvis ikke, selvom intuition kan være vildledende på grund af følgende resultat, der bliver falsk fra dimensionen : $3$

Proposition - Hvis er en lukket konveks af dimension , lukkes sættet med dens ekstreme punkter. $VS$ $2$

Minkowski og Kerin-Milman sætninger

Denne sætning på grund af Hermann Minkowski gør det muligt at rekonstituere al den konvekse fra dens eneste ekstreme punkter:

Teorem - Enhver kompakt konveks af et affinalt rum med begrænset dimension er den konvekse kuvert af sættet med dets slutpunkter.

Beviset er ikke meget langt, det væsentlige redskab er sætningen af eksistensen af et støttehyperplan på ethvert punkt af grænsen for en konveks.

Den kan generaliseres til bestemte rum med uendelig dimension under forudsætning af, at den lukkende operatør fint anvendes på den konvekse konvolut. Denne type udvidelse til funktionel analyse går tilbage til 1940 og er matematikernes Mark Kerins og David Milmans arbejde .

Sætning - Enhver kompakt konveks i et separat lokalt konveks rum er vedhæftningen af det konvekse skrog på alle dets slutpunkter.

En bestemt klasse af ekstreme punkter: de udsatte punkter

Lad være en konveks og et punkt af . Vi siger, at er en udsat punkt af , hvor der er en hyperplan af støtte for at kontrollere: . $VS$ $vs.$ $VS$ $vs.$ $VS$ $H$ $VS$ ${\ displaystyle H \ cap C = \ {c \}}$

Følgende udsagn er næsten åbenlyst, men dens omvendte er falsk fra dimension 2:

Proposition - Ethvert udsat punkt er ekstremt.

Faktisk, hvis det udsættes for , kan vi skrive til et af de åbne halvrum, der er afgrænset af , deraf konveksiteten af som skæringspunktet mellem konvekse. $vs.$ $VS$ ${\ displaystyle C \ setminus \ {c \} = C \ cap R}$ $R$ $H$ ${\ displaystyle C \ setminus \ {c \}}$

I mangel af en gensidig har vi imidlertid følgende oplysninger (dette er en sætning på grund af S. Straszewicz og dateres tilbage til 1935):

Sætning - I en lukket konveks i endelig dimension er ethvert ekstremt punkt grænse for udsatte punkter.

En særlig klasse af udsatte punkter: hjørner

I dette afsnit arbejder vi udelukkende i en begrænset dimension.

Definition og sammenligning med de udsatte punkter

Lad være en konveks og et punkt af . Vi siger, at det er et toppunkt på, hvornår det er på grænsen til, og skæringspunktet mellem de understøttende hyperplaner på det punkt er reduceret til . $VS$ $vs.$ $VS$ $vs.$ $VS$ $vs.$ $VS$ $VS$ $vs.$ $\ {vs \}$

Proposition - I en konveks (i en begrænset dimension) er ethvert toppunkt et eksponeret punkt.

Demonstration

Lad os betegne det konvekse, det betragtede toppunkt, det omgivende affine rum og dets dimension. Vi leverer en euklidisk struktur. $VS$ $vs.$ $E$ $d$ $E$

Bemærk den del, der er dannet af vektorer, der opfylder følgende betingelser: $S_ {c}$ $E$ $s$

{\ displaystyle \ forall x \ i C, <s | x> \ leq <s | c>}

Når s ikke er nul, fortolkes denne betingelse geometrisk: det betyder, at hyperplanet, der passerer gennem og vinkelret på , understøttes ved , hvor vektoren peger på den modsatte side af den konvekse. Skæringspunktet mellem de understøttende hyperplaner er derfor det sæt, hvor er vinkelret på alle elementerne i ; mere kortfattet er det . $vs.$ $s$ $vs.$ $s$ ${\ displaystyle c + u}$ $u$ $S_ {c}$ ${\ displaystyle c + S_ {c} ^ {\ perp}}$

At sige, at det er et toppunkt, er at sige, at dette kryds reduceres til , hvilket svarer til at sige, at det er reduceret til , eller at det vektorrum, der genereres af, er lig med ethvert heltal. Det er derfor muligt at vælge en -tuple af vektorer , hvori udgør en base af . $vs.$ $\ {vs \}$ ${\ displaystyle S_ {c} ^ {\ perp}}$ $\ {0 \}$ $S_ {c}$ $E$ $d$ ${\ displaystyle (s_ {1}, ..., s_ {d})}$ $S_ {c}$ $E$

Bemærk . Så for alt i : ${\ displaystyle v = s_ {1} + \ cdots + s_ {d}}$ $x$ $VS$

{\ displaystyle <v | x> = <s_ {1} | x> + \ cdots + <s_ {d} | x> \ leq <s_ {1} | c> + \ cdots + <s_ {d} | c > = <v | c>}

som allerede beviser, at det hyperplan, der passerer og er vinkelret på , understøttes i ; desuden, hvis det er et punkt i , er den foregående ulighed en lighed. Det er derfor nødvendigvis, at alle uligheder i sig selv er lighed ( ). Da det er et grundlag for , udleder vi det , hvilket beviser, at der ikke indeholder noget punkt i den konvekse uden for . $H$ $x$ $v$ $vs.$ $x$ ${\ displaystyle H \ cap C}$ ${\ displaystyle <s_ {i} | x> \ leq <s_ {i} | c>}$ ${\ displaystyle 1 \ leq i \ leq d}$ ${\ displaystyle (s_ {1}, ..., s_ {d})}$ $E$ ${\ displaystyle x = c}$ $H$ $vs.$

Sættet med hjørner kan højst tælles

Proposition - En konveks (i begrænset dimension) har et mest tællende sæt hjørner .

Demonstration

Vi tager igen notationerne, der blev introduceret i den foregående demonstration.

Bemærk først, at for alle strengt positive realer er vektoren inde, og at sættet af disse vektorer åbenbart er et åbent, hvorfra vi udleder, at det er indre ikke-frit. Det er derfor også tilfældet med dets oversatte . ${\ displaystyle \ alpha _ {1}, ..., \ alpha _ {d}}$ ${\ displaystyle \ alpha _ {1} s_ {1} + ... + \ alpha _ {d} s_ {d}}$ $S_ {c}$ $S_ {c}$ ${\ displaystyle c + S_ {c}}$

Overvej nu en vektor af ; lad os stille , med ind . For i , overvej dot-produktet (hvor den endelige ulighed kommer fra selve definitionen af ). $y$ ${\ displaystyle c + S_ {c}}$ ${\ displaystyle y = c + s}$ $s$ $S_ {c}$ $x$ $VS$ ${\ displaystyle <xc | yc> = <xc | s> = <s | x> - <s | c> \ leq 0}$ $S_ {c}$

I betragtning af den variationelle karakterisering af projektionen på en lukket konveks konkluderer vi, at det er projiceringen af på den lukkede konvekse . $vs.$ ${\ displaystyle p _ {\ overline {C}} (y)}$ $y$ ${\ displaystyle {\ overline {C}}}$

Lad os tage en tæt tællbar del af . For ethvert toppunkt i den konvekse, mødes (da denne er indvendig ikke-frit), mens den tager værdien på ethvert tidspunkt af : derfor tager begrænsningen af sig selv værdien . Dette kort defineret på et tællesæt, der tager ethvert toppunkt for værdi, vi konkluderer derefter, at sættet med hjørner højst kan tælles. $PÅ$ $E$ $vs.$ $PÅ$ ${\ displaystyle c + S_ {c}}$ ${\ displaystyle p _ {\ overline {C}}}$ $vs.$ ${\ displaystyle c + S_ {c}}$ ${\ displaystyle p _ {\ overline {C}}}$ $PÅ$ $vs.$

Kontekstualiseringer

Man vil være forsigtig med, at ordet "ansigt" ikke her har den betydning, det har i studiet af traditionelle polyedre i rummet af dimension 3, det for de plane elementer, der grænser op til dem. Her vil "ansigterne" kunne have alle dimensioner, inklusive 0 eller 1. Både hjørnerne, kanterne og de sædvanlige "ansigter" på en terning eller en tetraeder vil være ansigter i betydningen af de følgende definitioner.

Kontekstualisering af udsatte punkter: udsatte ansigter

Vi starter her med at udvide begrebet "eksponerede hjørner", selvom dette ikke er det mest nyttige, men fordi det er det nemmeste at definere og visualisere: vi kalder det eksponerede ansigt på en konveks ethvert sæt af formen , hvor er en understøttende hyperplan af . $VS$ ${\ displaystyle H \ cap C}$ $H$ $VS$

Følgende bemærkning er derfor tautologisk:

Bemærk - Et punkt på en konveks eksponeres, hvis og kun hvis det er et eksponeret ansigt af . $vs.$ $VS$ $\ {vs \}$ $VS$

De eksponerede ansigter dækker hele grænsen, da den passerer et understøttende hyperplan i det mindste ved hvert punkt deraf. $VS$

Kontekstualisering af de ekstreme punkter: ansigterne

Ligesom de eksponerede punkter er de eksponerede flader af dimension nul, er slutpunkterne ansigterne for dimension nul, hvor "ansigter" er defineret som følger:

En del af en konveks siges at være en flade af når er en ikke-tom konveks med følgende egenskab: hvis en åben segment trukket i mødes , så er hele lukket segment er inkluderet i . $F$ $VS$ $VS$ $F$ ${\ displaystyle] x, y [}$ $VS$ $F$ $[x, y]$ $F$

De to udsagn, der følger, har næsten øjeblikkelig verifikation, den anden bekræftes på samme måde som det blev verificeret, at de udsatte punkter var ekstreme:

Proposition - Et punkt i en konveks er ekstremt, hvis og kun hvis er et ansigt af . $vs.$ $VS$ $\ {vs \}$ $VS$

Proposition - De eksponerede ansigter er ansigter.

I betragtning af dette andet udsagn dækker ansigterne på (bortset fra ethvert heltal, der er den unikke ansigt med maksimal dimension) derfor hele grænsen til . $VS$ $VS$ $VS$

Det omvendte er ikke sandt (da der er ekstreme punkter, som ikke udsættes, giver de straks et eksempel på ansigter, der ikke er udsatte ansigter), dog med en undtagelse for ansigterne til codimension 1, som 'vi undertiden kalder facetter :

Proposition - Lad være konveks af begrænset dimension . Enhver dimension ansigt er eksponeret. $VS$ $d$ $VS$ ${\ displaystyle d-1}$

I modsætning til de eksponerede ansigter er ansigterne organiseret på en særlig behagelig hierarkisk måde som udtrykt ved de to følgende udsagn:

Proposition - Hvis er et ansigt af og et ansigt af , så er et ansigt af . $F$ $VS$ $F_1$ $F$ $F_1$ $VS$

Proposition - Hvis er en endelig-dimensionel konveks, danner det relative indre af ansigterne en skillevæg af det. $VS$ $VS$

Verifikation af sektionserklæringer

For det første forslag, enten ekstrem. Overvej et segment i container . Som det er konveks, er mindst en af dens ender ikke i dette sæt, derfor er lig med . Men et punkt inde i et segment kan kun svare til en ende, hvis segmentet derfor er en singleton . $vs.$ ${\ displaystyle] x, y [}$ $VS$ $vs.$ ${\ displaystyle C \ setminus \ {c \}}$ $vs.$ ${\ displaystyle x = y = c}$

For det andet forslag, det vil sige et udsat ansigt og et understøttende hyperplan med . Lad os nu være et åbent segment, der møder - og derfor H - mens det trækkes ind , og som kun er placeret på den ene side af : det er nødvendigvis, at dette segment er helt inde , derfor også dets ekstremiteter, som derfor virkelig er i . $F$ $H$ ${\ displaystyle F = H \ cap C}$ ${\ displaystyle] x, y [}$ ${\ displaystyle C \ setminus F}$ $VS$ $H$ $H$ $F$

For det tredje udsagn, det vil sige et ansigt af dimension , hyperplan affine kuverter affine af og et punkt af det relative indre af (det vil sige om dets indre i ). Bemærk , således at , og vis den gensidige inkludering; med denne hensigt tage . Derefter slutter segmentet ind, og fordi det er i det relative indre af det tilsvarende åbne segment indeholder punkter af . Den sidste ende af dette segment er derfor også i . Lad os derefter kontrollere, at det er et understøttende hyperplan. Hvis dette ikke var tilfældet, ville der være to punkter og af begge sider af (strengt). Segmentet ville så være et segment med ender, uden for hvilket interiøret, på det sted, hvor det krydser hinanden , mødes, hvilket vi ved er lig med . Dette er dog forbudt ved definitionen af et ansigt. Endelig skrev vi godt i form med et understøttende hyperplan, der beviste, at det er udsat. $F$ ${\ displaystyle d-1}$ $H$ $F$ $vs.$ $F$ $H$ ${\ displaystyle F '= H \ cap C}$ ${\ displaystyle F \ delmængde F '}$ ${\ displaystyle c '\ i F'}$ ${\ displaystyle [c, c ']}$ $VS$ $vs.$ $F$ $F$ ${\ displaystyle c '}$ $F$ $H$ $på$ $b$ $VS$ $H$ $[a, b]$ $F$ $H$ $F '$ $F$ $F$ ${\ displaystyle F = F '= H \ cap C}$ $H$

Lad os gå videre til det fjerde forslag. Lad et segment være åbent i mødet . A fortiori dette segment møder , hvilket er et ansigt , derfor er dets ender i . Da ansigterne per definition er konvekse, er hele segmentet inde . Vi har derefter et segment, hvor et punkt af interiøret mødes ; siden er et ansigt af dets to ender er i . ${\ displaystyle] x, y [}$ $VS$ $F_1$ $F$ $VS$ $F$ $[x, y]$ $F$ $F$ $F_1$ $F_1$ $F$ $F_1$

Der er stadig udsagnet om skillevæggen af ansigternes relative indre. Vi viser det ved induktion på dimensionen af den konvekse, idet initialiseringen er åbenbar (tilfældet med et punkt). Lad os således antage det sande for dimensionens konvekse dimensioner, der er strengt mindre end og være en konvekse af dimension . $k$ $VS$ $k$

Ikke-tomheden af ansigternes relative indre opstår fra den krævede tilstand for ikke-tomhed af ansigterne selv.

Hvad angår genforeningen af relative interiører, vær et punkt i . Hvis det er i det relative indre af , ved at bemærke, at det i sig selv er et ansigt, har vi udstillet et ansigt, hvis relative indre indeholder . Hvis det er på grænsen, skal det være et udsat ansigt, der indeholder . Ved induktionshypotesen hører det til det relative indre af et af ansigterne på , hvilket i sig selv ved den foregående udsagn er et ansigt af . $vs.$ $VS$ $vs.$ $VS$ $VS$ $vs.$ $vs.$ $F$ $vs.$ $vs.$ $F$ $VS$

Lad os endelig kontrollere, at to relative indre af ansigter enten er ens eller adskilt. Lad være og to ansigter, hvis relative indre mødes; betegne et punkt i deres skæringspunkt og deres respektive affine konvolutter. Vi vil først vise det ; da disse affine underrum begge passerer igennem , er det tilstrækkeligt at sikre, at de har samme retning. Lad være en vektor i retning af ; som det er i det relative indre af , forudsat at de to punkter tages små nok, og at de begge er i derfor , mens det åbne segment, der forbinder dem, passerer igennem, hvilket er ind . Som det er et ansigt, er enderne af dette segment også i og hører til retningen af . Ved at bytte roller og vi bevise lighed. Når dette trin er slut, ved at tage det samme argument som i det tredje forslag, kontrollerer vi det og det samme for . Dette beviser det, og så meget desto mindre, at de relative indvendige sider af disse to ansigter er ens. $F_1$ $F_2$ $VS$ $vs.$ $G_1$ $G_2$ ${\ displaystyle G_ {1} = G_ {2}}$ $vs.$ $u$ $G_1$ $vs.$ $F_1$ $\ alpha$ ${\ displaystyle c + \ alpha u}$ ${\ displaystyle c- \ alpha u}$ $F_1$ $VS$ $vs.$ $F_2$ $F_2$ $F_2$ $u$ $G_2$ $G_1$ $G_2$ ${\ displaystyle F_ {1} = G_ {1} \ cap C}$ $F_2$ ${\ displaystyle F_ {1} = F_ {2}}$

Kontekstualisering af hjørner: klassificering af kantpunkter efter deres rækkefølge

I en begrænset dimension har vi netop set, at der ved hvert punkt på grænsen kunne være forbundet med en slags "dimension", det af det unikke relative indre af ansigtet, som det hører til.

Der er en anden måde at fortsætte med at forbinde med hvert punkt af grænsen for en konveks dimension af et heltal mellem og , relateret til definitionen af "hjørner". ${\ displaystyle 0}$ ${\ displaystyle d-1}$

For konveks af endelig dimension og punkt af grænsen for . Vi kalder rækkefølgen af dimensionen af skæringspunktet mellem de understøttende hyperplaner ved ind . $VS$ $vs.$ $VS$ $vs.$ $VS$ $vs.$

Således er hjørnerne punkterne i nul rækkefølge.

Det meget enkle eksempel på en disk på planet viser, at denne opfattelse ikke overlapper den foregående: på cirklen, der grænser op til den, er alle punkter ekstreme, så hver enkelt singleton er i sig selv et ansigt: ved opdeling i ansigter, vi forbinder hele pointen med hvert punkt . På den anden side er der en unik supportlinje på hvert punkt, og rækkefølgen er derfor overalt lig med . ${\ displaystyle 0}$ $1$

Sagen med konveks polyhedra

De tre begreber, som denne artikel har lavet en parallel præsentation, falder sammen i det vigtige særlige tilfælde af konveks polyhedra (som vi vil definere som i artiklen Polytope som værende skæringspunkterne for et endeligt antal halvrum i et affinalt rum med dimension færdig ).

I denne særlige sag:

Proposition - I en konveks polyhedron,

hvert ansigt på grænsen er udsat

rækkefølgen af hvert punkt på grænsen er lig med dimensionen af det unikke relative indre af ansigtet, som det hører til.

Især er der identiteten af sættet af hjørner og for de ekstreme punkter. For en kompakt konveks polyhedron kan Minkowskis sætning derfor også angives som at sikre, at det er en konveks konvolut af sæt af hjørner.

Nogle andre oplysninger om opdeling i ansigter af en konveks polyhedron, som vi demonstrerer sammen med det foregående forslag, fortjenes at blive påpeget i denne hurtige oversigt. Husk at vi kalder facetter af en konveks af dimension dens dimensioner : $d$ ${\ displaystyle d-1}$

Proposition - I en konveks polyhedron , $VS$

facetterne er endelige i antal og dækker hele den relative grænse, de er selv konvekse polyedre;

ethvert ordentligt ansigt er i sig selv ansigtet til en facet af . $VS$ $VS$

En konsekvens er, at vi opnår alle de rette ansigter ved at overveje facetterne, så facetterne til facetterne osv. Ansigterne er derfor endelige i antal og især hjørnerne: enhver kompakt konveks polyhedron er derfor den konvekse kuvert af et endeligt antal punkter.

Referencer

Medmindre andet er angivet, kommer oplysningerne i denne artikel fra Fundamentals of konvex analysis af Jean-Baptiste Hiriart-Urruty og Claude Lemaréchal, coll. “Grundlehren Text Editions”, Springer, 2001 ( ISBN 978-3-540-42205-1 ) s. 41-45, 57 eller 246.

Marcel Berger , Geometry [ detalje af udgaver ] tjente som kilde til de sektioner, der er viet til hjørner (afsnit 11.6, bind 3, s. 50-52 i 1978-udgaven), til punktrækkefølgen (samme afsnit, s. 50) og til tilfældet med polyhedra konveks (afsnit 12.1 , s. 89-90).