Выбрать по координатам наименьшее расстояние

Господи, баянистая же задачка по алгоритмическому программированию.
Разбили точки на две половины с одинаковым количеством точек вертикальной прямой. Рекурсивно нашли ответ для двух половин — пусть такой минимальный периметр по двум половинам равен 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))

Интересная задача… Тоже буду ждать ответов, т.к. кроме тупого перебора в голову ничего не приходит…

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

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

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

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

Чем конкретнее задача, тем лучше ее можно оптимизировать.

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

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

точки задаются вот так вот 3<N<=100000, а времени мало, поэтому перебором, увы никак.

да забыл добавить равномерность не гарантируется. Но координаты ограничены прямоугольником допустим от -1 000 000 до 1 000 000 по X и по Y

таблица получится 10^9 ячеек памяти, чтобы это заполнить уйдет слишком много времени. Хотелось бы найти алгоритм не требующий перебора всех расстояний между координатами. Наверняка подобная задача человечеством уже решалась не однократно. Может какую-нить книжку кто посоветует?

Предыдущий ответ действительно хорош.

У меня появилась ещё одна идейка. Решение не идеальное, но как знать, может дать неплохие результаты…
1) Все точки упорядочиваем по расстоянию от начала координат (x^2+y^2).
2) Дальше проходим упорядоченный массив ещё раз, рассчитывая суммарное расстояние между каждыми тремя соседними точками в массиве (периметр треугольника). Тройка с минимальным периметром даст искомый треугольник.

Здесь, если не ошибаюсь, вообще получается O(n).
Да, сама по себе сортировка — не O(n), а медленнее. Для оптимизации можно изначально делать массив сортированным, т.е. вставлять точки в нужный элемент, это чуть ускорит.

Конечно, способ определения не точный (наверняка какие-то треугольники будут «съедены», но поскольку вам надо «быстро» — O(n) — возможно, неплохой вариант. Как думаете?