Volumen computacional de poliedros convexos de alta dimensión

Estoy buscando un software para calcular / estimar el volumen de poliedros convexos de alta dimensión. Más específicamente, estoy interesado en un programa, que puede manejar cuerpos con vértices en espacio dimensional con los parámetros delimitadas aproximadamente como sigue: y . Tenga en cuenta que no hay garantía sobre el número de caras. $n$ $d$ $d \le 50$ $n \le 1000$

La página de Jeff Erickson tiene un enlace a un programa Vinci-1.0.5 , que tiene un límite estricto de 255 caras. Esta es una limitación de la implementación, el algoritmo en sí mismo probablemente puede manejar más caras en un tiempo razonable.

No pude encontrar ninguna implementación del método de estimación basado en cadenas de Markov, aunque supongo que serán aún menos eficientes.

¿Existe algún software que pueda manejar el rango de parámetros descritos anteriormente o alguna relajación moderada? Estaría muy agradecido por cualquier otra referencia también.

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

Respuestas:

Puede probar y usar qhull http://www.qhull.org/ : puede calcular el volumen del casco convexo de los vértices. Sin embargo, a priori no veo ninguna razón para que funcione razonablemente para su rango de números. Si qhull no funciona, puede probar CGAL / GALIA. En el peor de los casos, puede probar e implementar uno de los algoritmos de paseo aleatorio que mencionó: no deberían ser demasiado difíciles de implementar en este caso, pero las constantes involucradas podrían ser muy grandes ...

Sariel Har-Peled
fuente

Gracias Sariel! Qhull trabajó para mí por d = 10, n = 32, pero parece estar atascado para siempre por d = 15, n = 64. Dado los algoritmos que implementa, parece que está más orientado en espacios de baja dimensión. ¿Hay alguna posibilidad de que pueda haber un análisis del tiempo de ejecución asintótico para algoritmos de casco convexo, dependiendo de estos dos parámetros?

Grigory Yaroslavtsev

En realidad, el sitio web dice: "Para cascos convexos e intersecciones de medio espacio, Qhull puede usarse para 2-d hasta 8-d". Por lo tanto, no es sorprendente que se haya atascado durante 15 días.

Grigory Yaroslavtsev

Actualmente, el cdd de Fukuda ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) parece muy prometedor, intentaré jugar con él.

Grigory Yaroslavtsev

Bien. Se sabe que un politopo con

vértices en

dimensiones tiene en el peor de los casos

facetas. Poner

puntos en la curva de momento en

dimensiones le proporciona dicho politopo. Me parece improbable que el cálculo del volumen se pueda hacer más rápido que la mayoría de las facetas. Entonces, realmente tiene que implementar los documentos de caminata aleatorios si desea mejores resultados ...

n

$n$

d

$d$

n^{\floor d / 2}

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

n

$n$

d

$d$

Sariel Har-Peled