Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 6

Пусть есть n магазинов x_j, заданных своими координатами. Выделим для каждого из них зону обслуживания, предполагая, что покупатели ходят в ближайший магазин. Тогда зоны обслуживания суть множества , называемые клетками Дирихле или многоугольниками Вороного. Совокупность всех таких многоугольников называется диаграммой Вороного. Магазины назовем соседними, если их многоугольники имеют общий участок границы. У нас соседями будут пары: (1,2), (1,4), (2,3), (2,4), (3,4). Соединив все пары соседних вершин ребрами, получим граф Делоне. Он задает наилучшую триангуляцию карты (минимальный угол в триангуляции Делоне - наибольший по всем триангуляциям). Число ребер в диаграмме и в графе Делоне считается по формуле  3·(n-1)-G, где G – число точек, лежащих на границе выпуклой оболочки. Диаграмма строится рекурсивно методом “разделяй и властвуй” за O(n·log n) операций (т.к. ):

1.  Найдем медиану среди первых координат точек и разобьем точки на два равных подмножества L и R, выпуклые оболочки conv(L) и conv(R) которых не пересекаются.

2.  Построим диаграммы Вороного ДВ(L) и ДВ(R) для каждого из подмножеств.

3.  По ДВ(L) и ДВ(R) за линейное время построим conv(L) и conv(R), и выполнив шаг 3 алгоритма Грэхема (см. ниже) – границу conv(X). На ней найдем два опорных отрезка (верхний и нижний), концы которых лежат в разных множествах L и R.

4.  Построим ломаную B, каждая точка z которой равноудалена от ближайших к z в множествах L и R точек l=l(z) и r=r(z). Двигаясь вверх по срединному перпендикуляру к текущему отрезку (начиная с нижнего опорного) до первой точки пересечения с отрезком одной из диаграмм, мы попадем в зону близости другой точки этой диаграммы Þ  меняем l или r. Дойдя до верхнего опорного отрезка, завершим построение ломаной B.

5.  Склеим две диаграммы в одну, удалив все части диаграммы ДВ(L), расположенные справа от ломаной B, и все части диаграммы ДВ(R), расположенные слева от B.

Пример:  L = {1,2,4},   R = {3,5,6}.

Опорные отрезки – (1,6) и (2,5).

Диаграмма Вороного полезна при решении многих оптимизационных задач на плоскости и ее построение выносится в предобработку. Она задает топологию на конечных множествах в ².

№6. ПОСТРОЕНИЕ ВЫПУКЛОЙ ОБОЛОЧКИ В Â².

Алгоритм Грехема. На входе - множество X={x_i}, состоящее из n точек плоскости.

1)  Выберем внутреннюю точку O (например, центр тяжести любых 3-х точек).

2)  Упорядочим полярные углы из O на точки x_i и перенумеруем точки.

3)  В цикле для тройки (l,k,r) проверим, лежит ли точка k внутри conv(O,l,r), где l=L(k), r=R(k), т.е. l и r- соседи слева и справа от k по оставшимся углам. Если лежит, то удаляем k {L(r)=l, R(l)=r} и делаем шаг назад {k=r, r=R(r)}, проверяя rÏconv(O,l,R(r)). Если же нет, то идем вперед: {r=k, k=l, l=L(l)}. Цикл идет до тех пор, пока некоторая тройка не повторится.

Суммарное число шагов вперед < 2n, шагов назад < n. А общая трудоемкость алгоритма определяется на шаге 2 и равна O(n·log n).

Пример:Выберем точку О как центр тяжести любых трех точек исходного множества точек. Упорядочим точки по полярному углу из точки О. Выполним шаг 3 алгоритма:

тройка (2,1,6) - 1 лежит справа от отрезка [2,6] Þ 2 не принадлежит выпуклой оболочке Þ идем вперед. Результат занесем в таблицу (цикл по средней точке от 1 до n и замыкаем на 1 до повтора тройки ???):