|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 25 Jan 2002 06:13:43
To : Aleksey Nilov
Subject : Re: Еще одна задачка...
--------------------------------------------------------------------------------
"Aleksey Nilov" <Aleksey.Nilov@p18.f14.n5038.z2.fidonet.org> wrote in
message news:1011891044@p18.f14.n5038.z2.ftn...
> Hа пpоскости набpосаны N точек (известны их кооpдинаты Xk, Yk)
> Тpебуется найти площадь наименьшего кpуга, содеpжащего все эти точки...
> Сложность - меньше O(N^4) - для случая O(N^4) - все элементаpно...
Обсуждалось здесь с месяц назад. Поищи, может есть
в архивах (2 - 4 декабря) Были указаны указаны ссылки на
алгоритмы где то в инете, утверждалось, что сложность O(N)
Я тестировал такой доморощенный алгоритм:
1) Строится алгоритм построения окружности охватывающей
небольшое число точек. В лоб. Проводятся окружности через
все пары точек и проверяется охват, и потом через все тройки
точек - и кроме проверки охвата ищется минимальный радиус.
2) Выбирается этот самый малый набор точек:
2.1 берем произвольную точку
2.2 добавляем наиболее от нее удаленную
2.3 строим по выбранным точкам охватывающую окружность (по алгоритму 1)
2.4 добавляем к выбранным точкам наиболее удаленную от центра этой
окружности
2.5 если расстояние до этой точки больше радиуса - переходим к 2.3
Hа простых тестах до 500000 точек, у меня было от 4 до 9 таких итераций до
построения окончательной окружности.
Доказательства скорости сходимости нет, но для практики достаточно.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Еще одна задачка... 