Самый простой вариант: сортируете точки по возрастанию расстояния от центра, и для каждой точки по порядку проверяете, останется ли после её добавления многоугольник выпуклым, и не окажется ли внутри многоугольника уже просмотренных, но недобавленных точек. Если всё хорошо - добавляете точку к многоугольнику. Правда, придётся с чего-то начать. Самая очевидная кандидатура - треугольник из триангуляции Делоне, содержащий центр, но его может быть дорого искать.
Другой вариант - динамика по сторонам многоугольника. Сортируете точки по углу, выбираете отрезок (A1 A2) такой, что в треугольнике O A1 A2 нет других точек, и двигаетесь по кругу, пытаясь добавлять новые точки - A3, A4 и т.д. Для каждого варианта последней стороны A{k-1} Ak считаете наилучшее значение характеристики, которую оптимизируете (число вершин или площадь). Когда (если) многоугольник замкнётся - сравниваете его с оптимальным.
К сожалению, придётся перебрать все стартовые стороны. Можно ограничиться теми, которые пересекаются лучом Ox - хотя бы одна такая сторона в многоугольнике должна быть.
Оценка сложности - N^5.
UPD. Если внешний цикл вести не по отрезку (A1 A2), а по самой правой точке строящегося контура, то сложность уменьшится до N^4.
