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

Конспект не готов.

Описание

Минимальная охватывающая окружность множества точек (smallest enclosing disc) - это задача, в которой необходимо по заданному набору точек найти окружность минимального радиуса, которая содержит все точки множества.

Алгоритм

Сперва приведем алгоритм, корректность которого позднее будет доказана.

Рассмотрим метод [math] MinDisc [/math], который будет принимать на вход множество точек, а возвращать будет искомую охватывающую окружность. Идея метода в том, что он генерирует случайную перестановку из точек, которые поступили на вход и в получившимся порядке по одной добавляет их в текущую охватывающую окружность. Как будет доказано позднее, если на каком-то шаге алгоритма текущая точка оказалась вне текущей минимальной окружности, то утверждается, что она лежит на границе новой окружности, которая будет содержать в себе ее и все предыдущие точки. Опишем приведенный выше алгоритм псевдоком:

MinDisc(S)
   Let P - random permutation of S
   Let D2 - be the smallest enclosing disc for {p1, p2}.
   for i = 3 to n {
       if pi [math] \in [/math] Di−1  then Di = Di−1 // point is inside. nothing to do here
                     else Di = MinDiscWithPoint ({p1,...,pi−1}, pi) // point is lying on the boundary of minimal circle
   }
   return Dn

Как вы заметили, мы использовали выше метод [math] MinDiscWithPoint [/math] - это метод, который по множеству точек и еще одной точке возвращают искомую окружность. При этом выделенная точка (которая передается в качестве второго аргумента) обязательно лежит на окружности. Эта функция очень похожа на предыдущую, поэтому приведу лишь ее псевдокод:

MinDiscWithPoint(S, q)
   Let P - random permutation of S
   Let D1 - be the smallest enclosing disc for {p1, q}.
   for i = 2 to n {
       if pi [math] \in [/math] Di−1  then Di = Di−1 
                     else Di = MinDiscWith2Points ({p1,...,pi−1}, pi, q) 
   }
   return Dn

Как и в предыдущем случае мы использовали новый метод. [math] MinDiscWith2Points [/math] аналогичен [math] MinDiscWithPoint [/math], но в нем уже передается две точки, которые будут лежать на построенном окружности. В этой функции шафлить инпут не требуется. Опишем его псевдоком:

MinDiscWith2Points(P, q1, q2)
   Let D0 - be the smallest enclosing disc for {q1, q2}.
   for i = 1 to n {
       if pi [math] \in [/math] Di−1  then Di = Di−1 
                     else Di = сircumcircle (прим. описанная окружность) of a triangle {pi, q1, q2} 
   }
   return Dn

Как мы видим больше подобных шагов делать не нужно, так как если известно, что три точки лежат на некоторой окружности, то они однозначно ее задают.

Корректность алгоритма

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

Докажем несколько вспомогательных лемм. Для удобства введем общие обозначения. Пусть [math] P [/math] и [math] R [/math] - два непересекающихся множества точек на плоскоти, Пусть [math] p [/math] - некоторая точка из множества [math] P [/math].

Лемма (лемма 1):

Окружность минимального радиуса, содержащая все точки [math] P [/math] внутри себя и все точки [math] R [/math] на границе уникальна.

Доказательство:

[math]\triangleright[/math]

Пусть это не так и существует две такие окружности [math] D_0 [/math] и [math] D_1 [/math]. Очевидно, что в таком случае все точки из [math] P [/math] должны лежать внутри [math] D_0 \cap D_1 [/math]. Пусть [math] z [/math] - точка пересечения окружностей (смотри рисунок).

[math]\triangleleft[/math]

Лемма (лемма 1):

Условие

Доказательство:

[math]\triangleright[/math]

БЛАБЛАБЛА

[math]\triangleleft[/math]

Лемма (лемма 1):

Условие

Доказательство:

[math]\triangleright[/math]

БЛАБЛАБЛА

[math]\triangleleft[/math]

Источники

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars-Computational Geometry Algorithms and Applications, p. 86