Я ищу алгоритм для нахождения наибольшего подмножества точек (по наибольшему я имею в виду число), которые образуют выпуклый многоугольник из данного набора точек. Я думаю, что это может быть решено с помощью DP, но я не уверен. Возможно ли сделать это в O (n ^ 3)? На самом деле мне просто нужен размер наибольшего подмножества, поэтому для него не нужно иметь уникальное решение

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

просто чтобы сохранить это простым,

Заданный вход: набор точек в 2D

Желаемый результат: максимальное количество точек, которые образуют выпуклый многоугольник, как в примере, выходное значение равно 5 (ABHCD является одним из возможных выпуклых многоугольников)

Есть похожая проблема spoj.com/problems/MPOLY, которая решается с помощью DP в O (N ^ 3), мой вопрос об обобщении этой проблемы, которая не должна содержать (0,0)