Самая большая клетка в расположении

10

Q . Какова сложность нахождения наибольшего объемаограниченная ячейка в Arrangment из гиперплоскостей в размерности г ?nd

Я чувствую, что должен это знать ... Но я не нахожу окончательной ссылки.

Это ? Как насчет специализации d = 2 : ячейка с наибольшей площадью в расположении линий?Ω(nd)d=2

Джозеф О'Рурк
источник

Ответы:

6

O(nd)1QCα1/n2m=(logn)/αQPCPO((n2/3m2/3+n+m)polylog)

αO((n+1/α+n2/3/α2/3)polylogn)αQ

Сариэль Хар-Пелед
источник
1
α1/n2