333
правки
Изменения
→Корректность алгоритма
==Корректность алгоритма==
Попробуем разобраться почему этот алгоритм действительно находит искомую окружность.
Докажем несколько вспомогательных лемм. Для удобства введем общие обозначения. Пусть <tex> P </tex> и <tex> R </tex> - два '''непересекающихся''' множества точек на плоскоти, Пусть <tex> p </tex> - некоторая точка из множества <tex> P </tex>.
{{Лемма
|id= ==lemma==
|about=лемма 1
|statement=
Окружность минимального радиуса, содержащая все точки <tex> P </tex> внутри себя и все точки <tex> R </tex> на границе ''уникальна''.
|proof=
Пусть это не так и существует две такие окружности <tex> D_0 </tex> и <tex> D_1 </tex>. Очевидно, что в таком случае все точки из <tex> P </tex> должны лежать внутри <tex> D_0 \cap D_1 </tex>. Пусть <tex> z </tex> - точка пересечения окружностей (смотри рисунок). [[Файл:MiniDisc.jpg]]
}}
{{Лемма
|id= ==lemma==
|about=лемма 1
|statement=
Условие
|proof=
БЛАБЛАБЛА
}}
{{Лемма
|id= ==lemma==
|about=лемма 1
|statement=
Условие
|proof=
БЛАБЛАБЛА
}}
==Память и время работы ==
