Дано n точек на плоскости. № 3 коллинеарны.

Учитывая число к.

Найдите подмножество из k точек, такое, что выпуклая оболочка из k точек имеет минимальный периметр из любой выпуклой оболочки из подмножества из k точек.

Я могу думать о наивном методе, работающем в O (n ^ k k log k). (Найдите выпуклую оболочку каждого подмножества размера k и выведите минимум).

Я думаю, что это проблема NP, но я не могу найти ничего подходящего для сокращения.

У кого-нибудь есть идеи по этой проблеме?

Пример,

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

Результат:

{(0,0),(0,1),(1,0)}

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