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

Получена характеризация $C$-семипространств частичной выпуклости. Приведена оценка числа $C$-семипространств в случае, когда число направлений частичной выпуклости конечно. Разработан алгоритм перечисления $C$-семипространств с полиномиальной скоростью. Доказано, что проблема распознавания аппроксимаций частично-выпуклых оболочек, порожденных пересечением $C$-семипространств частичной выпуклости, $\operatorname{NP}$-трудна.
Библиография: 5 названий.