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

Question

[ztarlitz]

Подскажите какой-нибудь алгоритм, который выберет из массива координат(х, у) три координаты, которые образуют треугольник наименьшего периметра.

PS В массиве координаты могут совпадать, и треугольник может быть с нулевой площадью.

Answer 1

[Zlobober]

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

Comments

[Zlobober]

А если ещё чуть-чуть подумать, то можно понять, что каждый раз пересортировывать необязательно — достаточно в начале посортировать точки двумя способами — по горизонтали и по вертикали. Тем самым получился алгоритм с оценкой T(n) = 2T(n / 2) + O(n), т. е. T(n) = O(nlogn).

[ztarlitz]

Чувак, хер с этими минусовщиками, я вообще не понимаю зачем этот рейтинг нужен?

Спасибо огромное за решение правда очень помог, ну а то что алгоритм боянист, так не суди строго, всего знать не получается))

Answer 2

[simplecode]

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

Answer 3

[Laplace]

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

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

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

Answer 4

[Laplace]

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

Answer 5

[dollar]

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

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

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

Comments

[artyomst]

если разбить плоскость на несколько то может получится, что граница плоскости разобъет наименьший треугольник.

[dollar]

Во-первых, рассматриваются плоскости, включая соседние (читайте внимательнее, пожалуйста, прежде чем комментировать).
Во-вторых, это лишь пример алгоритма, не претендующий на решение и указывающий на то, что задача слишком общая.

Answer 6

[ztarlitz]

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

Answer 7

[ztarlitz]

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

Answer 8

[ztarlitz]

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

Answer 9

[mt_]

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

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

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

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

Comments

[ztarlitz]

Увы, такой алгоритм работать не будет.

[mt_]

Почему?

[ztarlitz]

Ближайшие точки в списке не обязательно будут составлять треугольник с мин. периметром.

[Zlobober]

На самом деле… на самом деле известен такой факт, что, например, среди миллиона точек найти пару кратчайших можно некоторым хаком следующего вида: посортировали все точки по расстоянию от случайной далёкой-далёкой точки. А потом ищем пару кратчайших среди пар точек, находящихся на расстоянии не более чем K в этой сортировке. На практике оказывается, что ответ всегда находится точно при K <= 25.

Тут может сработать схожий прикол. Надо бы исследовать…