Politop convex

Un politop convex este un caz particular al politopurilor, având în plus proprietatea de a fi o mulțime convexă din spațiul euclidian $n$ -dimensional $\mathbb {R} ^{n}$ . Multe lucrări^[1]^[2] folosesc termenul „politop” pentru politopul convex și mărginit, iar termenul de „poliedru” în sens mai general, posibil și pentru obiecte nemărginite. Alții^[3] (inclusiv acest articol) admit că politopurile pot fi nemărginite. În continuare termenii „politop convex mărginit/nemărginit”' se vor folosi dacă mărginirea este semnificativă în context. Alte lucrări identifică un politop convex cu frontiera sa.

Politopurile convexe joacă un rol important în diferite ramuri ale matematicii și în diferite domenii aplicative, în special în programarea liniară.

În importantele manuale ale lui Grünbaum^[1] și Ziegler^[2] cu privire la acest subiect, precum și în multe alte texte din geometria discretă, politopurile convexe sunt adesea numite pur și simplu „politopuri”. Grünbaum subliniază că acest lucru are ca scop exclusiv evitarea repetării nesfârșite a cuvântului „convex” și că în acele lucrări discuția trebuie înțeleasă ca aplicându-se numai politopurilor convexe.^[4]

Un politop este numit complet-dimensional dacă este un obiect $n$ -dimensional în $\mathbb {R} ^{n}$ .

Exemple

Multe exemple de politopuri convexe mărginite pot fi găsite în articolul poliedru.
În două dimensiuni, exemplele complet-dimensionale sunt semiplanul, o bandă între două drepte paralele, o formă unghiulară (intersecția a două semiplane neparalele), o formă definită de un lanț poligonal^⁠(d) convex cu două semidrepte atașate la capetele sale și un poligon convex.
Cazurile particulare ale unui politop convex nemărginit sunt o placă între două hiperplane paralele, o pană definită de două semiplane neparalele, un cilindru poliedric (prismă infinită) și un con poliedric (con infinit) definit de trei sau mai multe semispații care trec printr-un punct comun.

Definiții

Un politop convex poate fi definit în mai multe moduri, în funcție de ceea ce este mai potrivit pentru problema tratată. Definiția lui Grünbaum este în termenii unei mulțimi convexe de puncte în spațiu. Alte definiții importante sunt: drept intersecție a semispațiilor și drept anvelopa convexă a unei mulțimi de puncte (definire prin vârfurile politopului).

Definire prin vârfuri

În cartea sa, Convex Polytopes, Grünbaum definește un politop convex drept o mulțime convexă compactă cu un număr finit de puncte extreme:

O mulțime

K

din

\mathbb {R} ^{n}

este convexă dacă pentru orice pereche de puncte distincte

a

,

b

din

K

segmentul având capetele

a

și

b

este cuprins în

K

.

Acest lucru este echivalent cu definirea unui politop convex mărginit drept anvelopa convexă a unei mulțimi finite de puncte, care mulțime trebuie să conțină toate punctele extreme ale politopului. O astfel de definiție se numește definire prin vârfuri (definire V sau descriere V).^[1] Pentru un politop convex compact, descrierea minimă în V este unică și este dată de mulțimea vârfurilor politopului.^[1] Un politop convex se numește politop întreg dacă toate vârfurile sale au coordonate întregi.

Definire prin intersecția semispațiilor

Un politop convex poate fi definit ca o intersecție a unui număr finit de semispații. O astfel de definiție se numește definire prin semispații (definire H sau descriere H, de la engleză half-space).^[1] Există infinit de multe descrieri H ale unui politop convex. Totuși, pentru un politop convex complet-dimensional, descrierea H minimă este de fapt unică și este dată de mulțimea fațetelor care definesc semispațiile.^[1]

Un semispațiu închis poate fi exprimat ca o inegalitate liniară:^[1]

a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b

unde $n$ este dimensiunea spațiului care conține politopul respectiv. Prin urmare, un politop convex închis poate fi privit ca mulțimea de soluții a sistemului liniar de inegalități:

{\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}

unde $m$ este numărul semispațiilor care definesc politopul. Acesta poate fi scris în formă matricială:

Ax\leq b

unde $A$ este o matrice $m\times n$ , $x$ este un vector coloană $n\times 1$ ale cărui componente sunt variabilele $x_{1}$ … $x_{n}$ , iar $b$ este un vector coloană $m\times 1$ ale cărui componente sunt valorile inegalităților scalare $b_{1}$ … $b_{m}$ .

Un politop convex deschis este definit în același mod, cu inegalități stricte utilizate în formule în locul celor nestricte.

Coeficienții fiecărui rând al lui $A$ și $b$ corespund cu coeficienții inegalității liniare care definesc semispațiul respectiv. Prin urmare, fiecare rând din matrice corespunde cu un hiperplan de susținere al politopului, un hiperplan care mărginește un semispațiu care conține politopul. Dacă un hiperplan de susținere intersectează, de asemenea, politopul, acesta se numește hiperplan de frontieră (deoarece este un hiperplan de susținere, el poate intersecta politopul doar pe frontieră).

Definiția de mai sus presupune că politopul este complet-dimensional. În acest caz, există o mulțime minimă unică de inegalități definitorii (până la înmulțirea cu un număr pozitiv). Inegalitățile care aparțin acestui sistem minim unic sunt numite esențiale. Mulțimea de puncte ale unui politop care satisface o inegalitate esențială prin egalitate se numește fațetă.

Dacă politopul nu este complet-dimensional, atunci soluțiile lui $Ax\leq b$ se află într-un subspațiu afin adecvat al lui $\mathbb {R} ^{n}$ , iar politopul poate fi studiat ca un obiect în acest subspatiu. În acest caz există ecuații liniare care sunt satisfăcute de toate punctele politopului. Adăugarea uneia dintre aceste ecuații la oricare dintre inegalitățile definitorii nu schimbă politopul. Prin urmare, în general nu există o mulțime minimă unică de inegalități care să definească politopul.

În general, intersecția dintre semispațiile arbitrare nu trebuie să aibă frontieră. Totuși, dacă se dorește să existe o definiție echivalentă cu cea a unei anvelope convexe, atunci frontiera este necesară explicit.

Alte definiri

Cele două reprezentări împreună oferă o modalitate eficientă de a decide dacă un anumit vector este inclus într-un politop convex dat: pentru a arăta că se află în politop, este suficient să fie definit drept o combinație convexă a vârfurilor politopului (este folosită descrierea V); pentru a arăta că nu se află în politop, este suficient să se indice o singură inegalitate esențială pe care n-o satisface.^[5]

Definirea politopurilor nemărginite

Pentru un politop nemărginit (uneori numit poliedru), descrierea H este încă valabilă, dar descrierea V ar trebui extinsă. Theodore Motzkin (1936) a demonstrat că orice politop nemărginit poate fi reprezentat ca suma unui politop mărginit și a unui con poliedric convex.^[6] Cu alte cuvinte, fiecare vector dintr-un politop nemărginit este o „sumă convexă” a vârfurilor sale („punctele sale definitorii”), plus o „sumă conică” a vectorilor euclidieni ai muchiilor sale infinite („semidreptele sale definitorii”). Aceasta se numește teorema bazei finite.^[3]

Proprietăți

Fiecare politop convex (mărginit) este imaginea unui simplex, întrucât fiecare punct este o combinație convexă a vârfurilor. Totuși, politopurile nu sunt în general izomorfe cu simplexurile. Acest lucru este în contrast cu cazul spațiilor vectoriale și al combinațiilor liniare, fiecare spațiu vectorial finit-dimensional fiind nu numai o imagine a spațiului euclidian, ci de fapt este izomorf cu un spațiu cu un anumit număr de dimensiuni.

Laticea fețelor

O față a unui politop convex este orice intersecție a politopului cu un semispațiu astfel încât niciunul dintre punctele interioare ale politopului să nu se afle pe frontiera semispațiului. În mod echivalent, o față este ansamblul de puncte care satisfac egalitatea într-o inegalitate validă care descrie politopul. ^[7]

Dacă un politop este d-dimensional, fațetele sale sunt fețele sale (d − 1)-dimensionale, vârfurile sunt fețele sale 0-dimensionale, laturile (muchiile) sale sunt fețele sale unidimensionale, iar „crestele” sale sunt fețe (d − 2)-dimensionale.

Fiind dat un politop convex P definit de inegalitatea matricială $Ax\leq b$ , dacă fiecare rând din A corespunde cu un hiperplan de delimitare și este liniar independent de celelalte rânduri, atunci fiecare fațetă a P corespunde exact cu un rând din A și invers. Fiecare punct de pe o fațetă dată va satisface egalitatea liniară a rândului corespunzător din matrice. (Poate satisface sau nu și egalitatea în alte rânduri). Similar, fiecare punct dintr-o creastă va satisface egalitatea în două dintre rândurile lui A.

În general, o față (n − j)-dimensională satisface egalitatea în j rânduri din A. Aceste rânduri formează o bază a feței. (Rândurile nu sunt arbitrare; mulțimea lor trebuie să fie j-dimensională, adică rândurile trebuie să fie liniar independente în matricea extinsă [A | b]. Însă mulțimea de j rânduri poate să nu fie unică.) Geometric vorbind, aceasta înseamnă că fața este ansamblul de puncte de pe politop care se află în intersecția a j hiperplane de la limitele politopului.

Fețele unui politop convex formează astfel o latice euleriană numită laticea fețelor, unde ordonarea parțială este dată de mulțimea elementelor fețelor. Definiția unei fețe dată mai sus permite atât politopului în sine, cât și a politopului nul ( $\,\phi \,$ ) să fie considerate fețe, asigurându-se că fiecare pereche de fețe are o îmbinare în laticea fețelor. Întregul politop este elementul maxim unic al laticei, iar politopul nul, considerat a fi o față (−1)-dimensională al oricărui politop, este elementul minim unic al laticei.

Despre două politopuri se spune că sunt combinatoric izomorfe dacă laticele fețelor lor sunt izomorfe.

Graful politopului (1-scheletul) este doar mulțimea de vârfuri și laturi ale politopului, ignorând fețele cu dimensiuni superioare. De exemplu, un graf poliedric este graful unui politop tridimensional. Printr-un rezultat al lui Whitney^[8] laticea fețelor unui politop tridimensional este determinată de graful său. Același lucru este valabil pentru politopurile simple cu dimensiune arbitrară (Blind și Mani-Levitska 1987, demonstrând o conjectură a lui Micha Perles).^[9] Kalai (1988)^[10] a dat o demonstrație simplă. Deoarece laticele fețelor acestor politopuri sunt determinate de grafurile lor, problema de a decide dacă două politopuri convexe tridimensionale sau politopuri convexe simple sunt combinatoric izomorfe poate fi formulată echivalent ca un caz particular al problemei izomorfismului grafului. De asemenea, este posibilă și abordarea inversă, arătând că din izomorfismul politopurilor rezultă izomorfismul grafurilor lor.^[11]

Proprietăți topologice

Un politop convex, la fel ca orice subset compact convex al Rⁿ, este homomorf cu o bilă închisă.^[12] Fie m dimensiunea politopului. Dacă politopul este copmlet-dimensional, atunci m = n. Politopul convex este, prin urmare, o varietate m-dimensională cu frontieră, caracteristica sa Euler este 1, iar grupul său fundamental^⁠(d) este banal. Limita politopului convex este homomorfă cu o (m − 1)-sferă. Caracteristica Euler a frontierei este 0 pentru m par și 2 pentru m impar. Frontiera poate fi, de asemenea, considerată ca o teselare a spațiului sferic (m − 1)-dimensional — adică o pavare sferică.

Descompunere simplicială

Un politop convex poate fi descompus într-un complex simplicial, sau reuniune de simplexuri, care au anumite proprietăți.

Fiind dat un politop convex r-dimensional, P, o submulțime a vârfurilor sale conținând (r + 1) puncte afin independente definește un r-simplex. Este posibil să se formeze o colecție de submulțimi astfel încât reunirea simplexurilor corespunzătoare să fie egală cu P, iar intersecția oricăror două simplexuri să fie vidă, fie un simplex de dimensiune inferioară. Această descompunere simplicială este baza multor metode de calcul ale volumului unui politop convex, deoarece volumul unui simplex este ușor de obținut cu o formulă.^[13]

Probleme algoritmice pentru un politop convex

Generarea reprezentărilor

Diferitele reprezentări ale unui politop convex au utilități diferite, prin urmare generarea unei anumite reprezentări este o problemă importantă. Problema generării unei reprezentări în V este cunoscută sub numele de problema enumerării vârfurilor, iar problema generării unei reprezentări în H este cunoscută sub numele de problema enumerării fațetelor. Deși mulțimea vârfurilor unui politop convex mărginit îl definește în mod unic, în diferite aplicații este important să se cunoască mai multe despre structura combinatorică a politopului, adică despre laticea fețelor sale. Diverși algoritmi pentru anvelopa convexă realizează atât enumerarea fațetelor, cât și de construcția laticei fețelor.

În cazul planului, adică pentru un poligon convex, atât problemele de enumerare a fațetelor, cât și a vârfurilor se reduc la ordonarea vârfurilor (respectiv a laturilor) din jurul anvelopei convexe. Asta este o sarcină banală când poligonul convex este descris în modul tradițional pentru poligoane, adică prin secvența ordonată a vârfurilor sale $v_{1},\dots ,v_{m}$ . Când lista de intrare cu vârfurile (sau laturile) nu este ordonată, complexitatea timpului problemelor devine $O(m\log m)$ .^[14] În modelul algebric al arborelui de decizie se cunoaște complexitatea minimă a calculului.^[15]

Calculul volumului

Problema calculului volumului unui politop convex a fost studiată în domeniul geometriei algoritmice^⁠(d). Volumul poate fi calculat aproximativ, de exemplu folosind tehnici Monte Carlo^⁠(d), verificând dacă un anumit punct se află în interiorul politopului sau în exterior. Metoda poate fi rafinată distribuind punctele între două politopuri cunoscute, dintre care unul este în interiorul politopului dat, iar celălalt îl cuprinde. În ceea ce privește calculul exact, un obstacol este acela că, atunci când este dată o descriere a politopului convex printr-un sistem de ecuații de inegalități liniare, pot apărea dificultăți datorită reprezentării numerelor reale în calculatorul respectiv.^[16]

Note

^ ^a ^b ^c ^d ^e ^f ^g Grünbaum, Convex…
^ ^a ^b Ziegler, Lectures…
^ ^a ^b en Melvyn W. Jeter, (1986) Mathematical Programming, ISBN: 0-8247-7478-7, p. 67
^ Ziegler, Lectures…, p. 51
^ Lovász, Plummer, Matching…, p. 256
^ en Motzkin, Theodore (1936). Beitrage zur Theorie der linearen Ungleichungen (Ph.D. dissertation). Jerusalem.
^ Lovász, Plummer, Matching…, p. 258
^ en Whitney, Hassler (1932). „Congruent graphs and the connectivity of graphs”. Amer. J. Math. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067 . JSTOR 2371086.
^ en Blind, Roswitha; Mani-Levitska, Peter (1987), „Puzzles and polytope isomorphisms”, Aequationes Mathematicae, 34 (2–3): 287–297, doi:10.1007/BF01830678, MR 0921106 .
^ en Kalai, Gil (1988), „A simple way to tell a simple polytope from its graph”, Journal of Combinatorial Theory, Ser. A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7 , MR 0964396 .
^ en Kaibel, Volker; Schwartz, Alexander (2003). „On the Complexity of Polytope Isomorphism Problems”. Graphs and Combinatorics. 19 (2): 215–230. arXiv:math/0106093 . doi:10.1007/s00373-002-0503-y. Arhivat din original la 21 iulie 2015.
^ en Glen Bredon, Topology and Geometry, 1993, ISBN: 0-387-97926-3, p. 56.
^ en Büeler, B.; Enge, A.; Fukuda, K. (2000). „Exact Volume Computation for Polytopes: A Practical Study”. Polytopes — Combinatorics and Computation. p. 131. doi:10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.
^ en Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, (2001) [1990]. "33.3 Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN: 0-262-03293-7. pp. 947–957
^ en Yao, Andrew Chi Chih (1981), „A lower bound to finding convex hulls”, Journal of the ACM, 28 (4): 780–787, doi:10.1145/322276.322289, MR 0677089 ; Ben-Or, Michael (1983), „Lower Bounds for Algebraic Computation Trees”, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80–86, doi:10.1145/800061.808735 .
^ en Lawrence, Jim (1991). „Polytope volume computation”. Mathematics of Computation (în engleză). 57 (195): 259–271. doi:10.1090/S0025-5718-1991-1079024-2 . ISSN 0025-5718.

Bibliografie

en Branko Grünbaum, Convex polytops, 2nd ed., revăzută de Volker Kaibel, Victor Klee și Günter M. Ziegler, 2003, ISBN: 0-387-40409-0, ISBN: 978-0-387-40409-7
en Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, 152, Berlin, New York: Springer-Verlag
en László Lovász, M. D. Plummer, Matching Theory, North-Holland: Annals of Discrete Mathematics, 29, 1986, ISBN: 0-444-87916-1, MR 0859549

Legături externe

Materiale media legate de Politopuri convexe la Wikimedia Commons
en Convex Polygon, (română Poligon convex) la Mathworld
en Convex Polyhedron, (română Poliedru convex) la Mathworld
en Komei Fukuda, Polyhedral computation FAQ.

Portal matematică

[grun-1] ^ ^a ^b ^c ^d ^e ^f ^g Grünbaum, Convex…

[zieg-2] Ziegler, Lectures…

[Jeter-3] Melvyn W. Jeter, (1986) Mathematical Programming, ISBN: 0-8247-7478-7, p. 67

[4] Ziegler, Lectures…, p. 51

[5] Lovász, Plummer, Matching…, p. 256

[6] Motzkin, Theodore (1936). Beitrage zur Theorie der linearen Ungleichungen (Ph.D. dissertation). Jerusalem.

[7] Lovász, Plummer, Matching…, p. 258

[8] Whitney, Hassler (1932). „Congruent graphs and the connectivity of graphs”. Amer. J. Math. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067 . JSTOR 2371086.

[9] Blind, Roswitha; Mani-Levitska, Peter (1987), „Puzzles and polytope isomorphisms”, Aequationes Mathematicae, 34 (2–3): 287–297, doi:10.1007/BF01830678, MR 0921106 .

[10] Kalai, Gil (1988), „A simple way to tell a simple polytope from its graph”, Journal of Combinatorial Theory, Ser. A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7 , MR 0964396 .

[11] Kaibel, Volker; Schwartz, Alexander (2003). „On the Complexity of Polytope Isomorphism Problems”. Graphs and Combinatorics. 19 (2): 215–230. arXiv:math/0106093 . doi:10.1007/s00373-002-0503-y. Arhivat din original la 21 iulie 2015.

[bredon-12] Glen Bredon, Topology and Geometry, 1993, ISBN: 0-387-97926-3, p. 56.

[13] Büeler, B.; Enge, A.; Fukuda, K. (2000). „Exact Volume Computation for Polytopes: A Practical Study”. Polytopes — Combinatorics and Computation. p. 131. doi:10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.

[14] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, (2001) [1990]. "33.3 Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN: 0-262-03293-7. pp. 947–957

[15] Yao, Andrew Chi Chih (1981), „A lower bound to finding convex hulls”, Journal of the ACM, 28 (4): 780–787, doi:10.1145/322276.322289, MR 0677089 ; Ben-Or, Michael (1983), „Lower Bounds for Algebraic Computation Trees”, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80–86, doi:10.1145/800061.808735 .

[16] Lawrence, Jim (1991). „Polytope volume computation”. Mathematics of Computation (în engleză). 57 (195): 259–271. doi:10.1090/S0025-5718-1991-1079024-2 . ISSN 0025-5718.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]