lrsfourier - Bulutta Çevrimiçi

Program:

ADI

lrslib - Dışbükey çokyüzlülerin yeniden gösterimleri arasında dönüştürme.

SİNOPSİS

lrs girdi.ine

lrs girdi.ine | lrs tamponu

lrsfourier dosya.ine [dosya çıkışı]

fazlalık girdi.ine

TANIM

Bir çokyüzlü, bir eşitsizlikler listesiyle tanımlanabilir (H-temsili) veya bir liste olarak
köşelerinin ve aşırı ışınlarının (V-temsil). lrs dönüştüren bir C programıdır.
Bir polihedronun V-temsiline göre H-temsili ve tam tersi. Bu problemler
sırasıyla bilinmektedir tepe sayım ve dışbükey gövde sorunlar.

Fukuda'nın SSS Kanal[1] ile birlikte soruna daha ayrıntılı bir giriş içerir
yeni kullanıcı için birçok faydalı ipucu.

lrs tamponu bazı yinelenen çıktıları kaldırabilir. fazlalık gereksiz eşitsizlikleri bulur
giriş.

DOSYA BİÇİMLER

Dosya biçimleri Komei Fukuda ile ortaklaşa geliştirildi ve CDD[2].

için giriş lrs bir politopun H- veya V- temsilidir.

isim
{temsil satırı}
{seçenekler}
{doğrusallıklar[3]}
başlamak
çok mantıklı
{giriş matrisi}
son
{seçenekler}

isim politop için kullanıcı tarafından sağlanan bir addır. Yorumlar başlamadan önce görünebilir veya
sonundan sonra ve bir seçenek olarak yorumdan kaçınmak için özel bir ile başlamalıdır.
"*" veya "#" gibi karakter.

isim politop için kullanıcı tarafından sağlanan bir addır. temsil hat ya
"H-temsil" veya "V-temsil". Atlanırsa, H-temsilinin varsayıldığı varsayılır. NS
girdi katsayıları serbest biçimde okunur ve tür için kontrol edilmez. katsayılar
boşlukla ayrılmış. m satır sayısı ve n girdinin sütun sayısıdır
matris.

H-temsili
m tamsayısı eşitsizliklerin sayısıdır ve n tamsayısı
+1 girin. Eşitsizlikler listesi, formun eşitsizlik katsayılarını içerir.

a0 + a1x1+ ... + an-1 xn-1 >= 0.

Bu eşitsizlik satır olarak girilir

a0 a1... bir-1

Katsayılar, x/y formatında tamsayı veya rasyonel olarak girilebilir.

V-temsil
m tamsayısı, köşelerin ve ışınların sayısıdır ve n tamsayısının boyutudur.
giriş +1. Her köşe şeklinde verilir

1 v0 v 1... vn-1

Her ışın şeklinde verilir

0 r0 r 1... rn-1

burada r0 r 1... rn-1 ışın üzerindeki bir noktadır.

Her dosyada en az bir köşe olmalıdır. Sınırlı çokyüzlüler için
ışınları girdi. Katsayılar, x/y formatında tamsayı veya rasyonel olarak girilebilir.

not için CDD kullanıcılar: lrs temelde aynı dosya biçimini kullanır CDD. için hazırlanan dosyalar
CDD çok az değişiklikle veya hiç değişiklik yapılmadan çalışmalıdır. V-temsilinin
içindeki "gövde" seçeneğine karşılık gelir CDD. Özel seçenekler CDD girişte bırakılabilir
dosyalar ve tarafından yoksayılacak lrs. için giriş dosyalarını not edin lrs serbest formatta okunur,
çizgiden sonra m n rasyonel, lrs tam olarak m*n rasyonel veya ayrılmış tamsayı arayacaktır
boşlukla (boşluk, satır başı, sekme vb.). lrs fazladan sütunları "bırakmayacak"
n sağlanan sütun sayısından azsa girin.

Basic Opsiyonlar
Hemen hemen tüm seçenekler yerleştirildi sonra bitiş ifadesi ile uyumluluğu koruyarak CDD.
Bunun olmadığı durumlarda, açıkça belirtilecektir.

tüm temeller Bu seçenek talimat verir lrs her bir tabanı için her bir köşeyi (veya yüzü) listelemek için.
Çıktı kopya[4].[5] Bu seçenek genellikle printcobasis ile birleştirilir.

bağlı x H-temsiliyle kullanın - lrs veya nash için Büyütme veya küçültme
seçeneği seçilmelidir. x bir tam sayı veya rasyoneldir. Maksimizasyon için (bkz.
minimizasyon) mevcut amaç değeri ne zaman olursa olsun ters arama ağacı kesilir
x'ten küçüktür (karşılıklı olarak daha fazladır).

önbellek nlrs en son n sözlüğü ters arama ağacında saklar. Bu hızlandırır
geri izleme adımı, ancak daha fazla bellek gerektirir.

ayıklamak başlangıç ​​temeli bitiş temeliŞifreli ancak ayrıntılı iz, sözlükler vb. yazdırın.
#B=başlangıç ​​temeli ile başlar ve #B=bitiş temeli ile biter. ayıklamak 0 0 tam verir
iz.

basamak n yerleştirilir önce the başlamak ifade n, olması gereken maksimum ondalık basamak sayısıdır
kullanılmış. Bu aşılırsa, program bir mesajla sona erer (genellikle
yeniden başlatıldı). Varsayılan, yaklaşık 100 haneye ayarlanmıştır. Bir çalıştırmanın sonunda bir mesaj
kullanıcıya karşılaşılan maksimum tamsayı boyutu hakkında bilgi verilir. Bu kullanılabilir
sonraki çalıştırmalarda bellek kullanımını ve hızı optimize edin (örneğin tahmin yapıyorsanız).

çift ​​pertürb lrs, büyütme veya küçültme seçeneğiyle yürütülürse, ters arama
ağaç bu fonksiyon için optimum bir tepe noktasında köklenir.
köşeler, çıktı genellikle tamamlanmayacaktır. Bu seçenek, küçük bir tedirginlik verir.
amaç bundan kaçınmaktır. Başlangıç ​​sözlüğü ikili ise bir uyarı mesajı verilir.
dejenere.

tahminleri k Çıktı boyutunu tahmin edin. maxdepth ile birlikte kullanılır - bkz.
Tahmin.[6]

geometrik // Yalnızca H temsili veya voronoi seçeneği // Bu seçenekle her ışın
geldiği tepe noktası ile birlikte yazdırılır. Daha fazla bilgi için bakınız
Geometrik Işınlar İpuçları ve Yorumlar[5].

oranBu seçenek otomatik olarak açılır baskı kobası , bu yüzden aşağıya bakın
önce bu seçeneğin açıklaması. printcobasis n ile kullanılabilir. (Ver 4.2b) .PP İçin
girdi H-temsili, köşeyi/ışınları içeren tüm girdi eşitsizliklerinin indeksleri
çıkış olmak üzere. Basit bir yüz için, bu indeksler olduğundan yeni bir çıktı yoktur.
zaten listelenmiştir. Aksi takdirde, ek sıkı eşitsizlikler iki nokta üst üste işaretinden sonra listelenir.
.PP Giriş V-temsili için, faset üzerinde bulunan tüm giriş köşelerinin/ışınlarının indeksleri
yani çıkış olmak üzere. Yıldızlı bir dizin, bu tepe noktasının aynı zamanda
cobasis, ancak fasette yer almıyor. Kullanılan kaldırma işlemi nedeniyle ortaya çıkar.
giriş V-temsilleri ile.

#insidansprintcobasis ile aynı. ile uyumluluk için dahil cdd.

doğrusallık k i1i2 i ... ikGirdi satırlarda k doğrusallık içeriyor i1i2i ... ikarasında
girdi dosyası denklemlerdir. Görmek Doğrusallıklar.[3]

Maksimum derinlik k Arama k derinliğinde kesilecektir. veya daha az derinliğe sahip tüm bazlar
k'ye eşit hesaplanacaktır. k, negatif olmayan bir tamsayıdır ve bu seçenek,
tahminler - bkz. Tahmin.[6]not: H-temsilleri için, k derinliğindeki ışınlar
bildirildi. V-temsilleri için, k derinliğindeki yönler rapor edilmeyecektir.

maksimuma çıkarmak a0 bir1... bir-1 // Yalnızca H temsili //

azaltmak a0 bir1... bir-1 // Yalnızca H temsili //

lrs ile kullanılırsa, başlangıç ​​tepe noktası a0 + a1x1+ ... fonksiyonunu büyütür (veya küçültür) ...
+ an-1 xn-1.İkili yozlaşmayı önlemek için ikiliperturb seçeneği gerekli olabilir.Bkz. Nash
denge ve doğrusal Programlama[7]

azami çıkış n Üretilen çıktı satırı sayısını (köşeler+ışınlar veya yönler) n ile sınırlar

minimum derinlik k Negatif olmayan ka için, geriye doğru izleme k derinliğinde sonlandırılacaktır. Bu
alt ağaçlarda ters aramayı ayrı işlemler olarak çalıştırmak için kullanılabilir, örn.
dağıtılmış bilgi işlem ortamı.

negatif olmayan // Bu seçenek, başlangıç ​​ifadesinden önce gelmelidir// //Yalnızca H-temsili
// Hata: Yalnızca orijin çokyüzlü bir köşe ise kullanılabilir.
girdi, b+Ax>=0, x>=0 (yani tüm değişkenler) biçiminde bir H temsilidir
negatif olmayan, tüm kısıtlamalar eşitsizlikler) negatif olmayanları vermek gerekli değildir
Negatif olmayan seçenek kullanılıyorsa açıkça kısıtlamalar. Bu seçenek için kullanılamaz
V-temsilleri veya doğrusallık seçeneğiyle (bu durumda doğrusallıklar
eşitsizlik olarak kabul edilir). Bu seçenek redund ile kullanılabilir, ancak ima edilen
negatif olmama kısıtlamaları artıklık için test edilmez. Her şeyi test etmek için
giriş dosyasına negatif olmayan kısıtlamaları açıkça girmek gereklidir. (Ver'de
4.1, orijin bir tepe noktası olmalıdır).

baskı kobası k;lrs 4.0'da değiştirildi Her k'th kobasis yazdırılır. k atlanırsa,
cobasis, çıktısı alınan her tepe noktası/ışın/yüzey için yazdırılır. Uzun vadede işe yarar
gerektiğinde programın yeniden başlatılabilmesi için kobasisin ara sıra yazdırılması.
H-temsili: Girdi bir H temsiliyse, kobasis, endekslerin bir listesidir.
mevcut tepe noktasını veya ışını tanımlayan girdi dosyasındaki eşitsizlikler. Seçeneğe bakın
oran Daha fazla bilgi için yukarıda. Işınlar için bir kobasis de yazdırılır. Bu durumda
kobasis, ışının çıktığı tepe noktasının kobazisidir. indekslerden biri
yıldızlı ise, bu, kobasisten çıkarılacak eşitsizliği gösterir.
ışın. Alternatif olarak, eğer tüm temellerseçeneği kullanılırsa, tüm kobaseler yazdırılacaktır.
V-temsil: Girdi bir V temsiliyse, kobasis, girdinin bir listesidir.
geçerli yönü tanımlayan köşeler/ışınlar. Seçeneğe bakın oran daha fazlası için yukarıda
bilgi. Başlatmak için lrs bu yönden tüm 4 indeks bu sırayla verilmelidir
(* işaretini atlayın).

baskı gevşekliği Ver 4.2'deki Yenilikler ; // H-temsiliyle kullan // lrs aşağıdakilerin bir listesini yazdırır
Geçerli tepe noktası için kesinlikle sağlanan girdi eşitsizliklerinin endeksleri, yani.
karşılık gelen gevşek değişken pozitiftir. Negatif olmayan ayarlanırsa, liste ayrıca
pozitif olan her xi karar değişkeni için n+i endekslerini dahil edin. proje Tarafından kullanılan
lrsfourier[8] sadece.

yeniden V# R# B# derinlik {yüz #s or köşe/ışın #s} lrs4.0'da değiştirildi lrs olabilir
bilinen herhangi bir kobasisten yeniden başlatıldı. Hesaplama normal sonlandırmaya devam edecektir. Tüm
bilgilerin çıktısında yer alan bir baskı kobası seçeneği. sipariş of
the endeksleri is çok önemli, bunları tam olarak çıktıda göründükleri gibi girin
daha önce durdurulan çalıştırma.

başlangıç ​​kobasis i1i2i ... 1 içinde Bu, kullanıcının bilinen bir kobasis belirlemesine izin verir.
ters aramayı başlatır. i1i2i ... 1 içinde eşitsizliklerin bir listesidir (için
Bir kobası tanımlayan H temsili) veya tepe noktaları/ışınları (V temsili için). Eğer öyleyse
geçersiz veya bu seçenek belirtilmemiş, lrs kendi başlangıç ​​kobasını bulacaktır. NS
yeni bir tepe noktası ile karşılaşıldığında ters arama ağacı kesilir (budanır). Not: Bu
içindeki optimum tepe noktasına bitişik tüm köşelerin kümesini mutlaka ürettiğini not eder.
çokyüzlü, ancak bunların sadece bir alt kümesi.

gereksiz sözlerle doluÇalıştırma hakkında biraz daha ayrıntılı bilgi yazdırın.

hacim // Yalnızca V temsili // Hesaplama hacmi - bkz. bölüm hacim Hesaplama.[9]

Voronoi // Yalnızca V temsili - bitiş ifadesinden hemen sonra yer alır // Hesapla
Voronoi diyagramı - bkz. bölüm Voronoi Diyagramlar.[10]

NOTLAR

1. SSS sayfası
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. cdd
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. doğrusallıklar
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Doğrusallıklar

4. Çıktı Çoğaltması
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Çoğaltma

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

6. Tahmin.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Tahmin

7. Doğrusal Programlama
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programlama

8.lrsfourier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. Hacim Hesaplaması.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Hesaplama

10. Voronoi Diyagramları.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diyagramlar

onworks.net hizmetlerini kullanarak lrsfourier'i çevrimiçi kullanın