2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

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



Начать новую тему Ответить на тему
 
 Минимальная охватывающая окружность
Сообщение19.12.2011, 17:43 


19/12/11
1
Добрый день! Не могли бы вы подсказать один момент в алгоритме?
Нам дан алгоритм для нахождения минимальной охватывающей окружности (который выполняется за время О(n^2):
http://www.personal.kent.edu/~rmuhamma/Com...r/centercli.htm

На шаге 4 мы получаем две точки, принадлежащие окружности. И в случае, когда у окружности имеется свободная дуга, на которой не лежит ни одна из опорных точек, и эта дуга размером больше половины окружности, мы должны уменьшить диаметр окружности:

Изображение

в данном случае, у нас это дуга с точками на конце A и B. Строим перпендикуляр к АВ от центра текущей окружности. И нам нужно идти по нему от точки О2 до S, уменьшая радиус окружности до тех пор, пока она не пересечёт ещё одну, третью точку. А если этого не произойдёт, то АВ это и будет диаметр искомой окружности.

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

Подскажите, пожалуйста, как в этом случае нужно правильно формально поставить задачу для нахождения этой самой точки? А в случае её отсутствия показать, что такой точки нет?

Заранее спасибо!

 Профиль  
                  
 
 Re: Минимальная охватывающая окружность
Сообщение20.12.2011, 12:42 
Заслуженный участник


08/04/08
8556
Алгоритм по ссылке, если честно, не читал.
shtirlitz111 в сообщении #517270 писал(а):
в данном случае, у нас это дуга с точками на конце A и B. Строим перпендикуляр к АВ от центра текущей окружности. И нам нужно идти по нему от точки О2 до S, уменьшая радиус окружности до тех пор, пока она не пересечёт ещё одну, третью точку. А если этого не произойдёт, то АВ это и будет диаметр искомой окружности.

Но если просто идти по отрезку и подбирать подходящую точку, такой алгоритм нельзя будет запрограммировать.
Почему? Просто так можно закодить численный метод бисекций: т.е. делим пополам отрезок, выбираем нужный, нужный отрезок делим пополам, выбираем снова нужный и т.п. - это будет $O(\ln n)$ операций.

shtirlitz111 в сообщении #517270 писал(а):
Подскажите, пожалуйста, как в этом случае нужно правильно формально поставить задачу для нахождения этой самой точки? А в случае её отсутствия показать, что такой точки нет?
Формально можно так: даны точки $A,B,C$ окружности (вроде даже симметричным образом). Найти окружность, проходящую через все 3 точки. Наверное, здесь нужно похимичить с простыми соотношениями между сторонами и углами.

 Профиль  
                  
 
 Re: Минимальная охватывающая окружность
Сообщение16.11.2013, 10:11 


15/04/10
985
г.Москва
Алгоритм должен включать 2 основных блока
1) перебор по тройкам всего множества точек, построении окружностей по 3 точкам и проверке условия принадлежности остальных.
2)поиск 1 (или нескольких) мах удаленных точек (диаметра множества),
построением на найденных как на диаметре окружностей и опять таки с последующей проверкой на включение остальных точек.

 Профиль  
                  
 
 Re: Минимальная охватывающая окружность
Сообщение16.11.2013, 11:51 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Я бы начал с построения выпуклой оболочки (быстрее квадрата числа точек). Далее - точки на концах диаметра.
И сравнение углов, под которыми виден диаметр.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group