Каков самый простой способ проверить, находится ли точка P внутри выпуклой оболочки, образованной множеством точек X?
Мне нужен алгоритм, который работает в высокоразмерном пространстве (скажем, до 40 измерений), который явно не вычисляет сам выпуклый корпус. Любые идеи?
Проблема может быть решена путем нахождения допустимой точки линейной программы. Если вас интересует полная информация, а не просто подключить LP к существующему решателю, я бы рекомендовал прочитать главу 11.4 в Boyd and Vandenberghe отличную книгу о выпуклой оптимизации.
Установить A = (X[1] X[2] ... X[n]), то есть первый столбец v1, второй v2 и т.д.
Решите следующую проблему с LP,
minimize (over x): 1
s.t. Ax = P
x^T * [1] = 1
x[i] >= 0 \forall i
где
x^T - это транспонирование x[1] - это вектор all-1.Задача имеет решение, если точка находится в выпуклой оболочке.
Точка лежит вне выпуклой оболочки других точек тогда и только тогда, когда направление всех векторов от нее к этим другим точкам меньше половины окружности/сферы/гиперсферы вокруг нее.
Вам не нужно вычислять само выпуклую оболочку, поскольку это кажется довольно трудным в многомерных пространствах. Там известное свойство выпуклых оболочек:
Любой вектор (точка) v внутри выпуклой оболочки точек [v1, v2, .., vn] может быть представлен как sum(ki*vi), где 0 <= ki <= 1 и sum(ki) = 1. Соответственно, никакая точка вне выпуклой оболочки не будет иметь такого представления.
В m-мерном пространстве это даст нам набор линейных уравнений m с n неизвестными.
изменить
Я не уверен в сложности этой новой проблемы в общем случае, но для m = 2 она кажется линейной. Возможно, кто-то, у кого больше опыта в этой области, исправит меня.
У меня была та же проблема с 16 измерениями. Поскольку даже qhull не работал должным образом, так как слишком много лиц должно было быть создано, я разработал свой собственный подход путем тестирования, можно ли найти разделительную гиперплоскость между новой точкой и справочными данными (я называю это "HyperHull";)),
Задача о нахождении разделительной гиперплоскости может быть преобразована в задачу выпуклого квадратичного программирования (см. SVM). Я сделал это на python, используя cvxopt с менее чем 170 строками кода (включая ввод-вывод). Алгоритм работает без изменений в любом измерении, даже если существует проблема: чем выше размерность, тем выше число точек на корпусе (см. На выпуклой корпус случайных точек в многограннике). Поскольку корпус не сконструирован явно, а проверен только, находится ли точка внутри или нет, алгоритм имеет очень большие преимущества в более высоких измерениях по сравнению с, например, быстрый корпус.
Этот алгоритм может "естественно" распараллеливаться, а ускорение должно быть равно числу процессоров.
Хотя исходный пост был три года назад, возможно, этот ответ по-прежнему будет полезен. Алгоритм Гильберта-Джонсона-Кирти (GJK) находит кратчайшее расстояние между двумя выпуклыми многогранниками, каждое из которых определяется как выпуклая оболочка множества генераторов - в частности, сама вычисленная оболочка не должна вычисляться. В частном случае, о котором идет речь, один из многогранников - это всего лишь точка. Почему бы не попробовать использовать алгоритм GJK для вычисления расстояния между P и выпуклой оболочкой точек X? Если это расстояние равно 0, то P находится внутри X (или, по крайней мере, на его границе). Реализация GJK в Octave/Matlab под названием ClosestPointInConvexPolytopeGJK.m вместе с поддерживающим кодом доступна по адресу http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html. Простое описание алгоритма GJK доступно в разделе Sect. 2 документа, http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf. Я использовал алгоритм GJK для некоторых очень маленьких множеств X в 31-мерном пространстве и имел хорошие результаты. Как производительность GJK сравнивается с методами линейного программирования, которые другие рекомендуют, является неопределенной (хотя любые сравнения были бы интересными). Метод GJK не позволяет вычислять выпуклую оболочку или выражать оболочку в терминах линейных неравенств, которые могут потребовать много времени. Надеюсь, что этот ответ поможет.
Готовы ли вы принять эвристический ответ, который обычно должен работать, но не гарантирован? Если вы тогда, вы можете попробовать эту случайную идею.
Пусть f (x) - куб расстояния до P раз число вещей в X, минус сумма кубов расстояния до всех точек в X. Начните где-нибудь случайным и используйте восхождение на холм алгоритм для максимизации f (x) для x в сфере, очень удаленной от P. За исключением вырожденных случаев, если P не находится в выпуклой оболочке, это должно иметь очень хорошую вероятность найти нормаль к гиперплоскости, на которой P находится одна сторона, и все в X находится на другой стороне.