Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 116

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 180 >> Следующая


В исследовании операций задача об охватывающей окружности известна под названием «минимаксная задача о размещении центра обслуживания». В этой задаче требуется найти точку р0 == (х0, уо) (центр окружности), для которой наибольшее из расстояний до точек заданного множества минимально. Точка ро определяется критерием

min max {{xt - xuf + (у, - yQf). (6.5)

МИНИМАЛЬНЫЙ

314 Гл. 6. Близость: варианты и обобщения

Такой минимаксный критерий используется при определении местоположения пунктов экстренной помощи, таких как полицейские участки и станции скорой помощи, с целью минимизировать время оказания помощи в худшем случае [Toregas et al. (1971)]. Он также используется при оптимальном размещении радиопередатчика, обслуживающего N принимающих устройств, чтобы минимизировать необходимую мощность радиопередатчика [Nair, Chandrasekaran (1971)]. По-видимому, критерий (6.5) ввел в заблуждение некоторых авторов, рассматривавших задачу о наименьшей охватывающей окружности как задачу непрерывной оптимизации, так как, на их взгляд, в постановке задачи отсутствуют какие-либо ограничения на положение точки ро. Это привело к появлению ряда итеративных алгоритмов решения этой задачи, хотя известно, что она является дискретной [Lawson, Zhukhovitsky, Avdeyeva (1966)]. Этот пример иллюстрирует важный момент: тот факт, что задачу si- можно сформулировать как частный случай задачи $8, не дает основания полагать, что общий метод, используемый для решения задачи 38, является эффективным и для решения задачи Мы уже имели возможность убедиться в справедливости этого принципа в связи с задачей о евклидовом минимальном остовном дереве (разд. 6.1): хотя ее можно рассматривать в постановке для полного графа, определенного на заданном множестве точек, усилия, затраченные на поиск метода, использующего особенности задачи, были сполна вознаграждены разработкой оптимального алгоритма.

Теперь обратимся к следующей задаче:

Задача Б.12 (НАИБОЛЬШАЯ ПУСТАЯ ОКРУЖНОСТЬ). На плоскости заданы N точек. Найти наибольшую окружность, не содержащую внутри ни одной точки этого множества, центр которой лежит внутри выпуклой оболочки множества точек (рис. 6.20).

Ограничение на положение центра окружности необходимо, так как при его отсутствии задача не имела бы ограниченного решения. Эта задача является двойственной к задаче Б. 11 в том смысле, что она является максиминной. Иначе говоря, требуется найти точку ро, определяемую критерием

Ро еГниН is) "У" ^ ~ Х0)2 + ~ У^" (6'6)

Очевидно, что могут существовать несколько точек р0, удовлетворяющих критерию (6.6). Задача о наибольшей пустой окружности является примером другой задачи о размещении какой-либо службы или предприятия. Но в этом случае необходимо выбрать положение объекта так, чтобы он был максимально удален от других N заданных объектов. Размещаемый

6.4. Промежутки и покрытия

315

объект может быть источником загрязнения, поэтому его следует располагать таким образом, чтобы минимизировать эффект от такого соседства, либо это может быть новое производство и при этом желательно избежать конкуренции за окружающее пространство. Эти задачи возникают довольно часто в промышленности [Francis, White (1974)]. Один из ранних алгоритмов решения данной задачи давал решение за время 0(N3) в худшем случае [Dasarathy, White (1975)].

Тот факт, что алгоритм, решающий задачу Б. 12, имеет сложность 0(N3), в то время когда, как нам кажется, можно получить лучший результат (О(Л72)) для «двойственной» задачи, приводит в полное недоумение. Имеется ли между этими двумя задачами глубокое различие? Сейчас мы увидим, что отличие между 0(jV3) и 0(N2) отражает недостаточную глубину анализа задач, так как с помощью диаграммы Вороного Обе ЭТИ задачи Могут рис. 6.20. Наибольшая пустая окруж-

быть решены за время ность с центром внутри выпуклой O(NlogN). Тогда как время оболочки. Q(NlogN) является оптимальным для задачи Б.12, для задачи Б.11, как мы увидим, достижима оптимальная оценка получения решения, равная Q(N).

Начнем с того, как, используя диаграмму Вороного, можно решить задачу Б.11. Мы знаем, что наименьшая охватывающая окружность С полностью определяется либо диаметром заданного множества 5, либо тремя его точками. Напомним, что окружность с центром в вершине диаграммы Вороного дальней точки множества 5 (Vor^-i(S)) и проходящая через три точки множества 5, определяемые этой вершиной, охватывает все точки множества 5. Кроме того, окружность с центром в произвольной точке, лежащей на ребре е диаграммы Vor^_i(5), и проходящая через две точки такие, что ребро е перпендикулярно отрезку, соединяющему эти точки, и делит его пополам-л также охватывает все точки множества S. Таким образом, если окружность С определяется тремя точками множества S, то ее центр находится в некоторой вершине диаграммы VorW-i(S). В противном случае, если С определяется двумя точками, то ее центр находится на некотором ребре диаграммы Уоглг_1(5). Возможен следующий подход к решению задачи [Shamos (1978)]. Сначала за время O(NlogN) определяется диаметр множества S (например, методом, рассмотренным в разд. 4.2.3) и проверяется, охватывает или нет окружность, построенная на этом диаметре, заданное множество точек. Если окружность
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed