Objętość obliczeniowa wielowymiarowych wypukłych wielościanów

Szukam oprogramowania do obliczania / szacowania objętości wielowymiarowych wypukłych wielościanów. Mówiąc dokładniej, jestem zainteresowany programem, który może obsługiwać ciała $n$ wierzchołki w $d$ -wymiarowa przestrzeń z parametrami z grubsza określonymi następująco: $d \le 50$ i $n \le 1000$ . Pamiętaj, że nie ma gwarancji liczby twarzy.

Strona Jeffa Ericksona zawiera link do programu Vinci-1.0.5 , który ma twardy limit 255 twarzy. Jest to ograniczenie implementacji, sam algorytm prawdopodobnie poradzi sobie z większą liczbą twarzy w rozsądnym czasie.

Nie mogłem znaleźć żadnych implementacji metody szacowania opartej na łańcuchach Markowa, choć sądzę, że będą one jeszcze mniej wydajne.

Czy jest jakieś oprogramowanie, które może obsłużyć zakres parametrów opisanych powyżej lub jego umiarkowane złagodzenie? Byłbym również bardzo wdzięczny za wszelkie inne referencje.

cg.comp-geom software convex-geometry high-dimensional-geometry Grigorij Jarosławcew
źródło

Odpowiedzi:

Możesz spróbować użyć qhull http://www.qhull.org/ - może obliczyć objętość wypukłego kadłuba wierzchołków. Jednak z góry nie widzę żadnego powodu, aby działał rozsądnie dla twojego zakresu liczb. Jeśli qhull nie działa, możesz wypróbować CGAL / GALIA. W najgorszym przypadku możesz spróbować ulepszyć jeden z wymienionych przez ciebie algorytmów chodzenia losowego - nie powinny być zbyt trudne do wdrożenia w tym przypadku, ale zaangażowane stałe mogą być bardzo duże ...

Sariel Har-Peled
źródło

Dziękuję Sariel! Qhull pracował dla mnie dla d = 10, n = 32, ale wydaje się, że utknął na zawsze dla d = 15, n = 64. Biorąc pod uwagę algorytmy, które implementuje, wygląda na to, że jest bardziej zorientowany na przestrzenie niskiego wymiaru. Czy jest jakaś szansa na analizę asymptotycznego czasu pracy algorytmów wypukłego kadłuba, w zależności od tych dwóch parametrów?

Grigorij Jarosławcew

W rzeczywistości strona internetowa mówi: „W przypadku wypukłych kadłubów i skrzyżowań półprzestrzeni Qhull można stosować do 2-d do 8-d.” Nic więc dziwnego, że utknął na 15-d.

Grigorij Jarosławcew

Obecnie cdd Fukudy ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) wydaje się najbardziej obiecujący, spróbuję z nim grać.

Grigorij Jarosławcew

Dobrze. Wiadomo, że z polytopem

n

$n$ wierzchołki w

d

$d$ wymiary mają w najgorszym przypadku

n^{\floor d / 2}

$n^{\floor{d/2}}$ aspekty. Putting

n

$n$ punkty na krzywej momentu w

d

$d$ wymiary zapewniają taki polytop. Wydaje mi się mało prawdopodobne, aby obliczanie objętości można było wykonać szybciej niż mnogość aspektów. Więc naprawdę musisz wdrożyć losowe dokumenty, jeśli chcesz uzyskać lepsze wyniki ...

Sariel Har-Peled