Dışbükey politop - Convex polytope

Bir dışbükey politop , aynı zamanda -boyutlu Öklid uzayında bulunan bir dışbükey küme olması gibi ek bir özelliğe sahip olan bir politopun özel bir halidir . Çoğu metin, sınırlı bir dışbükey politop için "politop" terimini ve daha genel, muhtemelen sınırsız nesne için "polihedron" kelimesini kullanır. Diğerleri (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, sınırlılık tartışılan konu için kritik olduğunda aşağıda kullanılacaktır. Yine de diğer metinler, dışbükey bir politopu sınırıyla tanımlar. ${\görüntüleme stili n}$${\displaystyle \mathbb {R} ^{n}}$

Dışbükey politoplar, hem matematiğin çeşitli dallarında hem de uygulamalı alanlarda, özellikle de doğrusal programlamada önemli bir rol oynamaktadır .

Grünbaum ve Ziegler'in konuyla ilgili etkili ders kitaplarında ve ayrık geometrideki diğer birçok metinde konveks politoplara genellikle "politoplar" denir. Grünbaum, bunun yalnızca "dışbükey" kelimesinin sonsuz tekrarından kaçınmak için olduğuna ve tartışmanın baştan sona sadece dışbükey türe uygulanıyor olarak anlaşılması gerektiğine dikkat çekiyor (s. 51).

Bir politop denir tam boyutlu bir ise de boyutlu nesne . ${\görüntüleme stili n}$${\displaystyle \mathbb {R} ^{n}}$

Örnekler

• Sınırlı dışbükey politopların birçok örneği " polihedron " makalesinde bulunabilir .
• 2-boyutlu bir durumda tam boyutlu örnekler olarak yarı düzlem , iki paralel hat arasında bir şerit, bir açı şekli (iki paralel olmayan yarı Düzlemlerin kesişimi), bir konveks ile tanımlanan bir şekil çokgen zincir ile iki uçlarına bağlı ışınlar ve dışbükey bir çokgen .
• Sınırsız bir dışbükey politopun özel durumları, iki paralel hiperdüzlem arasındaki bir levha, iki paralel olmayan yarım-uzay tarafından tanımlanan bir kama , bir çokyüzlü silindir (sonsuz prizma ) ve üç veya daha fazla yarım -uzay tarafından tanımlanan bir çokyüzlü koni (sonsuz koni ). ortak bir noktadan geçen boşluklardır.

Tanımlar

Bir dışbükey politop, eldeki problem için neyin daha uygun olduğuna bağlı olarak çeşitli şekillerde tanımlanabilir. Grünbaum'un tanımı, uzayda bir dışbükey noktalar kümesi cinsindendir. Diğer önemli tanımlar şunlardır: yarım boşlukların kesişimi olarak (yarım boşluk gösterimi) ve bir dizi noktanın dışbükey gövdesi olarak (köşe gösterimi).

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

Grünbaum, Convex Polytopes adlı kitabında, konveks politopu , sınırlı sayıda uç nokta içeren kompakt bir dışbükey küme olarak tanımlar :

Bir dizi arasında olan dışbükey belirgin noktalarına her çifti için, eğer , içinde uç noktaları ile kapalı kesimi, ve içinde yer almaktadır .${\görüntüleme stili K}$${\displaystyle \mathbb {R} ^{n}}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili K}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili K}$

Bu, sınırlı bir dışbükey politopu , sonlu kümenin politopun uç noktaları kümesini içermesi gereken sonlu bir nokta kümesinin dışbükey gövdesi olarak tanımlamaya eşdeğerdir . Böyle bir tanımlamaya tepe noktası gösterimi ( V-temsil veya V-tanım ) denir . Kompakt bir dışbükey politop için, minimal V-tanımı benzersizdir ve politopun köşeleri kümesi tarafından verilir . Bir dışbükey politop, tüm köşeleri tamsayı koordinatlarına sahipse, integral politop olarak adlandırılır .

Yarım uzayların kesişimi

Bir dışbükey politop, sonlu sayıda yarım uzayın kesişimi olarak tanımlanabilir. Bu tanımlamaya yarım uzay gösterimi ( H-temsili veya H-tanımı ) denir . Bir dışbükey politopun sonsuz sayıda H-tanımı vardır. Bununla birlikte, tam boyutlu bir dışbükey politop için, minimal H-tanımı aslında benzersizdir ve faset tanımlayan yarım uzaylar kümesi tarafından verilir .

Bir kapalı yarı-uzay bir şekilde yazılabilir doğrusal eşitsizlik :

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

söz konusu politopu içeren alanın boyutu nerede . Bu nedenle, kapalı bir dışbükey politop , doğrusal eşitsizlikler sisteminin çözüm kümesi olarak kabul edilebilir : ${\görüntüleme stili n}$

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

politopu tanımlayan yarım boşlukların sayısı nerede . Bu kısaca matris eşitsizliği olarak yazılabilir : ${\görüntüleme stili m}$

${\displaystyle Balta\leq b}$

burada bir bir matris, bir olduğu , koordinatları değişkenler, kolon vektörü için , ve bir olduğu , koordinatları sağ tarafı olan kolon vektörü için skalar eşitsizliklerin. ${\görüntüleme stili A}$${\displaystyle m\times n}$${\görüntüleme stili x}$${\görüntüleme stili n\ kere 1}$${\görüntüleme stili x_{1}}$${\displaystyle x_{n}}$${\görüntüleme stili b}$${\displaystyle m\times 1}$${\displaystyle b_{1}}$${\ Displaystyle b_{m}}$

Bir açık dışbükey politop yerine olmayan katı olanları formüllerde kullanılan katı eşitsizlikler ile aynı şekilde tanımlanmıştır.

Her bir satır katsayıları ve ilgili yarım boşluk tanımlayan lineer eşitsizlik katsayıları ile örtüşmektedir. Bu nedenle, matristeki her satır , politopun destekleyici bir hiperdüzlemine , politopu içeren bir yarım uzayı sınırlayan bir hiperdüzleme karşılık gelir . Destekleyici bir hiperdüzlem de politopla kesişiyorsa, buna sınırlayıcı hiperdüzlem denir (destekleyici bir hiperdüzlem olduğu için, politopu yalnızca politopun sınırında kesebilir). ${\görüntüleme stili A}$${\görüntüleme stili b}$

Yukarıdaki tanım, politopun tam boyutlu olduğunu varsayar. Bu durumda, benzersiz bir minimal tanımlayıcı eşitsizlikler kümesi vardır (pozitif bir sayı ile çarpmaya kadar). Bu benzersiz minimal sisteme ait eşitsizliklere esas denir . Temel bir eşitsizliği eşitlikle karşılayan bir politopun noktaları kümesine faset denir .

Politop tam boyutlu değilse, o zaman çözeltileri uygun olarak yalan afin alt uzay arasında ve politop bu alt-alanında bir nesne olarak incelenebilir. Bu durumda politopun tüm noktaları tarafından sağlanan lineer denklemler vardır. Tanımlayıcı eşitsizliklerden herhangi birine bu denklemlerden birinin eklenmesi politopu değiştirmez. Bu nedenle, genel olarak, politopu tanımlayan benzersiz bir minimal eşitsizlik seti yoktur. ${\displaystyle Balta\leq b}$${\displaystyle \mathbb {R} ^{n}}$

Genel olarak keyfi yarı-uzayların kesişiminin sınırlandırılması gerekmez. Bununla birlikte, dışbükey bir gövde olarak buna eşdeğer bir tanıma sahip olmak isteniyorsa, o zaman açıkça sınırlama 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 vermek için etkili bir yol sağlar: politopta olduğunu göstermek için, onu politop köşelerinin dışbükey bir kombinasyonu olarak sunmak yeterlidir (V-tanımı kullanıldı); politopta olmadığını göstermek için ihlal ettiği tek bir tanımlayıcı eşitsizliği sunmak yeterlidir.

Vektörlerle temsilde ince bir nokta, vektörlerin sayısının boyutta üstel olabileceğidir, bu nedenle bir vektörün politopta olduğunun kanıtı üstel olarak uzun olabilir. Neyse ki, Carathéodory teoremi , politoptaki her vektörün en fazla d +1 tanımlayıcı vektörlerle temsil edilebileceğini garanti eder , burada d uzayın boyutudur.

Sınırsız politopların temsili

Sınırsız bir politop için (bazen çokyüzlü olarak adlandırılır), H-tanımı hala geçerlidir, ancak V-tanımı genişletilmelidir. Theodore Motzkin (1936), herhangi bir sınırsız politopun , sınırlı bir politop ve bir dışbükey çokyüzlü koninin toplamı olarak temsil edilebileceğini kanıtladı . Diğer bir deyişle, sınırsız bir politop her vektör, dışbükey toplamı olan köşelerin (kendi "tanımlayan noktaları"), artı, bir konik toplamı ait Öklid vektörleri sonsuz kenarları (kendi "tanımlayan ışınları") olarak. Buna sonlu temel teoremi denir .

Özellikleri

Her (sınırlı) dışbükey politop, bir simpleks görüntüsüdür , çünkü her nokta (sonlu sayıda) köşelerin dışbükey bir birleşimidir . Bununla birlikte, politoplar genel olarak basitlere eşbiçimli değildir. Bu, vektör uzayları ve lineer kombinasyonların durumunun aksinedir , her sonlu-boyutlu vektör uzayı sadece bir görüntü değil, aynı zamanda bazı boyutlu Öklid uzayının (veya diğer alanların analogu) eşbiçimlidir.

yüz kafes

Bir yüz konveks bir politop bir ile politop herhangi kesişimidir halfspace şekilde halfspace sınırında politop yalan iç noktaları yok. Eşdeğer olarak, bir yüz, politopun bazı geçerli eşitsizliğinde eşitlik veren noktalar kümesidir.

Politop ise d boyutlu, kendi yönü olarak (vardır d  - 1) boyutlu yüzleri, kendi tepe noktaları olan 0 boyutlu yüzleri, kendi kenarları olan 1 boyutlu yüzleri, ve çıkıntılar olarak (vardır d  - 2) - boyutlu yüzler.

Matris eşitsizliği tarafından tanımlanan bir dışbükey politop P verildiğinde , A'daki her satır sınırlayıcı bir hiperdüzleme karşılık geliyorsa ve diğer satırlardan doğrusal olarak bağımsızsa , o zaman P'nin her yüzü tam olarak bir A satırına karşılık gelir ve bunun tersi de geçerlidir. Belirli bir yüzey üzerindeki her nokta, matristeki karşılık gelen satırın doğrusal eşitliğini sağlayacaktır. (Diğer satırlardaki eşitliği de sağlayabilir veya sağlamayabilir). Benzer şekilde, bir sırt üzerindeki her nokta, A'nın iki satırında eşitliği sağlayacaktır . ${\displaystyle Balta\leq b}$

Genel olarak, ( n  -  j ) boyutlu bir yüz , A'nın j özel satırında eşitliği sağlar . Bu sıralar yüzün temelini oluşturur. Geometrik olarak konuşursak, bu, yüzün, politopun sınırlayıcı hiperdüzlemlerinin j'nin kesişiminde bulunan politop üzerindeki noktalar kümesi olduğu anlamına gelir .

Dışbükey bir politopun yüzleri, böylece , yüz kafesi adı verilen bir Euler kafesi oluşturur ; burada kısmi sıralama, yüzlerin kümelenmesiyle yapılır. Yukarıda verilen bir yüzün tanımı, hem politopun kendisinin hem de boş kümenin yüz olarak kabul edilmesini sağlayarak, her yüz çiftinin yüz kafesinde birleşim ve birleşim olmasını sağlar. Tüm politop, kafesin benzersiz maksimum öğesidir ve her politopun (-1) boyutlu yüzü ( boş politop ) olarak kabul edilen boş küme, kafesin benzersiz minimum öğesidir.

İki polytopes denir kombinasyon yöntemiyle izomorf onların yüz kafesler ise izomorfik .

Politop grafiği ( polytopal grafik , politop grafiği , 1-iskelet ) daha yüksek boyutlu yüzeyler göz ardı köşe ve tek politop kenarları kümesidir. Örneğin, çokyüzlü bir grafik , üç boyutlu bir politopun politop grafiğidir. Whitney'in bir sonucu olarak, üç boyutlu bir politopun yüz kafesi, grafiği ile belirlenir. Aynısı, keyfi boyuttaki basit politoplar için de geçerlidir (Blind & Mani-Levitska 1987, Micha Perles'in bir varsayımını kanıtlıyor ). Kalai (1988), benzersiz lavabo yönelimlerine dayanan basit bir kanıt verir . Bu politopların yüzey kafesleri grafikleri tarafından belirlendiğinden, iki üç boyutlu veya basit dışbükey politopun kombinatoryal olarak izomorfik olup olmadığına karar verme problemi, grafik izomorfizm probleminin özel bir durumu olarak eşdeğer şekilde formüle edilebilir . Bununla birlikte, politop izomorfizm testinin graf izomorfizmi tamamlanmış olduğunu göstererek bu problemleri ters yöne çevirmek de mümkündür.

topolojik özellikler

Herhangi bir kompakt konveks alt kümesinin gibi bir dışbükey politop, R ^{, n} , bir homeomorphic kapalı için top . Let m politop boyutunu belirtir. Politop tam boyutlu ise, o zaman m = n . Bu nedenle dışbükey politop , sınırı olan m boyutlu bir manifolddur , Euler özelliği 1'dir ve temel grubu önemsizdir. Dışbükey  politopun sınırı bir ( m − 1)-küresine homeomorfiktir . Sınırın Euler özelliği çift m için 0 ve tek m için 2'dir . Sınır , ( m  -1) boyutlu küresel uzayın bir mozaiklemesi olarak da kabul edilebilir - yani küresel bir döşeme olarak .

basit ayrıştırma

Bir dışbükey politop, belirli özellikleri sağlayan basit bir komplekse veya basitlerin birliğine ayrıştırılabilir .

Bir dışbükey r -boyutlu politop P verildiğinde , ( r +1) afin bağımsız noktalar içeren köşelerinin bir alt kümesi bir r- simplex tanımlar . Karşılık gelen simplices birliği eşittir, öyle ki alt kümelerinin bir toplama oluşturulması mümkündür , P , ve boş ya da herhangi bir, iki simplices kesişimini ya da bir düşük boyutlu simplex. Bu basit ayrıştırma bir dışbükey politopun hacmini hesaplamak için birçok yöntemin temelidir, çünkü bir simpleksin hacmi bir formülle kolayca verilir.

Bir dışbükey politop için algoritmik problemler

Temsilciliklerin inşası

Bir dışbükey politopun farklı gösterimleri farklı faydalara sahiptir, bu nedenle bir gösterimin diğer bir gösterimle oluşturulması önemli bir problemdir. Bir V-temsilinin inşası problemi, köşe numaralandırma problemi olarak bilinir ve bir H-temsilinin inşası problemi , faset numaralandırma problemi olarak bilinir . Sınırlı bir dışbükey politopun tepe kümesi onu benzersiz bir şekilde tanımlarken, çeşitli uygulamalarda politopun kombinatoryal yapısı, yani yüz kafesi hakkında daha fazla bilgi sahibi olmak önemlidir. Çeşitli dışbükey gövde algoritmaları hem faset numaralandırma hem de yüz kafes yapısı ile ilgilenir.

Düzlemsel durumda, yani, bir dışbükey çokgen için , hem faset hem de tepe noktası numaralandırma sorunları, dışbükey gövde etrafındaki köşeleri (ilişki kenarlarını) sıralar. Dışbükey çokgen, çokgenler için geleneksel bir şekilde , yani köşelerinin sıralı dizisiyle belirtildiğinde, bu önemsiz bir görevdir . Köşelerin (veya kenarların) giriş listesi sırasız olduğunda, problemlerin zaman karmaşıklığı O ( m  log  m ) olur. Cebirsel karar ağacı hesaplama modelinde eşleşen bir alt sınır bilinmektedir . ${\displaystyle v_{1},\dots,v_{m}}$

Hacim hesaplama

Bir dışbükey politopun hacmini hesaplama görevi , hesaplamalı geometri alanında incelenmiştir . Hacim yaklaşık olarak hesaplanabilir , örneğin, bir üyelik kehanetine erişim olduğunda dışbükey hacim yaklaşımı tekniği kullanılarak . İçin olduğu gibi tam olarak hesaplama , bir engel bir şekilde konveks bir politop bir temsilini verildiğinde, yani denklem sisteminin bir doğrusal eşitsizlikler , politop hacmi olabilir bit uzunluğu , bu temsilde polinom değildir.

Ayrıca bakınız

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

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Dışbükey çokgen" . Matematik Dünyası .
• Weisstein, Eric W. "Dışbükey çokyüzlü" . Matematik Dünyası .
• Komei Fukuda , Çokyüzlü hesaplama SSS .