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

Для заданного набора гиперплоскостей, определяемых нормальными векторами , его типами ячеек (или знаковыми векторами) являются все векторы t ∈ { + , - } m, для которых существует вектор v ∈ R d так , что ⟨ v , ч я ⟩ ≠ 0 и т я = знак ( ⟨ v , ч я ⟩ $h_1,\dots,h_m \in \mathbf R^d$$t\in\{+,-\}^m$$v\in\mathbf R^d$$\langle v,h_i \rangle \neq 0$$t_i = \text{sign}( \langle v,h_i \rangle )$имеет место для всех . Здесь, ⟨ U , V ⟩ обозначает скалярное произведение , а знак ( х ) обозначает знак ( + или - ) от ненулевого вещественного числа х .$i$$\langle u,v\rangle$$\text{sign}(x)$$+$$-$$x$

Вопрос: Какой самый быстрый известный алгоритм для обратной операции? Учитывая набор типов ячеек , мы хотим вычислить некоторый набор гиперплоскостей в как можно меньшем количестве измерений, чтобы его типы ячеек были надмножеством t 1 , … , t n .$t_1,\dots,t_n$$t_1,\dots,t_n$

Это эквивалентно вычислению ранга знака матрицы, которая является NP-трудной, как показано в этой статье . Таким образом, вы не можете ожидать слишком эффективного алгоритма.