А.А. Бедринцев, В.В. Чепыжов

Две связанные задачи о сокращении избыточности при представлении данных с помощью выпуклых многогранников

В работе рассмотрены две задачи о представлении данных с помощью выпуклых многогранников. В первой задаче требуется исключить из конечного множества X точек те из них, которые не являются вершинами многогранника выпуклой оболочки множества X. Разработан алгоритм, основанный на решении серии задач линейного программирования. Его вычислительная сложность асимптотически ниже сложности построения выпуклой оболочки, и ему требуется значительно меньший объем дополнительной памяти, чем при построении выпуклой оболочки. Вторая задача состоит в нахождении минимального подмножества неравенств в системе линейных неравенств, множество решений которого совпадает с множеством решений исходной системы. Показано, что эту задачу можно решать аналогично первой, и алгоритм решения обобщается на случай нелинейных неравенств. Предложены рандомизорованные улучшения обоих алгоритмов.

КЛЮЧЕВЫЕ СЛОВА: линейное программирование, выпуклая оболочка, QuickHull, системы линейных неравенств, экстремальные эллипсоиды, эллипсоид Дикина, Hit-and-run, Billiard walk