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

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

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

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

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

cg.comp-geom software convex-geometry high-dimensional-geometry Григорий Ярославцев
источник

Ответы:

Вы можете попробовать использовать 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

$n$ вершины в

d

$d$ Размеры имеют в худшем случае

n^{\floor d / 2}

$n^{\floor{d/2}}$ фасеты. Ввод

n

$n$ указывает на момент кривой в

d

$d$ Размеры дают вам такой многогранник. Мне кажется маловероятным, что вычисление объема может быть выполнено быстрее, чем количество граней. Таким образом, вам действительно нужно применять документы о случайных блужданиях, если вы хотите получить лучшие результаты ...

Сариэль Хар-Пелед