Выпуклый корпус, состоящий из макс. n баллов

Возможно, вам подойдет следующий подход: сначала вычислите выпуклую оболочку H. Затем выберите подмножество точек n случайным образом из H, который строит новый многоугольник, который может не покрывать все точки, поэтому назовем его квазивыпуклой оболочкой Q. Подсчитайте, сколько точек содержится в Q (инлайнеры). Повторите это определенное количество раз и оставьте предложение Q с наибольшим количеством вставок.

Это кажется немного связанным с RANSAC, но для этой задачи у нас нет представления о том, что такое выброс, поэтому мы не можем реально оценить коэффициент выбросов. Следовательно, я не знаю, насколько хорошим будет приближение или сколько итераций вам нужно, чтобы получить разумный результат. Может быть, вы можете добавить некоторые эвристики вместо того, чтобы выбирать точки n чисто случайным образом, или вы можете установить пороговое значение того, сколько точек должно по крайней мере содержаться в Q, а затем остановиться, когда вы достигнете этого порога.

Редактировать

На самом деле, подумав об этом, вы могли бы использовать подход RANSAC:

max_inliers = 0
best_Q = None
while(true):
    points = sample_n_points(X)
    Q = construct_convex_hull(points)
    n_inliers = count_inliers(Q, X)
    if n_inliers > max_inliers:
        max_inliers = n_inliers
        best_Q = Q
    if some_condition:
        break

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

Пара идей.

1. Точки, которые мы исключаем при удалении вершины, лежат в треугольнике, образованном этой вершиной и двумя смежными с ней вершинами на выпуклой оболочке. Удаление любой другой вершины не влияет на набор потенциально исключаемых точек. Таким образом, нам нужно всего лишь дважды пересчитать покрытие для каждой удаленной вершины.

2. Говоря о пересчете покрытия, мы не обязательно должны рассматривать каждую точку. Эта идея не улучшает худший случай, но я думаю, что на практике это должно быть большим улучшением. Поддерживайте индекс точек следующим образом. Выберите случайную вершину, которая будет «корнем», и сгруппируйте точки, по которым треугольник, образованный корнем, и две другие вершины содержат их (время O (m log m) с хорошим алгоритмом). Всякий раз, когда мы удаляем некорневую вершину, мы объединяем и фильтруем два набора точек для треугольников, включающих удаленную вершину. Всякий раз, когда мы пересчитываем покрытие, мы можем сканировать только точки в двух соответствующих треугольниках. Если мы когда-нибудь удалим этот корень, выберем новый и переделаем индекс. Общая стоимость этого обслуживания составит O(m log^2 m) в ожидании, где m — количество баллов. Однако оценить стоимость вычислительного покрытия сложнее.

3. Если точки достаточно равномерно распределены внутри корпуса, можно использовать площадь в качестве прокси для покрытия. Сохраните вершины в очереди приоритетов, упорядоченной по площади их треугольника, образованного их соседями (ухом). Всякий раз, когда мы удаляем точку, обновляем область уха двух ее соседей. Это алгоритм O (m log m).

Следующее не решает вопрос в том виде, в каком я его сформулировал, но решает проблему, породившую вопрос. Поэтому я хотел добавить его на случай, если кто-то еще столкнется с чем-то подобным.

Я исследовал два подхода:

1) Рассматривает выпуклую оболочку как многоугольник и применяет к ней алгоритм упрощения многоугольника. Конкретным алгоритмом, который я исследовал, был Алгоритм Рамера-Дугласа-Пекера.

2) Применить алгоритм, описанный в вопросе, без пересчета выпуклой оболочки.

Оба подхода не дадут вам (насколько я могу судить) желаемого решения поставленной задачи оптимизации, но для моих задач они работали достаточно хорошо.