Rechenvolumen hochdimensionaler konvexer Polyeder

Ich suche Software zur Berechnung / Schätzung des Volumens hochdimensionaler konvexer Polyeder. Insbesondere interessiert mich ein Programm, das Körper mit Eckpunkten im dimensionalen Raum mit ungefähr wie folgt begrenzten Parametern verarbeiten kann: und . Beachten Sie, dass für die Anzahl der Gesichter keine Garantie besteht. $n$ $d$ $d \le 50$ $n \le 1000$

Jeff Ericksons Seite enthält einen Link zu einem Programm Vinci-1.0.5 , das eine feste Grenze von 255 Gesichtern hat. Dies ist eine Einschränkung der Implementierung. Der Algorithmus selbst kann wahrscheinlich in angemessener Zeit mehr Gesichter verarbeiten.

Ich konnte keine Implementierungen der auf Markov-Ketten basierenden Schätzmethode finden, obwohl ich denke, dass sie noch weniger effizient sein werden.

Gibt es eine Software, die den oben beschriebenen Parameterbereich oder eine moderate Entspannung verarbeiten kann? Ich wäre auch für andere Referenzen sehr dankbar.

cg.comp-geom software convex-geometry high-dimensional-geometry Grigory Yaroslavtsev
quelle

Antworten:

Sie können versuchen, qhull http://www.qhull.org/ zu verwenden - es kann das Volumen der konvexen Hülle der Eckpunkte berechnen. A priori sehe ich jedoch keinen Grund dafür, dass es für Ihren Zahlenbereich eine angemessene Leistung erbringt. Wenn qhull nicht funktioniert, können Sie CGAL / GALIA ausprobieren. Im schlimmsten Fall können Sie versuchen, einen der von Ihnen erwähnten Random-Walk-Algorithmen zu impementieren - sie sollten in diesem Fall nicht zu schwer zu implementieren sein, aber die beteiligten Konstanten können sehr groß sein ...

Sariel Har-Peled
quelle

Danke, Sariel! Qhull arbeitete für mich für d = 10, n = 32, scheint aber für d = 15, n = 64 für immer hängen zu bleiben. Angesichts der Algorithmen, die es implementiert, scheint es eher auf niedrigdimensionale Räume ausgerichtet zu sein. Besteht die Möglichkeit, dass die asymptotische Laufzeit für konvexe Rumpfalgorithmen in Abhängigkeit von diesen beiden Parametern analysiert wird?

Grigory Yaroslavtsev

Tatsächlich heißt es auf der Website: "Für konvexe Rümpfe und Halbraumkreuzungen kann Qhull für 2-d bis 8-d verwendet werden." Es ist also nicht verwunderlich, dass es für 15 Tage stecken geblieben ist.

Grigory Yaroslavtsev

Derzeit scheint Fukudas CD ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) am vielversprechendsten zu sein. Ich werde versuchen, damit zu spielen.

Grigory Yaroslavtsev

n

$n$

d

$d$

n^{\floor d / 2}

$n^{\floor{d/2}}$

n

$n$

d

$d$