Calcul du volume des polyèdres convexes de grande dimension

Je recherche un logiciel de calcul / estimation de volume de polyèdres convexes de grande dimension. Plus spécifiquement, je m'intéresse à un programme, qui peut gérer des corps avec sommets dans un espace dimensionnel avec des paramètres à peu près comme suit: et . Notez qu'il n'y a aucune garantie sur le nombre de faces. $n$ $d$ $d \le 50$ $n \le 1000$

La page de Jeff Erickson a un lien vers un programme Vinci-1.0.5 , qui a une limite fixe de 255 faces. Ceci est une limitation de l'implémentation, l'algorithme lui-même peut probablement gérer plus de visages dans un délai raisonnable.

Je n'ai trouvé aucune implémentation de la méthode d'estimation basée sur les chaînes de Markov, bien que je suppose qu'elles seront encore moins efficaces.

Existe-t-il un logiciel capable de gérer la gamme de paramètres décrits ci-dessus ou une relaxation modérée de celui-ci? Je serais également très reconnaissant pour toute autre référence.

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

Réponses:

Vous pouvez essayer d'utiliser qhull http://www.qhull.org/ - il peut calculer le volume de la coque convexe des sommets. Cependant, a priori, je ne vois aucune raison pour qu'il fonctionne raisonnablement pour votre plage de nombres. Si qhull ne fonctionne pas, vous pouvez essayer CGAL / GALIA. Dans le pire des cas, vous pouvez essayer d'implémenter l'un des algorithmes de marche aléatoire que vous avez mentionnés - ils ne devraient pas être trop difficiles à implémenter dans ce cas, mais les constantes impliquées pourraient être très grandes ...

Sariel Har-Peled
la source

Merci, Sariel! Qhull a fonctionné pour moi pour d = 10, n = 32, mais semble être bloqué pour toujours pour d = 15, n = 64. Compte tenu des algorithmes qu'il implémente, il semble qu'il soit davantage orienté sur les espaces de faible dimension. Y a-t-il une chance qu'il y ait une analyse du temps de fonctionnement asymptotique pour les algorithmes de coque convexe, en fonction de ces deux paramètres?

Grigory Yaroslavtsev

En fait, le site Web dit: "Pour les coques convexes et les intersections de demi-espace, Qhull peut être utilisé pour 2-j jusqu'à 8-d." Il n'est donc pas surprenant qu'il soit resté bloqué pendant 15 jours.

Grigory Yaroslavtsev

Actuellement, le cdd de Fukuda ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) semble le plus prometteur, je vais essayer de jouer avec.

Grigory Yaroslavtsev

Bien. IL est connu qu'un polytope avec sommets en dimensions a dans le pire des cas facettes. Mettre points sur la courbe de moment en dimensions vous fournit un tel polytope. Il me semble peu probable que le calcul du volume puisse être fait plus rapidement que le nombre de facettes. Donc, vous devez vraiment implémenter les documents de marche aléatoire si vous voulez de meilleurs résultats ....

n

$n$

d

$d$

n^{\floor d / 2}

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

n

$n$

d

$d$

Sariel Har-Peled