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

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

Описание

Минимальная охватывающая окружность множества точек (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

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

Источники

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