Минимальная охватывающая окружность

[shtirlitz111]

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

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



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

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

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

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

[Sonic86]

Алгоритм по ссылке, если честно, не читал.

shtirlitz111 в сообщении #517270 писал(а):

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

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

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

shtirlitz111 в сообщении #517270 писал(а):

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

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

[eugrita]

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

[nikvic]

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