ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     04 Dec 2001  04:05:26
 To : Boris Sivko
 Subject : Re: Задачка: Точки на плоскости
 -------------------------------------------------------------------------------- 
 

 "Boris Sivko" <Boris.Sivko@p14.f26.n452.z2.fidonet.org> wrote in message
 news:1007413087@p14.f26.n452.z2.FIDOnet.ftn...
 
 >  MN>> Плоскость заполнена точками со случайными координатами
 >  MN>> (количество точек конечно). Ограничить их окружностью с
 >  MN>> минимальным радиусом.
 >  NS> Введем функцию R(x,y) где x,y координаты центра, R максимальное
 >  NS> расстояние точек от (x,y). Смотрим значение и градиент этой функции в
 >  NS> крайних точках. Функция кусочно-линейна(?), можно смело спуститься по
 >  NS> градиенту.
 >
 >   Ты представляешь, что это за функция будет при 100 точках? И скока
 
 времени
 
 > она будет вычислятся?
 >
 >   Идея 1(мини-ускоритель): ограничиваем все точки
 
 многоугольником(выпуклым) и
 
 > работаем только с точками, которые являются вершинами многоугольника.
 >
 >   Идея 2(решение):
 >   Основывается на утверждении, что решение является окружностью, описанной
 > вокруг трёх точек(как минимум). Действительно, если опишем окружность
 
 через 2 и
 
 > менее точки, то мы можем смело как-то уменьшить ответный радиус, т.к. для
 
 этих
 
 > двух все остальные находятся внутри данной.
 
 Для ромба, например, охватывающая окружность минимального радиуса
 проходит через _две_ наиболее удаленные точки.
 
 >   Остаётся перебрать все тройки точек многоугольника.
 
 Это вроде O(N^3). И даже с преоложенным ускорителем
 для большого числа точек может работать медленно.
 
 Могу предложить свой вариант:
 
 1) Берем одну точку (если и одной нет то ошибка)
 и проводим через нее окружность.
 Заносим эту точку в стек "определяющих" точек.
 
 2) Ищем точку не принадлежащую кругу построенному
 на "определяющих" точках, если нет - то заканчиваем.
 По-видимому, будет быстрее сходиться, если сразу
 искать наиболее удаленную от текущего центра точку.
 
 3) Берем найденную точку и добавляем к "определяющим"
 и перестраиваем окружность так, чтобы она охватывала все
 "определяющие" точки.
 Те из "определяющих" точек которые попадут внутрь -
 выбрасываем из "определяющих". Хотя для устойчивости
 их можно, и даже, наверное, следует, держать в списке
 "определяющих". Хотя, возможно, не все ... :)
 
 4) переходим к 2.
 
 Hа нескольких тысячах точек должно сходится за <10 итераций.
 Hаибольшая сложность здесь - реализация шага 3.
 Это в принципе эта же самая задача, но на малом числе точек.
 
 Cheers,
 Serge
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Задачка: Точки на плоскости   Serge Kanilo   04 Dec 2001 04:05:26   Задачка: Точки на плоскости   Boris Sivko   04 Dec 2001 13:30:48