Приближение выпуклого объема

При анализе алгоритмов несколько авторов изучали вычисление объема многомерных выпуклых тел — проблему, которую также можно использовать для моделирования многих других задач комбинаторного перечисления .Часто в этих работах используется модель вычислений «черного ящика», в которой входные данные предоставляются подпрограммой для проверки того, находится ли точка внутри или снаружи выпуклого тела, а не путем явного перечисления вершин или граней выпуклого многогранника .Известно, что в этой модели ни один детерминированный алгоритм не может обеспечить точную аппроксимацию. ^[1]^[2] и даже для явного перечисления граней или вершин проблема #P-hard . ^[3]Однако совместная работа Мартина Дайера , Алана М. Фриза и Равиндрана Каннана предоставила схему аппроксимации рандомизированным полиномиальным временем для этой проблемы:обеспечивая резкий контраст между возможностями рандомизированных и детерминированных алгоритмов. ^[4]

Основным результатом работы является рандомизированный алгоритм поиска $\varepsilon$ приближение к объему выпуклого тела $K$ в $n$ -мерное евклидово пространство, предполагая существование членского оракула . Алгоритм требует времени, ограниченного полиномом от $n$ , размерность $K$ и $1/\varepsilon$ .Алгоритм объединяет две идеи:

Используя метод Монте-Карло цепи Маркова (MCMC), можно генерировать точки, которые почти равномерно и случайно распределены внутри данного выпуклого тела. Основная схема алгоритма — практически равномерная выборка изнутри. $K$ путем размещения сетки, состоящей из $n$ -мерные кубы и совершаем случайное блуждание по этим кубам. Используя теорию быстрого перемешивания цепей Маркова , они показывают, что для того, чтобы случайное блуждание приобрело почти равномерное распределение, требуется полиномиальное время. ^[4]
Используя браковочную выборку , можно сравнивать объемы двух выпуклых тел, вложенных одно в другое, когда их объемы отличаются друг от друга в пределах небольшого коэффициента. Основная идея состоит в том, чтобы генерировать случайные точки внутри внешнего из двух тел и подсчитывать, как часто эти точки оказываются и внутри внутреннего тела.

Данное выпуклое тело можно аппроксимировать последовательностью вложенных тел, в конечном итоге достигая одного известного объема (гиперсферы), при этом этот подход используется для оценки коэффициента изменения объема на каждом шаге этой последовательности. Умножение этих коэффициентов дает приблизительный объем исходного тела.

Эта работа принесла своим авторам премию Фулкерсона 1991 года . ^[5]

Улучшения

Хотя время этого алгоритма является полиномиальным, оно имеет высокий показатель степени.Последующие авторы улучшили время работы этого метода, обеспечив более быстрое смешивание цепей Маркова для той же задачи. ^[6]^[7]^[8]^[9]

Обобщения

Результат аппроксимации за полиномиальное время был обобщен на более сложные структуры, такие как объединение и пересечение объектов. ^[10] Это относится к проблеме меры Клее .

Ссылки

^ Элекес, Г. (1986), «Геометрическое неравенство и сложность вычислительного объема», Дискретная и вычислительная геометрия , 1 (4): 289–292, doi : 10.1007/BF02187701 , MR 0866364
^ Ламб, Имре ; Фюреди, Золтан (1987), «Вычислить объем сложно», Дискретная и вычислительная геометрия , 2 (4): 319–326, doi : 10.1007/BF02187886 , hdl : 1813/8572 , MR 0911186
^ Дайер, Мартин ; Фриз, Алан (1988), «О сложности вычисления объема многогранника», SIAM Journal on Computing , 17 (5): 967–974, doi : 10.1137/0217060 , MR 0961051
^ Jump up to: ^а ^б Дайер, Мартин ; Фриз, Алан ; Каннан, Рави (1991), «Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел», Журнал ACM , 38 (1): 1–17, doi : 10.1145/102782.102783 , MR 1095916 , S2CID 13268711
^ Лауреаты премии Фулкерсона , Американское математическое общество , получено 3 августа 2017 г.
^ Эпплгейт, Дэвид ; Каннан, Рави (1991), «Выборка и интеграция почти логарифмически вогнутых функций», Труды двадцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '91) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 156. –163, номер домена : 10.1145/103418.103439 , ISBN 978-0-89791-397-3 , S2CID 15432190
^ Каннан, Рави ; Ловас, Ласло ; Симоновиц, Миклош (1997), "Случайные блуждания и $O^{*}(n^{5})$ алгоритм объема для выпуклых тел», Случайные структуры и алгоритмы , 11 (1): 1–50, doi : 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2 -Х , МР 1608200
^ Ловас, Л. ; Симоновиц, М. (1993), «Случайные блуждания по выпуклому телу и улучшенный алгоритм объема», Random Structures & Algorithms , 4 (4): 359–412, doi : 10.1002/rsa.3240040402 , MR 1238906
^ Ловас, Л. ; Вемпала, Сантош (2006), «Моделированный отжиг в выпуклых телах и $O^{*}(n^{4})$ алгоритм объема», Журнал компьютерных и системных наук , 72 (2): 392–417, doi : 10.1016/j.jcss.2005.08.004 , MR 2205290
^ Брингманн, Карл; Фридрих, Тобиас (01 августа 2010 г.). «Аппроксимация объема объединений и пересечений многомерных геометрических объектов» . Вычислительная геометрия . 43 (6): 601–610. arXiv : 0809.0835 . дои : 10.1016/j.comgeo.2010.03.004 . hdl : 11858/00-001M-0000-000F-1603-4 . ISSN 0925-7721 . S2CID 5930593 .

[E-1] Элекес, Г. (1986), «Геометрическое неравенство и сложность вычислительного объема», Дискретная и вычислительная геометрия , 1 (4): 289–292, doi : 10.1007/BF02187701 , MR 0866364

[BF-2] Ламб, Имре ; Фюреди, Золтан (1987), «Вычислить объем сложно», Дискретная и вычислительная геометрия , 2 (4): 319–326, doi : 10.1007/BF02187886 , hdl : 1813/8572 , MR 0911186

[DF-3] Дайер, Мартин ; Фриз, Алан (1988), «О сложности вычисления объема многогранника», SIAM Journal on Computing , 17 (5): 967–974, doi : 10.1137/0217060 , MR 0961051

[DFK-4] Jump up to: ^а ^б Дайер, Мартин ; Фриз, Алан ; Каннан, Рави (1991), «Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел», Журнал ACM , 38 (1): 1–17, doi : 10.1145/102782.102783 , MR 1095916 , S2CID 13268711

[5] Лауреаты премии Фулкерсона , Американское математическое общество , получено 3 августа 2017 г.

[AK-6] Эпплгейт, Дэвид ; Каннан, Рави (1991), «Выборка и интеграция почти логарифмически вогнутых функций», Труды двадцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '91) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 156. –163, номер домена : 10.1145/103418.103439 , ISBN 978-0-89791-397-3 , S2CID 15432190

[KLS-7] Каннан, Рави ; Ловас, Ласло ; Симоновиц, Миклош (1997), "Случайные блуждания и $O^{*}(n^{5})$ алгоритм объема для выпуклых тел», Случайные структуры и алгоритмы , 11 (1): 1–50, doi : 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2 -Х , МР 1608200

[LS-8] Ловас, Л. ; Симоновиц, М. (1993), «Случайные блуждания по выпуклому телу и улучшенный алгоритм объема», Random Structures & Algorithms , 4 (4): 359–412, doi : 10.1002/rsa.3240040402 , MR 1238906

[LV-9] Ловас, Л. ; Вемпала, Сантош (2006), «Моделированный отжиг в выпуклых телах и $O^{*}(n^{4})$ алгоритм объема», Журнал компьютерных и системных наук , 72 (2): 392–417, doi : 10.1016/j.jcss.2005.08.004 , MR 2205290

[10] Брингманн, Карл; Фридрих, Тобиас (01 августа 2010 г.). «Аппроксимация объема объединений и пересечений многомерных геометрических объектов» . Вычислительная геометрия . 43 (6): 601–610. arXiv : 0809.0835 . дои : 10.1016/j.comgeo.2010.03.004 . hdl : 11858/00-001M-0000-000F-1603-4 . ISSN 0925-7721 . S2CID 5930593 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]