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

Конспект готов к прочтению.

Описание

Минимальная охватывающая окружность множества точек (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] D(\lambda), 0\lt =\lambda \lt = 1 [/math]. При этом центры этих окружностей лежат на отрезке, соединяющем центры [math] D_0 [/math] и [math] D_1 [/math], и перемещаются очевидным образом в зависимости от параметра [math]\lambda [/math]. При этом радиус каждой из этих окружностей - расстояние от центра до точки [math] z [/math], описанной выше. Рассмотрим окружность [math] D(1/2) [/math]. Заметим, что [math] D_0 \cap D_1 [/math] лежит целиком внутри нее (по построению окружности [math] D(1/2) [/math]), а так как [math] D(1/2) [/math] проходит через пересечение окружностей [math] D_0 [/math] и [math] D_1 [/math], то она проходит через все точки [math] R [/math] (так все точки [math] R [/math] лежат на [math] \partial D_0 \cap \partial D_1 [/math].). Из этого следует, что эта окружность явлется допустимой для нашей теоремы и при этом обладает меньшим радиусом, то наше предположение неверно и искомая окружность единственная. Далее будем называть искомую окружность [math] md(P, R) [/math].

[math]\triangleleft[/math]

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

Если [math] p \in md(P \setminus \{p\}, R) [/math], то [math] md(P, R) = md(P \setminus \{p\}, R) [/math]

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

[math]\triangleright[/math]

Для множества [math] P \setminus \{p\} [/math] справедливо, что для него минимальный диск по определению - это [math] md(P \setminus \{p\}, R) [/math], но так как [math] p [/math] лежит внутри него, то он и является корректным диском для множества [math] P [/math]. Но если бы в [math] P [/math] существовал еще меньший диск, то он бы существовал бы и для [math] P \setminus \{p\} [/math]. Значит эти диски равны(в силу единственности) и [math] md(P, R) = md(P \setminus \{p\}, R) [/math]

[math]\triangleleft[/math]

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

Если [math] p \notin md(P \setminus \{p\}, R) [/math], то [math] md(P, R) = md(P \setminus \{p\}, R \cup {p}) [/math]

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

[math]\triangleright[/math]

Пусть [math] D_0 = md(P \setminus \{p\}, R) [/math] и [math] D_1 = md(P, R) [/math]. Рассмотрим аналогичное семейство множеств [math] D(\lambda) [/math] как в лемме 1. Зададим это семейство с помощью окружностей [math] D_0 [/math] и [math] D_1 [/math]. Заметим, что [math] p \notin D_0 [/math], но [math] p \in D_1 [/math]. Значит найдется такое [math] \lambda [/math], что точка [math] p [/math] лежит на границе окружности [math] D(\lambda) [/math]. Но в таком случае так как эта окружность удовлетворяет условиям теоремы и к тому же обладает не большим радиусом, чем [math] D_1 [/math] (которая в свою очередь является минимальной охватыающей окружностью), то [math] \lambda = 1 [/math]. Это означает, что [math] D(\lambda) = D_1 [/math], то точка [math] p [/math] лежит на границе [math] D_1 [/math], то [math] md(P, R) = md(P \setminus \{p\}, R \cup {p}) [/math].

[math]\triangleleft[/math]

Эти три доказанные леммы полностью подтверждают корректность наших действий в приведенном выше алгоритме, ведь во всех трех методах в условном операторе мы используем леммы 2 и 3, корректность которых доказана. Другими словами, алгоритм действительно найдет искомую минимальную охватывающую окружность множества точек.

Память и время работы

Сначала разберемся с памятью. Тут все просто - никаких лишних затрат, кроме как на хранение точек нам требуется, то алгоритм требует [math] O(n) [/math] памяти.

С временем работы дела обстоят интереснее. На самом деле приведенный алгоритм работает за линейное время. Докажем этот факт.

Рассмотрим некоторое множество [math] P = \{p_1, ... p_i \} [/math] и точку [math] q [/math], которая лежит на границе построенной охватывающей окружности. Тогда попробуем удалить одну точку из набора [math] P [/math]. Искомая окружность может измениться только в том случае, когда эта удаленная точка лежала на границе, а вероятность этого [math] 2 / i [/math] (так как точек, которые образуют нашу окружность не более трех. при этом одна из этих трех точек - [math] q [/math]).

То оценим время работы MinDiscWithPoint c помощью доказанного выше факта. На каждой итерации цикла будет происходить проверка, которая пройдет в "else" с вероятностью [math] 2 / i [/math]. А сложность работы каждого "else" - [math] O(i) [/math]. То суммарное время работы MinDiscWithPoint вычисляется следующим образом:

[math] O(n) + \sum_{i=1}^{n} O(i) * (2 / i ) = O(n) [/math].

Абсолютно аналогичным образом доказываем, что время работы [math] MinDisc [/math] есть [math] O(n) [/math]. То есть рассматриваемый алгоритм имеет линейную сложность.

Источники

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