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

[ИСН]

Окружность-то? Big deal! Convex hull и там перебор по всем тройкам.
(Хреново, ну дак я и не пытался оптимизировать. Обещан был полиномиальный? - извольте!)

[Spook]

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

ИСН, да, по-видимому, надо строить выпуклую оболочку, сейчас как раз читаю про алгоритм просмотра Грэхема.

[ИСН]

Не надо никакой оболочки, можно проще. Берём три первые точки. Строим описанную окружность. И идём по всем остальным точкам. Если какая не влезает в окружность - заменяем одну из трёх (тут надо прикинуть, какую именно) на неё, и ползём перебирать сначала.
Думаю, что и это не оптимум.

[ewert]

Spook писал(а):

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

Ну Вы ж критерия минимальности для эллипса не предложили, я и решил сделать вид, что не понял. Для окружности -- дело другое.

ИСН писал(а):

Не надо никакой оболочки, можно проще. Берём три первые точки. Строим описанную окружность. И идём по всем остальным точкам. Если какая не влезает в окружность - заменяем одну из трёх (тут надо прикинуть, какую именно) на неё, и ползём перебирать сначала.
Думаю, что и это не оптимум.

Буквально "описанная окружность" не пройдёт -- представьте себе, что точки на одной прямой. Но вот что можно.

1). Находим две наиболее удалённые друг от друга точки $\vec r_1$, $\vec r_2$ и строим на них окружность как на диаметре длины $D=\Vert\vec r_1-\vec r_2\Vert$. Проверяем, попадают ли все остальные точки в этот круг; если да, то построение закончено.

2). Если нет. Перебираем все тройки точек и пытаемся провести через них окружность; учитываем при этом только те тройки, для которых радиус окружности не превосходит $D$ (это чтоб избежать неприятностей в случаях, когда эти точки оказываются на прямой или близко к этому). Проверяем, попадают ли остальные точки в построенный круг; если нет, то эту окружность отбрасываем.

3). Из всех оставленных окружностей берём ту, что имеет наименьший радиус.

Конечно, алгоритм наверняка не оптимален.

[Cave]

Минимальная окружность ищется со сложностью $O(n)$. По-английский задача называется smallest enclosing circle problem, можно поискать или посмотреть здесь на английском
Более известен алгоритм решения за $O(n\log n)$, он использует диаграмму Вороного (Voronoi diagram) множества точек на плоскости и её построение за такое же время (алгоритм Форчуна - Fortune). Почитать на английском можно в статье Franz Aurenhammer, Rolf Klein - Voronoi Diagrams.

[Spook]

Спасибо, думаю все это можно обобщить и на эллипс.

Добавлено спустя 9 минут 40 секунд:

Cave, а Вы разбирали этот алгоритм? Там учитываются неприятности, про которые говорил ewert?

[Cave]

Spook
Какие неприятности? Я что-то пропустил.
Вообще алгоритмы в информатике обычно решают поставленную задачу, несмотря ни на какие неприятности.
Я диаграмму Вороного лично не строил, но охотно верю, что это делается за указанное время. Исходя из неё решить задачу несложно, это есть в статье отдельным параграфом, прочитайте.
На эллипс конкретно этот метод не обобщается, поскольку явно используется определение окружности и её центра.

[Spook]

Ну я имел ввиду такие возможные ситуации как

ewert писал(а):

...неприятностей в случаях, когда эти точки оказываются на прямой или близко к этому

то есть мне показалось, что может произойти выход за пределы разрядной сетки. Но в принципе - да,

Cave писал(а):

алгоритмы в информатике обычно решают поставленную задачу, несмотря ни на какие неприятности.

Я просто подумал, что Вы уже реализовывали этот алгоритм, вот и решил поинтересоваться. А так - статьи скачал, начал читать.

[Cave]

Spook
Эта "неприятность" свойственна алгоритму, предложенному тов. ewert. В принципе, этот алгоритм считается стандартным, потому что очевиден, платить приходится огромной сложностью по сравнению с возможной - $O(n^4)$.

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

На самом деле, теоретические сложности - это, конечно, здорово и интересно, но на практике они нужны далеко не всегда и потому зачастую представляют собой просто интерес или даже спорт. Понятно, что $O(n)$ является оптимальной сложностью в нашей задаче (нужно же прочитать входные данные хотя бы), поэтому можно считать, что задача решена полностью. Однако константа в $O$ большом наверняка кроется такая, что $\log n$ при разумных значениях $n$ будет не сильно хуже, а возможно и лучше.
Во всяком случае подобные вещи наблюдаются во многих алгоритмах, ближайшие, что приходит на ум, - умножение чисел метотом Карацубы (два $n$-битовых числа можно умножить "в столбик" за время $O(n^2)$, а метод Карацубы позволяет это сделать за $O(n^{\log_2 3)$; впрочем, используя быстрое преобразование Фурье эта задача решается за время что-то вроде $O(n\log n\log\log n)$), поиск $k$-порядковой статистики за линейное время (то есть поиск $k$-го по величине элемента массива; тривиальное решение - отсортировать весь массив за время $O(k\log k)$ и найти искомый элемент оказывается практически наилучшим), Фиббоначиевы кучи (отдельная тема, в двух словах не рассказать). Всё это познавательно, но не всегда практично.

[Spook]

Cave писал(а):

На эллипс конкретно этот метод не обобщается, поскольку явно используется определение окружности и её центра.

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

[ИСН]

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

[Spook]

. Эх, жалко. Хотя в принципе, можно просто перебирать по 4 точки, как ewert писал для окружности.

[Алексей К.]

По 4 точки? Может, по 5 (ведь кр. втор. пор. через 5 точек проводится)? Гиперболы сразу выкидываем?

[Spook]

Алексей К. писал(а):

По 4 точки? Может, по 5 (ведь кр. втор. пор. через 5 точек проводится)? Гиперболы сразу выкидываем?

В этом случае, по-моему, все-таки 4, так как уравнение невырожденного эллипса, оси которого параллельны осям декартовой системе координат имеет вид

$$\frac{(x-x_c)^2}{a^2}+\frac{(y-y_c)^2}{b^2}=1$$

.