Вычислительный объем многомерных выпуклых многогранников

9

Я ищу программное обеспечение для вычисления / оценки объема многомерных выпуклых многогранников. В частности, я заинтересован в программе, которая может обрабатывать тела сN вершины в dпространство с параметрами, ограниченными примерно следующим образом: d50 а также N1000, Обратите внимание, что нет гарантии на количество лиц.

На странице Джеффа Эриксона есть ссылка на программу Vinci-1.0.5 , которая имеет жесткий лимит в 255 граней. Это ограничение реализации, сам алгоритм, вероятно, может обрабатывать больше лиц в разумные сроки.

Я не смог найти никаких реализаций метода оценки на основе цепей Маркова, хотя, думаю, они будут еще менее эффективными.

Существует ли какое-либо программное обеспечение, которое может обрабатывать диапазон параметров, описанных выше, или его умеренное ослабление? Я был бы очень благодарен за любые другие ссылки.

Григорий Ярославцев
источник

Ответы:

7

Вы можете попробовать использовать qhull http://www.qhull.org/ - он может вычислить объем выпуклой оболочки вершин. Тем не менее, априори я не вижу причин для его разумной работы для вашего диапазона номеров. Если qhull не работает, вы можете попробовать CGAL / GALIA. В худшем случае вы можете попытаться реализовать один из упомянутых вами алгоритмов случайного блуждания - их не должно быть слишком сложно реализовать в этом случае, но используемые константы могут быть очень большими ...

Сариэль Хар-Пелед
источник
Спасибо, Сариэль! Qhull работал для меня при d = 10, n = 32, но, кажется, застрял навсегда при d = 15, n = 64. Учитывая алгоритмы, которые он реализует, похоже, что он больше ориентирован на низкоразмерные пространства. Есть ли вероятность, что может быть проведен анализ асимптотического времени работы алгоритмов выпуклой оболочки в зависимости от этих двух параметров?
Григорий Ярославцев
На самом деле, на сайте написано: «Для выпуклых корпусов и пересечений полупространства Qhull может использоваться от 2 до 8 дней». Поэтому неудивительно, что он застрял на 15 день.
Григорий Ярославцев
В настоящее время CDD Фукуда ( cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html ) кажется наиболее перспективным, я попытаюсь поиграть с ним.
Григорий Ярославцев
Хорошо. ОНО известно, что многогранник сN вершины в d Размеры имеют в худшем случае N\этажd/2фасеты. ВводN указывает на момент кривой в dРазмеры дают вам такой многогранник. Мне кажется маловероятным, что вычисление объема может быть выполнено быстрее, чем количество граней. Таким образом, вам действительно нужно применять документы о случайных блужданиях, если вы хотите получить лучшие результаты ...
Сариэль Хар-Пелед