Выбрать по координатам наименьшее расстояние
Господи, баянистая же задачка по алгоритмическому программированию.
Разбили точки на две половины с одинаковым количеством точек вертикальной прямой. Рекурсивно нашли ответ для двух половин — пусть такой минимальный периметр по двум половинам равен P.
Осталось разобрать треугольники, у которых одна вершина в одной половине, а две других — во второй. Нам достаточно рассматривать только точки на расстоянии <= P / 2 от прямой деления. 
Теперь идём по точкам в этой полосе сверху вниз, поддерживая набор точек, которые находятся по вертикали от нашей на расстоянии не более P / 2. Т. е. идём эдаким плывущим окошком ширины P / 2 — получаются два вида событий — точка попала внутрь окна и точка вышла из окна. 
Если внутри окна не существует треугольника, который периметром меньше P, то в этом окне (навскидку) никак не может быть больше 7 точек (раз окно — прямоугольник P x P / 2). Эти 7 точек можно уже за кубическую сложность перебрать. Иначе там обязательно есть треугольник периметром меньше P, на который мы наткнёмся. Каждый раз, натыкаясь на такой треугольник будем попросту уменьшать P до нового значения.

Тем самым, получился алгоритм со сложностью, удовлетворяющей оценке T(n) = 2T(n / 2) + O(nlogn), решением которой является O(n*log^2(n))
Чем конкретнее задача, тем лучше ее можно оптимизировать.

Например, если заранее известно, что точки равномерно разбросаны на плоскости (ограничены прямоугольником), и при этом точек очень много (иначе проще перебором), то первое, что приходит в голову, — разбить плоскость на зоны. Например, точек около 10.000, и мы делим прямоугольник на шахматную доску 10х10 клеток. В каждой клетке окажется примерно 100 точек. Далее обсчитываем не полный набор вариантов, а лишь соседние клетки. Т.е. получается уже не (10.000*9999*9998)/2 вариантов, а всего лишь (10.000*900*899)/2. Это грубый пример, но на нем видно, что эта оптимизация не универсальна, — здесь использовались два уточнения, т.е. задача более узкая.

В общем, нужно больше конкретики.