Я ищу алгоритм (и, возможно, реализацию, которую я могу вызвать из python), решающую следующую проблему:
Учитывая набор S из N точек (N порядка 1000) в многомерном пространстве (размерность d порядка 10-500), я хотел бы найти наименьший выпуклый многогранник с M вершинами, такой, что каждая точка в S находится внутри многогранника. Таким образом, этот многогранник будет внешним приближением выпуклой оболочки только с M вершинами.
Для больших M этот многогранник по сути является выпуклой оболочкой, которую я могу найти с помощью следующего кода:
import numpy as np
S=np.random.rand(N,d)
hull=ConvexHull(S)
result=hull.vertices
Это очень медленно или не хватает памяти для вида N и d, которые меня интересуют, поэтому мне было бы интересно узнать, существуют ли более оптимизированные библиотеки для этой проблемы. Я сам реализовал решение с помощью линейного программирования, но оно имеет те же проблемы и намного медленнее.
Для моей цели может быть достаточно приближения с меньшим М, но я не нашел алгоритм, решающий эту проблему, возможно, потому что я не знаю правильной терминологии.