Dışbükey politop - Convex polytope

3 boyutlu bir dışbükey politop

Bir dışbükey politop özel bir durumdur politop, aynı zamanda bir dışbükey küme içerdiği ${ displaystyle n}$boyutlu Öklid uzayı ${ displaystyle mathbb {R} ^ {n}}$. Çoğu metin^[1][2] "politop" terimini bir sınırlı dışbükey politop ve daha genel, muhtemelen sınırsız nesne için "polihedron" kelimesi. Diğerleri^[3] (bu makale dahil) politopların sınırsız olmasına izin verir. "Sınırlı / sınırsız dışbükey politop" terimleri, tartışılan konu için sınırlılığın kritik olduğu her durumda aşağıda kullanılacaktır. Yine de diğer metinler dışbükey bir politopu sınırıyla tanımlar.

Konveks politoplar, hem çeşitli dallarda önemli bir rol oynar. matematik ve uygulamalı alanlarda, özellikle de doğrusal programlama.

Grünbaum'un etkili ders kitaplarında^[1] ve Ziegler^[2] konuyla ilgili ve diğer birçok metinde olduğu gibi ayrık geometri, dışbükey politoplar genellikle basitçe "politoplar" olarak adlandırılır. Grünbaum, bunun yalnızca "dışbükey" kelimesinin sonsuz tekrarından kaçınmak için olduğuna ve tartışmanın sadece dışbükey çeşidi kapsayacak şekilde anlaşılması gerektiğine işaret ediyor (s. 51).

Bir politop denir tam boyutlu eğer bir ${ displaystyle n}$boyutlu nesne ${ displaystyle mathbb {R} ^ {n}}$.

Örnekler

• Makalede birçok sınırlı dışbükey politop örneği bulunabilir. "çokyüzlü ".
• 2 boyutlu durumda, tam boyutlu örnekler, yarım düzlem iki paralel çizgi arasında bir şerit, bir açı şekil (paralel olmayan iki yarı düzlemin kesişimi), dışbükey ile tanımlanan bir şekil poligonal zincir ikisiyle ışınlar uçlarına bağlı ve bir dışbükey Poligon.
• Sınırsız bir dışbükey politopun özel durumları, iki paralel hiper düzlem arasındaki bir levhadır, iki paralel olmayan ile tanımlanan bir kama yarım boşluklar, bir çok yüzlü silindir (sonsuz prizma ) ve a çok yüzlü koni (sonsuz koni ) ortak bir noktadan geçen üç veya daha fazla yarı boşlukla tanımlanır.

Tanımlar

Dışbükey bir politop, eldeki sorun için neyin daha uygun olduğuna bağlı olarak birkaç yolla tanımlanabilir. Grünbaum'un tanımı, uzayda bir dışbükey nokta kümesi cinsinden ifade edilir. Diğer önemli tanımlar şunlardır: kavşak nın-nin yarım boşluklar (yarım boşluk gösterimi) ve dışbükey örtü bir dizi nokta (köşe gösterimi).

Köşe gösterimi (dışbükey gövde)

Kitabında Konveks Politoplar Grünbaum, dışbükey bir politopu bir kompakt dışbükey küme sınırlı sayıda aşırı noktalar:

Bir set ${ displaystyle K}$ nın-nin ${ displaystyle mathbb {R} ^ {n}}$ dır-dir dışbükey her bir çift farklı nokta için ${ displaystyle a}$, ${ displaystyle b}$ içinde ${ displaystyle K}$, uç noktaları olan kapalı segment ${ displaystyle a}$ ve ${ displaystyle b}$ içinde bulunur ${ displaystyle K}$.

Bu, sınırlı bir dışbükey politopu tanımlamaya eşdeğerdir. dışbükey örtü Sonlu kümenin politopun uç noktalarının kümesini içermesi gereken sonlu bir nokta kümesinin. Böyle bir tanıma a köşe gösterimi (V-gösterimi veya V açıklaması).^[1] Kompakt bir dışbükey politop için, minimum V açıklaması benzersizdir ve köşeler politopun.^[1] Dışbükey bir politopa bir integral politop tüm köşelerinin tamsayı koordinatları varsa.

Yarım boşlukların kesişimi

Dışbükey bir politop, sonlu sayıda yarı uzayın kesişimi olarak tanımlanabilir. Böyle bir tanıma yarım uzay gösterimi (H-gösterimi veya H açıklaması).^[1] Dışbükey bir politopun sonsuz sayıda H tanımı vardır. Bununla birlikte, tam boyutlu bir dışbükey politop için, minimum H açıklaması aslında benzersizdir ve faset -yarı boşlukları tanımlama.^[1]

Bir kapalı yarım boşluk olarak yazılabilir doğrusal eşitsizlik:^[1]

${ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} + cdots + a_ {n} x_ {n} leq b}$

nerede ${ displaystyle n}$ söz konusu politopu içeren boşluğun boyutudur. Bu nedenle, a kapalı dışbükey politop çözüm kümesi olarak kabul edilebilir. doğrusal eşitsizlikler sistemi:

${ displaystyle { begin {alignat} {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 {alignat}}}$

nerede ${ displaystyle m}$ politopu tanımlayan yarı boşlukların sayısıdır. Bu kısaca şu şekilde yazılabilir: matris eşitsizlik:

${ displaystyle Ax leq b}$

nerede ${ displaystyle A}$ bir ${ displaystyle m kere n}$ matris, ${ displaystyle x}$ bir ${ displaystyle n times 1}$ koordinatları değişken olan sütun vektörü ${ displaystyle x_ {1}}$ -e ${ displaystyle x_ {n}}$, ve ${ displaystyle b}$ bir ${ displaystyle m times 1}$ koordinatları sağ taraf olan sütun vektörü ${ displaystyle b_ {1}}$ -e ${ displaystyle b_ {m}}$ skaler eşitsizlikler.

Bir açık dışbükey politop aynı şekilde, katı olmayan eşitsizlikler yerine formüllerde kullanılan katı eşitsizliklerle tanımlanır.

Her satırın katsayıları ${ displaystyle A}$ ve ${ displaystyle b}$ ilgili yarı uzayı tanımlayan doğrusal eşitsizlik katsayılarına karşılık gelir. Dolayısıyla, matristeki her satır bir alt düzlemi desteklemek politopun, politopu içeren bir yarım uzayı sınırlayan bir hiper düzlem. Destekleyen bir hiper düzlem de politop ile kesişirse, buna bir sınırlayıcı hiper düzlem (destekleyen bir hiper düzlem olduğu için, politopu yalnızca politopun sınırında kesebilir).

Yukarıdaki tanım, politopun tam boyutlu olduğunu varsayar. Bu durumda, bir benzersiz minimal tanımlama eşitsizlikleri (pozitif bir sayıyla çarpmaya kadar). Bu benzersiz minimal sisteme ait eşitsizliklere önemli. Eşitlikle temel bir eşitsizliği karşılayan bir politopun nokta kümesine faset.

Politop tam boyutlu değilse, çözümleri ${ displaystyle Ax leq b}$ doğru dürüst yalan söylemek afin alt uzay nın-nin ${ displaystyle mathbb {R} ^ {n}}$ ve politop bu alt uzayda bir nesne olarak incelenebilir. Bu durumda, politopun tüm noktalarının karşıladığı doğrusal denklemler vardır. Tanımlayıcı eşitsizliklerden herhangi birine bu denklemlerden birini eklemek politopu değiştirmez. Bu nedenle, genel olarak, politopu tanımlayan benzersiz bir minimal eşitsizlikler kümesi yoktur.

Genel olarak, keyfi yarı boşlukların kesişme noktasının sınırlandırılmasına gerek yoktur. Bununla birlikte, dışbükey bir gövde olarak buna eşdeğer bir tanıma sahip olmak istenirse, sınırlama açıkça gerekli olmalıdır.

Farklı temsilleri kullanma

İki temsil birlikte, belirli bir vektörün belirli bir dışbükey politopa dahil edilip edilmediğine karar vermenin etkili bir yolunu sağlar: politopta olduğunu göstermek için, politop köşelerinin dışbükey bir kombinasyonu olduğunu göstermek yeterlidir (V-açıklaması kullanıldı); politopta olmadığını göstermek için, ihlal ettiği tek bir tanımlayıcı eşitsizliği sunmak yeterlidir.^[4]:256

Vektörlerle gösterimdeki ince bir nokta, vektörlerin sayısının boyutta üstel olabileceğidir, bu nedenle bir vektörün politopta olduğunun kanıtı üssel olarak uzun olabilir. Neyse ki, Carathéodory teoremi politoptaki her vektörün en fazla ile temsil edilebileceğini garanti eder d+1 tanımlayan vektörler, nerede d mekanın boyutudur.

Sınırsız politopların gösterimi

Sınırsız bir politop için (bazen: polihedron olarak adlandırılır), H tanımı hala geçerlidir, ancak V tanımının genişletilmesi gerekir. Theodore Motzkin (1936), sınırsız herhangi bir politopun bir toplamı olarak temsil edilebileceğini kanıtladı. sınırlı politop ve bir dışbükey çok yüzlü koni.^[5] Başka bir deyişle, sınırsız bir politoptaki her vektör bir dışbükey toplam köşelerinin sayısı ("tanımlama noktaları"), artı bir konik toplam of Öklid vektörleri sonsuz kenarları ("tanımlayıcı ışınları"). Bu denir sonlu temel teoremi.^[3]

Özellikleri

Her (sınırlı) dışbükey politop, bir basit her nokta bir dışbükey kombinasyon (sonlu çok) köşelerden. Bununla birlikte, politoplar genel olarak basitler için izomorfik değildir. Bu, durumunun tersidir vektör uzayları ve doğrusal kombinasyonlar, her sonlu boyutlu vektör uzayı sadece bir görüntü değil, aynı zamanda bir boyuttaki Öklid uzayının (veya diğer alanlara göre analog) bir izomorfudur.

Yüz kafesi

Bir yüz dışbükey bir politopun, politopun bir yarım boşluk öyle ki politopun iç noktalarının hiçbiri yarı uzayın sınırı üzerinde yer almaz. Benzer şekilde, bir yüz, politopun bazı geçerli eşitsizliklerinde eşitlik sağlayan noktalar kümesidir.^[4]:258

Bir politop ise dboyutlu, onun yönler onun (d - 1) boyutlu yüzler, köşeler 0 boyutlu yüzleri, kenarlar 1 boyutlu yüzleri ve sırtlar onun (d - 2) boyutlu yüzler.

Dışbükey bir politop verildiğinde P matris eşitsizliği ile tanımlanır ${ displaystyle Ax leq b}$, eğer her satır Bir sınırlayıcı bir hiper düzleme karşılık gelir ve Doğrusal bağımsız diğer satırların her bir yönü, ardından P tam olarak bir satıra karşılık gelir Birve tam tersi. Belirli bir yüzdeki her nokta, matristeki karşılık gelen satırın doğrusal eşitliğini karşılayacaktır. (Diğer satırlarda da eşitliği sağlayabilir veya sağlamayabilir). Benzer şekilde, bir sırt üzerindeki her nokta, sıranın ikisinde eşitliği sağlayacaktır. Bir.

Bir yüz kafesi kare piramit olarak çizilmiş Hasse diyagramı; Kafesteki her yüz, köşe kümesiyle etiketlenir.

Genel olarak, bir (n − j) boyutlu yüz eşitliği sağlar j belirli satırlar Bir. Bu satırlar bir temel yüzün. Geometrik olarak konuşursak, bu, yüzün, politopun kesişme noktasında yer alan noktalar kümesi olduğu anlamına gelir. j politopun sınırlayıcı hiper düzlemlerinden.

Dışbükey bir politopun yüzleri böylece bir Euler kafes aradı yüz kafes, burada kısmi sıralama yüzlerin set kapsamına göre yapılır. Yukarıda verilen bir yüzün tanımı, hem politopun kendisinin hem de boş kümenin yüzler olarak kabul edilmesine izin vererek, her yüz çiftinin yüz kafesinde bir birleşim ve buluşma olmasını sağlar. Tüm politop, kafesin benzersiz maksimum elemanıdır ve boş küme (−1) boyutlu bir yüz (a boş politop) her politopun), kafesin benzersiz minimum unsurudur.

İki politop denir kombinatoryal olarak izomorfik yüz kafesleri ise izomorf.

politop grafiği (politopal grafik, politopun grafiği, 1 iskelet) yalnızca politopun köşeleri ve kenarları kümesidir, yüksek boyutlu yüzleri yok sayar. Örneğin, bir çok yüzlü grafik üç boyutlu bir politopun politop grafiğidir. Sonucu Whitney^[6] üç boyutlu bir politopun yüz kafesi grafiği tarafından belirlenir. Aynısı için de geçerlidir basit politoplar keyfi boyutun (Blind & Mani-Levitska 1987, bir varsayımı kanıtlıyor) Micha Perles ).^[7] Kalai (1988)^[8] dayalı basit bir kanıt verir benzersiz lavabo yönelimleri. Bu politopların yüz kafesleri grafikleri tarafından belirlendiğinden, iki üç boyutlu veya basit dışbükey politopun birleşimsel olarak izomorfik olup olmadığına karar verme problemi, özel bir durum olarak eşdeğer şekilde formüle edilebilir. grafik izomorfizm problemi. Bununla birlikte, politop izomorfizm testinin grafik izomorfizmasının tamamlandığını göstererek, bu problemleri ters yönde çevirmek de mümkündür.^[9]

Topolojik özellikler

Dışbükey bir politop, herhangi bir kompakt dışbükey alt kümesi gibi Rⁿ, dır-dir homomorfik kapalı top.^[10] İzin Vermek m politopun boyutunu belirtir. Politop tam boyutluysa, o zaman m = n. Dışbükey politop bu nedenle bir m-boyutlu manifold sınır ile Euler karakteristiği 1'dir ve temel grup önemsizdir. Dışbükey politopun sınırı, homomorfiktir. (m - 1) - küre. Sınırın Euler özelliği çift için 0'dır m ve tek için 2 m. Sınır aynı zamanda bir mozaikleme nın-nin (m - 1) boyutlu küresel uzay - yani bir küresel döşeme.

Basit ayrıştırma

Dışbükey bir politop, bir basit kompleks veya birliği basitler, belirli özellikleri tatmin ediyor.

Dışbükey verildiğinde rboyutlu politop P, köşelerinin bir alt kümesini içeren (r+1) afin bir şekilde bağımsız puanlar bir r-basit. Karşılık gelen basitliklerin birleşiminin eşit olacağı şekilde bir alt kümeler koleksiyonu oluşturmak mümkündür. Pve herhangi iki simpleksin kesişimi ya boş ya da daha düşük boyutlu bir simplekstir. Bu basit ayrıştırma, bir dışbükey politopun hacmini hesaplamak için birçok yöntemin temelini oluşturur, çünkü bir simpleksin hacmi bir formülle kolayca verilir.^[11]

Dışbükey bir politop için algoritmik problemler

Temsilciliklerin yapımı

Dışbükey bir politopun farklı temsillerinin farklı faydaları vardır, bu nedenle bir diğerine verilen bir temsilin oluşturulması önemli bir sorundur. Bir V temsilinin inşası sorunu şu şekilde bilinir: köşe numaralandırma sorunu ve bir H temsilinin inşası problemi, faset numaralandırma problemi. Sınırlı bir dışbükey politopun köşe seti onu benzersiz bir şekilde tanımlarken, çeşitli uygulamalarda politopun kombinatoryal yapısı, yani yüz kafesi hakkında daha fazla bilgi edinmek önemlidir. Çeşitli dışbükey gövde algoritmaları hem faset numaralandırma hem de yüz kafes yapısı ile ilgilenin.

Düzlemsel durumda, yani bir dışbükey Poligon hem faset hem de köşe numaralandırma problemleri, dışbükey gövde etrafındaki sıralama köşeleri (ve kenarları) ile ilgilidir. Dışbükey çokgen geleneksel olarak belirtildiğinde önemsiz bir görevdir. çokgenler yol, yani köşelerinin sıralı sırasına göre ${ displaystyle v_ {1}, noktalar, v_ {m}}$. Köşelerin (veya kenarların) giriş listesi sırasız olduğunda, zaman karmaşıklığı sorunların Ö (m günlükm).^[12] Eşleşen alt sınır bilinir cebirsel karar ağacı hesaplama modeli.^[13]

Hacim hesaplama

Hesaplama görevi Ses dışbükey bir politopun alanında çalışılmıştır. hesaplamalı geometri. Hacim hesaplanabilir yaklaşık olarak örneğin, dışbükey hacim yaklaşımı teknik, bir üyeliğe erişim sağlandığında kehanet. Gelince kesin hesaplama Bir engel, dışbükey politopun bir denklem sistemi nın-nin doğrusal eşitsizlikler politopun hacmi bir bit uzunluğu bu gösterimde polinom değildir.^[14]

Ayrıca bakınız

• Odaklı matroid
• Nef çokyüzlü
• Steinitz teoremi dışbükey çokyüzlüler için

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Dışbükey Poligon". MathWorld.
• Weisstein, Eric W. "Dışbükey çokyüzlü". MathWorld.
• Komei Fukuda, Çok yüzlü hesaplama SSS.