Laplace

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

Можно посчитать все расстояния (N² и ассоциировать эти расстояния с обеими точками (2N памяти), можно с сортировкой по возрастанию.

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

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