алгоритм проверки выпуклости пространства

Question

возможно ли это сделать менее чем за полиномиальное время?

Answer 1

Используйте больше слов.

Мы не можем знать, что именно вы спрашиваете. Мы можем только догадываться.

Я не думаю, что пространства могут быть выпуклыми или вогнутыми вообще ... может быть, вы имеете в виду объем или площадь? В любом случае, я не думаю, что вы будете бить полиномиальное время, учитывая, что сложность поверхности будет полиномиальной по своей природе.

Answer 2

Хм ... интересный вопрос. Я верю, что ответ - да. Грубо, найдите уравнение плоскости каждой из граней; для каждой пары соединенных граней, если угол между ними тупой, объем вогнутый. Это должно выполняться за время O (log (n)).

Могу поспорить, есть какой-то способ решить это с помощью алгоритма раскраски графа, но я просто не такой умный ...