Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
4.1. Расширения и варианты
189
от рассматривавшихся до сих пор. А именно в этом разделе будет предполагаться, что функция взятия целой части « |_ J» входит в состав множества примитивных операций 1). Обратимся к рис. 4.1 (а).)На первом шаге алгоритма ищутся минимальное и максимальное значения х-координаты точек множества, а затем вертикальная полоса между ними разбивается на k полос равной ширины. Эти k полос образуют последовательность «ящиков», по которым будут распределены N точек исходного множества S (для этого как раз и понадобится функция взятия целой части). После этого в каждой из полос ищутся две точки, имеющие минимальное и максимальное значения г/-координаты (рис. 4.1(b)). Кроме того, выбираются точки с экстремальными значениями х-координаты. Если при этом одно и то же экстремальное значение по х-координате имеют сразу несколько точек, то из них выбираются только точки с минимальной и максимальной (/-координатами. Таким образом, результирующее множество, обозначаемое S*, содержит самое большее 2k + 4 точек. Наконец, строится выпуклая оболочка множества S*, которая служит аппроксимацией оболочки исходного множества (рис. 4.1(c)). Отметим, что получившаяся оболочка в самом деле является лишь аппроксимацией: в примере на рис. 4.1(c) одна из точек исходного множества лежит вне построенной оболочки.
Описанный здесь коротко метод чрезвычайно прост в реализации. Указанные k полос отображаются на массиве из (k + 2) элементов (нулевой и (&+1)-й элементы содержат две точки с экстремальными значениями х-координаты: соответственно Xmin и Хтах). Чтобы определить полосу, в которую попадает некоторая точка р, необходимо вычесть из х(р) минимальное значение х-координаты (xmin) и разделить получившуюся разность на (1/&)-ю часть разности значений х-координат экстремальных точек. Взяв целую часть от получившегося результата, получим номер полосы, содержащей точку. Можно параллельно искать минимум и максимум в каждой полосе, так как для каждой точки проверяется, выходит ли она за пределы текущих значений максимума и минимума, и, если это имеет место, производится необходимое изменение в массиве. И наконец, можно выбрать удобный в данном случае алгоритм построения выпуклой оболочки: очевидно, что наиболее подходящим является вариант алгоритма Грэхема, предложенный Эндрью (см. разд. 3.3.2). Заметим, что точки множества S* почти упорядочены по значению х-координаты. Чтобы получить полностью упорядоченное
') Заметим, что модель вычислений, основанная на деревьях решений, использовавшаяся во всех рассмотренных до сих пор алгоритмах построения выпуклой оболочки, исключает использование функции взятия целой части.
190 Гл. 4. Выпуклые оболочки: расширения и приложения
множество, необходимо лишь сравнить в каждой полосе значения х-координаты двух точек множества 5*, принадлежащих этой полосе.
Работа этого метода также легко поддается анализу. Объем необходимой памяти пропорционален k (в предположении, что исходные точки уже представлены в памяти). Для нахождения минимального и максимального значений х-координаты требуется время 0 (N). Поиск экстремумов во всех полосах требует времени 6(iV), а выпуклая оболочка множества S* может быть построена за время 0(k) (так как множество S* содержит не более 2К + 4 точек, причем эти точки уже упорядочены по значению х-координаты). Следовательно, полное время работы алгоритма равно Q(N + k).
Простота и эффективность описанного алгоритма имели бы небольшую ценность, если бы получаемый результат был слишком неточным. Попробуем оценить точность такого подхода. Прежде всего, так как для построения выпуклой оболочки алгоритм использует лишь точки исходного множества, то получающаяся аппроксимация является внутренней в том смысле, что любая точка, попавшая внутрь приближенной оболочки, будет также и внутренней точкой действительной выпуклой оболочки. Возникает вопрос: насколько далеко от приближенной выпуклой оболочки может оказаться точка из 5, находящаяся вне её? Ответ на это вопрос дает следующая довольно очевидная теорема:
Теорема 4.6. Любая точка р е S, не попавшая внутрь приближенной выпуклой оболочки, находится на расстоянии, не превышающем (xmax — xmin) /k от этой оболочки.
Доказательство. Рассмотрим полосу, содержащую точку р (рис. 4.2). Так как точка р находится вне приближенной оболочки, то она не может иметь ни наибольшую, ни наименьшую г/-координату среди точек, попавших в ту же полосу. Поэтому #min ^ у(р) ^ Утях. Если и ¦— это точка пересечения горизонтальной прямой, проходящей через точку р, с ребром приближенной оболочки, то длина отрезка ри ограничивает сверху расстояние от точки р до оболочки. Длина отрезка ри сама ограничена сверху шириной полосы (хтах — xmin)/k.
Рассмотренный метод аппроксимации дает приближенную оболочку, являющуюся подмножеством истинной выпуклой оболочки, но нетрудно изменить метод, чтобы получать «супермножество» истинной оболочки. Достаточно лишь заменить каждую экстремальную точку р парой точек на границах полосы, но с той же ординатой, что и у точки р. Очевидно, что получающаяся в результате оболочка охватывает истинную выпуклую оболоч-
