Volume de computação de poliedros convexos de alta dimensão

9

Estou procurando um software para calcular / estimar o volume de poliedros convexos de alta dimensão. Mais especificamente, eu estou interessado em um programa, que pode lidar com corpos com vértices em espaço dimensional com parâmetros delimitados aproximadamente da seguinte forma: e . Observe que não há garantia no número de faces.ndd50.n1000

A página de Jeff Erickson possui um link para o programa Vinci-1.0.5 , que possui um limite rígido de 255 faces. Esta é uma limitação da implementação, o próprio algoritmo provavelmente pode lidar com mais faces em tempo razoável.

Não consegui encontrar nenhuma implementação do método de estimativa baseado em cadeias de Markov, embora eu ache que elas serão ainda menos eficientes.

Existe algum software que possa lidar com a gama de parâmetros descritos acima ou com algum relaxamento moderado? Ficaria muito grato por outras referências também.

Grigory Yaroslavtsev
fonte

Respostas:

7

Você pode tentar usar o qhull http://www.qhull.org/ - ele pode calcular o volume do casco convexo dos vértices. No entanto, a priori, não vejo nenhuma razão para o desempenho razoável do seu intervalo de números. Se o qhull não funcionar, você pode tentar o CGAL / GALIA. Na pior das hipóteses, você pode tentar impulsionar um dos algoritmos de caminhada aleatória que você mencionou - eles não devem ser muito difíceis de implementar neste caso, mas as constantes envolvidas podem ser muito grandes ...

Sariel Har-Peled
fonte
Obrigado, Sariel! Qhull trabalhou para mim por d = 10, n = 32, mas parece estar preso para sempre por d = 15, n = 64. Dados os algoritmos que implementa, parece que ele é mais orientado em espaços de baixa dimensão. Existe alguma chance de que possa haver uma análise do tempo de execução assintótico para algoritmos de casco convexo, dependendo desses dois parâmetros?
Grigory Yaroslavtsev
Na verdade, o site diz: "Para cascos convexos e cruzamentos de meio espaço, o Qhull pode ser usado para 2-d até 8-d". Portanto, não surpreende que tenha ficado preso por 15 dias.
Grigory Yaroslavtsev
Atualmente, o cdd de Fukuda ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) parece mais promissor, vou tentar brincar com ele.
Grigory Yaroslavtsev
ndn\chãod/2nd