Всем привет!

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


Рекомендуют использовать алгоритм поиска двух наиболее близких точек на плоскости (Описан тут), но я пока не придумал куда его прикрутить.


Любые идеи, ссылки приветствуются. Спасибо.

"Метод наименьших отклонений".

Гы... Зачет?
 Рассмотрим 2 точки. если прямая расположена между ними, то сумма перпендикуляров наименьшая и не изменяется. Можно на досуге подоказывать...
Итого решение - делим все точки на 2 равные половины. одна половина лежит выше другой. проводим прямую между половинами. Если количество точек нечетно - выделяем точку прямо "типо по центру" и проводим прямую по ней...

Гугл нашел только твой пост, может есть другое название?



Ну, если бы все так просто  Это я сам уже придумал. Мне смутила подсказка про "алгоритм поиска двух наиболее близких точек на плоскости".

Я, наверное, немного не так написал в первом посте. Мне интересно как можно использовать алгоритм про две точки в этой задаче. В этом основная проблема.




Лабу помогаю сделать.

Пудрют мозги? Либо так, либо условие неполное  Вроде по этому условию решение такое и есть...

Ок, попытаюсь ща найти что-нибудь в условии. Спасибо.

Добавлено через 45 секунд

Все может быть ))

метод наименьшх квадратов

Бред. 

Возьми метод наименьших квадратов - конкретно АНАЛИТИЧЕСКОЕ получение выражения для подсчета k и b через соотв. суммирование. Потом проделай ТО ЖЕ САМОЕ, но минимизируя не сумму квадратов, а сумму абсов отклонений от регрессионного уравнения y=k. И получишь аналитическое выражение для расчета этого самого k.
Если же тебе достаточно численного решения, без аналитики - Экселевский "поиск решения" щелкает такие задачки как орехи.

?
если мы отобразим все множество наших точек на прямую Y и будем решать ту-же задачу для прямой это будет бредом? 

Пусть для начала, количество точек четно. Разделим точки на 2 равных по количеству множества (Y и Z), все элементы первого лежат не "ниже" всех элементов второго. 

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

Итого - Нужно минимизировать выражение СУММА(abs(Y[]-X))+ СУММА(abs(Z[]-X))

Для этого выберем по одной точке из первого и второго множества, возьмем первую по счету пару и убедимся, что это так... Показывается перебором возможного расположения x y и z.
Возьмем вторую, третью и т.д пары

Получим, что конструкция abs(Y[n]-X)+abs(Z[n]-X) уже минимизирована. Сложив все такие уже минимизированные конструкции получим, что искомое выражение таки уже  минимизировано...

В каком месте наблюдается бред?

У меня. Просто в другом форуме буквально день назад была та же задача - но с минимизацией суммы квадратов отклонений. Вот и ляпнул не подумав.

Приношу извинения. 

А я  уже минут 10 чесал репу над твоим постом   


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


ksnk, 
Akina, 
спасибо.