Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Прежде чем обсуждать чрезвычайно важный результат Сти ли —Яо и Бен-Ора, давайте посмотрим, почему модель линейного дерева решений не подходит для нашей задачи. Коротко можно сказать, что не существует алгоритма построения выпуклой оболочки, использующего исключительно линейные проверки, поэтому модель линейного дерева решений не применима Типичная элементарная операция имеет вид: даны три точки р, р' и р" и требуется определить, находится ли точка р слева или справа или на ориентированном отрезке р'р"? Полином, реализующий соответствующую проверку, задается определителем х у 1
х' у' \ , (3.4)
х" у" 1
где р = {х, у), р= [х', у') и р" = (х", у"). Этот определитель, как отмечалось в разд. 2.2.1, дает удвоенную площадь треугольника (рр'р") со знаком. Очевидно, что полином (3.4) является квадратным.
Это — огорчающее обстоятельство, так как ранее Эйвис [Avis (1979)] предложил простое и изящное доказательство, основанное на модели линейного дерева решений. В этом доказательстве ключевым образом использовался тот факт, что линейная проверка f(xi, xm): 0 определяет гиперплоскость в т-мер-ном евклидовом пространстве Ет и каждый путь от корня к листу дерева определяет пересечение выпуклых множеств (полупространства соответствуют случаям «>» или «<», гиперплоскости соответствуют случаю (« = »), которое само является выпуклым множеством в Ет (область решений, связанная с этим листом). Однако это свойство не сохраняется, когда проверочный полином имеет более высокую степень.
Искусное, но чрезвычайно сложное доказательство, представленное Яо, ограничивалось моделью квадратичных деревьев решений. Хотя существующие алгоритмы можно охватить, ограничиваясь квадратичными деревьями вычислений, непроизвольно возникает следующий вопрос: если допускаются полиномы степени выше второй, то можно ли по-прежнему доказывать аналогичные результаты? Или, если этого нельзя сделать, можно ли, используя такие, возможно, более мощные проверки, разработать более быстрые алгоритмы? Яо высказался против положительного ответа. Однако совсем недавно этот вопрос был окончательно решен с помощью следующего доказательства.
Предположим, дан алгоритм, представленный алгебраическим деревом решений фиксированного порядка d ^ 2, претендующий на решение задачи ВОЗ для множества из 2N точек на плоскости, т. е. он воспринимает на входе вектор из AN компо-
¦3.2. Постановка задачи и нижние оценки сложности 123
нент (по две координаты для каждой точки) и определяет, содержит ли их выпуклая оболочка 2N крайних точек. Отметим, что входной вектор, имеющий 4N компонент, можно вполне корректно представлять как точку в пространстве EiN. Рассматриваемая нами задача на распознавание характеризуется «множеством истинности» FcP (см. разд. 1.4). Для удобства мы повторяем здесь результат, полученный Бен-Ором.
Теорема 1.2. Пусть W — множество в Em, а Т — алгебраическое дерево решений фиксированного порядка d, решающее задачу о принадлежности W. Если h* — глубина дерева Т, а #(№) — число разделимых связных компонент W, то
A* = Q(log#(r)-m).
Для того чтобы воспользоваться этим результатом, необходимо получить нижнюю оценку для #(№). Это может быть сделано следующим образом.
Пусть (ро, Pi, p2N~\)—последовательность вершин выпуклого многоугольника, перечисленных в порядке обхода по часовой стрелке (рис. 3.2). Исходные данные для алгоритма представлены в виде цепочки z = {z0, z\, ..., z4w_i) действительных
Рис. 3.2. Иллюстрация к доказательству теоремы 3.3.
чисел, получаемой следующим образом: на плоскости заданы 2N точек qo, q\, q2n-i с координатами qi= (xi, г/,), полагаем z2i = xi и z2;+i = у< для i = 0, 1. ..., 2N — 1. Для фиксированной последовательности (ро, Рь • • • , ргы-\) можно построить N1 различных экземпляров входных цепочек для данного варианта задачи, выбирая произвольную перестановку л целых чисел {0, 1, Л/ — 1} и полагая
42s = P2s> <72s+i = PM2s+d (s = 0, ..., Л/ — I). (3.5)
Отметим, что все возможные для данной задачи входные последовательности имеют одинаковые подпоследовательности точек
124
Гл. 3. Выпуклые оболочки: основные алгоритмы
с четными индексами (показанные на рис. 3.2 черными кружками). Для заданной перестановки я обозначим через z (л) (последовательность координат точек (q0.....q2N~i)).
Теперь для каждой перестановки я построим массив Л (я) с N2 элементами. Сделаем это следующим образом. Обозначив через А (и, v, w) площадь треугольника (и, v, w) со знаком и через A(n)[j] /-й элемент Л (я), имеем
А (я) [Ns + г] = A (q2s, q{2s+2) mod 2/v, q2r+i),
0<s<JV, 0<г<ЛГ. (3.6)
Из (3.5) и (3.6) и рис. 3.2 легко понять, что для данного s имеется всего одно значение г, для которого A(n)[Ns + г] < О (это имеет место при 2s + 1 = я-1(2г + 1)). Предположим теперь, что я, и яг — две различные перестановки чисел {0, 1, ... .... N — ]}, и рассмотрим массивы А(щ) и Л(я2). Мы утверждаем, что существует по крайней мере одно целое число / такое, что Л(я1)[/] и Л(я2)[/] имеют противоположные знаки. Действительно, рассмотрим N элементов массива А(п\), являющихся отрицательными, т. е. элементы А (щ) [Ni -f- ri\, 0 s=: t < Л/. Если А (яО [ЛЯ + п] - А (я2) [ЛЯ -+- п] > 0, то обе точки qn-.x ^Ni+r^
