Представление суммы минковского для двух полиэдров системой линейных неравенств

Аннотация

Любой выпуклый полиэдр представим как множество решений некоторой системы линейных неравенств. Алгебраическая сумма по Минковскому выпуклых полиэдров $X,Y\subset \mathbb{\mathbb{R}}^n$ также является выпуклым полиэдром, и, следовательно, также представим как множество решений некоторой системы линейных неравенств. В статье предложен полиномиальный алгоритм решения указанной задачи, основанный на формировании ряда избыточных ограничений в представлении слагаемых и их трансляции в результирующее представление. Предложен эффективный способ использования параллельных и распределенных вычислений для реализации алгоритма.