Предыдущий ответ действительно хорош.
У меня появилась ещё одна идейка. Решение не идеальное, но как знать, может дать неплохие результаты…
1) Все точки упорядочиваем по расстоянию от начала координат (x^2+y^2).
2) Дальше проходим упорядоченный массив ещё раз, рассчитывая суммарное расстояние между каждыми тремя соседними точками в массиве (периметр треугольника). Тройка с минимальным периметром даст искомый треугольник.
Здесь, если не ошибаюсь, вообще получается O(n).
Да, сама по себе сортировка — не O(n), а медленнее. Для оптимизации можно изначально делать массив сортированным, т.е. вставлять точки в нужный элемент, это чуть ускорит.
Конечно, способ определения не точный (наверняка какие-то треугольники будут «съедены», но поскольку вам надо «быстро» — O(n) — возможно, неплохой вариант. Как думаете?