Аппроксимация прямой на плоскости

[Алексей К.]

А мне эта задачка часто к слову приходится: совсем недавно --- по поводу кв. уравнения типа $x^2-100.01x+1=0$ попаясничал:

Цитата:

Кабы этот случай не приключился бы со мной в реальном программировании, я бы о нём и не знал. А программировал я только реальную жизнь: прямоугольные пакеты с молоком, соком или вином пользуете? (Упаковочная машина, деталька от неё, проверка допуска прямолинейности, задача на собственные значения, кв. уравнение именно такого типа; маленький корень равен нулю, если фрезеровщик совсем не пил).

Когда-то казалось, что жизнь состоит из МНК --- миллионы снимков с пузырьковых камер, допуски и посадки, ещё чо-то... Но прошло вроде... Иногда какие-то реминисценции... Впрочем,

и ewert в самом начале писал(а):

Задачка вполне практическая.

[Spook]

ewert, решения будут показаны?

[ewert]

не знаю, может, народ хочет ещё помучиться. А то все жалуются: школьные, школьные, а как до дела -- ни гу-гу...

[worm2]

Дык решены же уже на этом форуме.
Я же ссылку уже кидал (по 1-й задаче). Она элементарно сводится к этой.
А 3-я вот здесь рассмотрена.

[ewert]

worm2 писал(а):

Дык решены же уже на этом форуме.
Я же ссылку уже кидал (по 1-й задаче). Она элементарно сводится к этой.
А 3-я вот здесь рассмотрена.

Хм.
Там обсуждалась не первая задача, и к этой она не сводится (т.к. к эта относится к точкам на прямой).
Здесь действительно рассмотрена 3-я, только я чего-то перестал понимать:

worm2 писал(а):

Да вроде "просто": найти минимальную по длине проекцию выпуклой оболочки точек и через её середину восстановить перпендикуляр...

-- как конкретно Вы предлагаете искать "минимальную по длине проекцию"?

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

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

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

Задача 2 (минимизируем сумму квадратов расстояний).
В принципе, Алексей К. изложил правильное решение. Я только приведу его обобщение на произвольные размерности.

Пусть есть $N$ точек: $\{\vec x_k\}_{k=1}^N$, где каждая $\vec x_k\equiv(x_k^1,x_k^2,\dots,x_k^d)$, $d$ -- размерность пространства. Требуется провести между ними линейное многообразие размерности $r$ ($1\leqslant r<d$) так, чтобы сумма квадратов расстояний от него до этих точек была минимальна.

Решение. Многообразие фиксируется своей "точкой привязки" и направлением. В качестве точки привязки может служить центр масс. Будем считать, что из всех координат уже вычтены координаты центра масс, т.е. что центр масс уже сдвинут в начало. Далее, образуем матрицу $G$ с элементами:

$$ g_{ij}\equiv\sum_{k=1}^Nx_k^i\cdot x_k^j $$

и назовём её матрицей Грама (почему бы и нет?). Размер матрицы совпадает с размерностью исходного пространства.

Тогда искомым подпространством будет спектральное подпространство матрицы Грама размерности $r$, отвечающее соответствующему количеству (с учётом кратности) наибольших чисел этой матрицы. Или, другими словами: базисом в этом подпространстве будут собственные вектора, отвечающие наибольшим собственным числам.

Или, что эквивалентно: ортогональное дополнение к искомому подпространству натянуто на собственные вектора, отвечающие наименьшим собственным числам. Как выгоднее считать -- зависит от того, к чему ближе $r$: к единице или к $d$.

Решение единственно ровно настолько, насколько однозначно определяется спектральное подпространство. Т.е. насколько вырожденным будет собственное число, попадающее на границу. В частности, если все собственные числа простые, то решение заведомо единственно.

[worm2]

ewert писал(а):

я писал(а):

Я же ссылку уже кидал (по 1-й задаче). Она элементарно сводится к этой.
А 3-я вот здесь рассмотрена.

Хм.
Там обсуждалась не первая задача, и к этой она не сводится (т.к. к эта относится к точкам на прямой).

Ну да. С "элементарно сводится" я, конечно, переборщил . Имелось в виду, что если известно направление прямой, то рассматриваем проекцию точек на нормаль к этому направлению, и тогда таки да, задача свелась к точкам на прямой. Но это оптимальное направление ещё нужно найти. Впрочем, так же как и здесь:

ewert писал(а):

я писал(а):

Да вроде "просто": найти минимальную по длине проекцию выпуклой оболочки точек и через её середину восстановить перпендикуляр...

-- как конкретно Вы предлагаете искать "минимальную по длине проекцию"?

Поэтому "просто" и в кавычках
Но, возможно, найдётся способ поискать эту минимальную проекцию по скорости лучший, чем $O(n^3)$.
По крайней мере, мне кажется, что достаточно перебрать (в качестве кандидатов на проецирующие направления) нормали ко всем сторонам выпуклой оболочки, что уже даёт $O(n^2)$

[ewert]

worm2 писал(а):

Но, возможно, найдётся способ поискать эту минимальную проекцию по скорости лучший, чем $O(n^3)$.

А почему эн именно в кубе? Мой вариант требует порядка эн в четвёртой, а (видимо) оптимальный -- эн квадрат...

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

--------------------------
поправку заметил

[worm2]

ewert в сообщении #136108 писал(а):

А почему эн именно в кубе? Мой вариант требует порядка эн в четвёртой, а (видимо) оптимальный -- эн квадрат...

Ну, средняя линия всегда параллельна какой-либо прямой, проходящей через 2 точки. Для каждой из таких прямых можно заранее вычислить пару точек, максимально удалённых от неё (с одной и с другой стороны) за $O(n^3)$ операций. Сумма этих максимальных расстояний не меняется при переходе от прямой, проходящей через 2 точки, к средней линии треугольника, которая ей параллельна.

[ewert]

worm2 писал(а):

Ну, средняя линия всегда параллельна какой-либо прямой, проходящей через 2 точки. Для каждой из таких прямых можно заранее вычислить пару точек, максимально удалённых от неё (с одной и с другой стороны) за $O(n^3)$ операций. Сумма этих максимальных расстояний не меняется при переходе от прямой, проходящей через 2 точки, к средней линии треугольника, которая ей параллельна.

Да, это правда, при таком способе перебора действительно понадобится $O(n^3)$, только я не понял, при чём тут сумма.

[worm2]

Ой, про сумму стормозил. Важно, что максимальным будет расстояние до одной из этих двух точек. А сумма здесь действительно ни при чём.

[ewert]

ну тогда ещё два ньюанеца.

Во-первых, зачем перпендикуляры -- средняя линия и есть средняя линия.

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

[Spook]

А если я ищу не прямую, а кривую (тоже на плоскости)? Например, эллипс, причем минимальный и включающий в себя все данные точки. Остается только перебор?

[ИСН]

О! Вы ведь, наверное, понимаете, какие бездны стоят за этим скромным "например"? Будут кривые, с которыми повезёт найти полиномиальный алгоритм (уж окружность-то наверняка, а с ней, может быть, и эллипс...), а будут такие, с которыми всё плохо... совсем плохо!

[Spook]

Ну,хотя бы окружность.

[ewert]

Spook писал(а):

Например, эллипс, причем минимальный и включающий в себя все данные точки. Остается только перебор?

Нет, не обязательно только, возможны и ещё варианты. Что, например, если точки не лежат на том эллипсе? -- тогда остаётся только застрелиться.