Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Важнейшей характеристикой этой процедуры, изменяющейся от приложения к приложению, является функция КОРРЕКТИРОВАТЬ (v) из строки 4, частные случаи которой будут обсуждаться в соответствующих местах. Аналогичные соображения применимы и к процедуре УДАЛИТЬ(6, е; и).
В заключение заметим, что метод плоского заметания и использование структур данных, ориентированных на хранение интервалов, являются естественными средствами для решения множества задач, возникающих в геометрии прямоугольников. Приведенные ниже разделы посвящены детальному разбору специальных методов.
8.4. Мера и периметр объединения прямоугольников
В одной статье [Klee (1977)], которая представляет заметный интерес и может считаться началом целого направления исследований, Кли поставил следующий вопрос: «Заданы N интервалов [aubi], [aN,bN] на действительной прямой, надо найти меру их объединения. Какой может быть трудоемкость этой процедуры?».
8.4. Мера и периметр объединения прямоугольников
405
Такая постановка дает простейший (одномерный) пример задачи о мере объединения. (Будем называть задачу о вычислении меры объединения для произвольного числа измерений задачей 0.1.') Кли сразу же построил алгоритм решения этой задачи с оценкой 0(N\ogN), основанный на предварительной сортировке абсцисс аи Ьи aN, bN в массиве X[l:2N]. Дополнительное свойство этого массива состоит в том, что если а, помещено в X[h], Ь/— в X[k) и а, = 6/, то h < k (т. е. правая концевая точка помещается в нем после левой точки, обладающей такой же абсциссой). Вычисление завершается простым просмотром массива X[l : 2N] за линейное время (нижеследующий алгоритм представляет собой адаптацию алгоритма Кли, удобную для последующих обобщений):
procedure МЕРА-ОБЪЕДИНЕНИЯ-ИНТЕРВАЛОВ 1. begin X[l : 2N] := упорядоченная последовательность
абсцисс концов интервалов;
2. *[0]:=*[1];
3. т:=0; {* m — мера*)
4. С:=0; (* С — число перекрывающихся интервалов*)
5. for /:=1 until 2N do
6. begin if (С Ф 0) then m := m + X[i] - X[i - 1];
7. if (X[i] — левая концевая точка) then
8. C:=C+ 1 else C:=C — 1 end
end.
В своей статье Кли также отметил, что, хотя сортировка является ключом к получению вышеизложенного результата, она не является априорно необходимой, и поставил вопрос о существовании какого-нибудь метода решения, требующего o(N\ogN) операций.
Ответ на этот вопрос был получен Фредменом и Вайде [Fredman, Weide (1978)] для модели вычислений с линейным деревом решений (к которой относится и вышеизложенный алгоритм); применение общего метода Бен-Ора (разд. 1.4) расширяет пределы этого результата на произвольные алгебраические деревья решений. Закономерно, что доказательства подобного типа укладываются в уже знакомую схему, встречавшуюся ранее в связи с исследованиями выпуклых оболочек (разд. 3.2), максимумов на множестве векторов (разд. 4.1.3), уникальности элементов (разд. 5.2) и максимального промежутка (разд. 6.4). В основе лежит симметрическая группа степени N, которая вновь является ключом к доказательству. Здесь будет использован следующий вычислительный прототип:
¦') О — аббревиатура слова «ортогональность». — Прим. перев.
406
Гл. 8. Геометрия прямоугольников
Задача 0.2 (е-БЛИЗОСТЬ). Дано N+1 действительных чисел хи х2, ¦ ¦ ¦, xN и е > 0. Надо определить, будут ли какие-нибудь два числа xt и х,- (i Ф /) находиться на расстоянии, меньшем чем е одно от другого.
Прежде всего покажем, что можно легко установить преобразование
е-БЛИЗОСТЬ ос„ МЕРА ОБЪЕДИНЕНИЯ ИНТЕРВАЛОВ.
Действительно, построим интервалы [*,-,Xi + е] для i— 1, 2, ... .., N. Эти интервалы будут входом для процедуры МЕРА-ОБЪЕДИНЕНИЯ, результатом работы которой будет вещественное число т. Теперь ясно, что никакие два числа из
(а) (Ь)
Рис. 8.7. Иллюстрация (в случае Е?) различия между множествами истинности в задачах об УНИКАЛЬНОСТИ ЭЛЕМЕНТОВ (а) и е-БЛИЗО-СТИ (Ь).
{х\, ..., xn) не будут находиться на расстоянии, меньшем чем е друг от друга, тогда и только тогда, когда т = Ne.
Существует близкое сходство между е-БЛИЗОСТЬЮ и УНИКАЛЬНОСТЬЮ ЭЛЕМЕНТОВ, изложенной в разд. 5.2. Однако УНИКАЛЬНОСТЬ ЭЛЕМЕНТОВ не является частным случаем е-БЛИЗОСТИ, поскольку значение е = 0, необходимое для получения указанного частного случая, недопустимо. Различие этих задач выразительно проиллюстрировано на рис. 8.7 для двумерного случая: если речь идет об УНИКАЛЬНОСТИ ЭЛЕМЕНТОВ, то непересекающиеся связные компоненты множества истинности W (см. разд. 1.4 и 5.2) представляют собой открытые множества, разделенные только их общей границей; если же речь идет об е-БЛИЗОСТИ, то компоненты представляют собой замкнутые множества и расстояние между ними положительно. Если исключить это различие, то доказательство того, что множество W для задачи об е-БЛИЗОСТИ распадается на ЛП непересекающихся компонент связности, будет анало-
8.4. Мера и периметр объединения прямоугольников
407
гично доказательству, приведенному в разд. 5.2; отсюда вытекает следствие из теоремы 1.2:
