 |
Метод разделяй и властвуй.
|
|
|
|
Поскольку задача построения выпуклой оболочки легко разбивается на подзадачи, можно для ее решения применить технику «разделяй и властвуй». Разобьем множество 
из 
точек на два подмножества 
и 
по 
и 
точек в каждом соответственно. После разбиения можно рекурсивно строить выпуклую оболочку для каждого из множеств и . Для построения 
необходимо решить задачу слияния оболочек 
и 
. С этой целью выберем некоторую внутреннюю точку 
множества . Например, в качестве можно взять центроид трех любых вершин, лежащих на . Далее рассмотрим следующие варианты:
- точка является внутренней вершиной в . Условие выполняется, если при обходе вершин из против часовой стрелки, вершина все время лежит слева от ребер соответствующего многоугольника. Данная процедура занимает
времени. Поскольку вершины и являются упорядоченными по полярному углу относительно точки , можно, используя метод Грэхема, построить за времени выпуклую оболочку для множества 
. Эта ситуация проиллюстрирована на рисунке ниже
- точка не является внутренней вершиной в .Поместим в точку точечный источник света, который «освещает» точки из . Из выходят два луча (опорные прямые), касающиеся в точках
и 
. Тогда цепь, составляющая , разбивается точками и на освещенную и затененную части. При движении против часовой стрелке вокруг точки от точки к по затененной части полярный угол возрастает, а такое же движение от к по освещенной части вызывает уменьшение значения угловой меры. Можно не рассматривать вершины освещенной части цепи, поскольку они являются внутренними точками множества . Затененная часть границы и граница множества представляют собой два упорядоченных списка, которые содержат в общей сумме не более вершин. После слияния этих последовательностей (требует не более времени), применяем к получившейся последовательности метод Грэхема и строим
|
|
|
Обозначая время работы алгоритма на точках через 
и учитывая, что построение опорных прямых требует времени, имеем следующие рекуррентные соотношения
где 
- некоторые константы. Решением этого уравнения является функция 
Метод разделяй и властвуй имеет много общего с алгоритмом сортировки слиянием. Идеи, заложенные в алгоритме Quicksort, нашли отражение в методе построения выпуклой оболочки, названном
QuickHull
Основная идея алгоритма заключается в разбиении исходного множества на два подмножества и , выпуклые оболочки которых содержат ломанные, сцепление которых дает часть выпуклой оболочки множества . На первом шаге для разбиения [27] выбираются точка 
, с наименьшей ординатой из всех точек, имеющих наименьшую абсциссу, и точка 
, с наименьшей ординатой из всех точек, имеющих наибольшую абсциссу. Тогда - множество точек из , расположенных выше или на прямой 
, а соответственно множество точек из , лежащих ниже или на разделяющей прямой. Далее ведется поиск некоторой точки 
из так, чтобы значение площади 
было максимальным среди всех треугольников, лежащих в . В случае совпадения нескольких максимальных площадей выбирается треугольник с наименьшим значением угла 
. Нетрудно заметить что при таком выборе точка С принадлежит .
Точка разбивает на три множества:
-
- множество точек, лежащих слева от 
-
- множество точек, лежащих справа от 
-
- точки, принадлежащие
Поскольку точки из не принадлежат , они отбрасываются. Точка гарантированно принадлежит выпуклой оболочке. В самом деле, если провести через прямую 
, параллельную прямой , то выше этой прямой не лежит ни одной точки из множества . Поскольку является самой левой точкой из , лежащей на прямой , она не может быть равна выпуклой комбинации других точек из , а следовательно является крайней точкой. Далее рекурсивно строятся части выпуклых оболочек множеств и , затем выпуклые цепи сцепляются в точке . Первое разбиение прямой немного отличается от разбиений, которые алгоритм строит на последующих шагах. В [5] указано, как можно выйти из этой ситуации. Можно, выбрав произвольно малое число 
, рядом с точкой с координатами (
) добавить точку 
с координатами 
, провести через эти точки вертикальную прямую, а далее строить разбиение (выбрать точку ) относительно этой прямой. После выбора точки , точку следует удалить.
|
|
|
В этом методе не удается сбалансировано делить на подмножества, поэтому в худшем случае, как и в Quicksort, оценка достигает 
. Метод плохо работает, когда все точки из являются крайними, и на каждом шаге отсекается ровно одна точка. Пример такого расположения точек исходного множества приведен на рисунке ниже
В этом примере на каждом шаге алгоритма в выпуклую оболочку будет включаться ровно по одной точке начиная с точки, находящейся к оси абсцисс под углом 
, далее под углами 
, 
, …
Однако если при разбиении на каждом уровне рекурсии отсекается не константная часть элементов, то можно, как и в случае алгоритма Quicksort, оценить время работы алгоритма функцией [5].
Алгоритм Чена
В 1995 году Т.Ченем был предложен алгоритм построения выпуклой оболочки, имеющий временную сложность 
, где через 
обозначено число вершин выпуклой оболочки. В основе алгоритма, как и у Джарвиса, лежит идея заворачивания, но Чень в своем алгоритме вводит некоторый числовой параметр, по которому проводится оптимизация.
Сначала множество исходных точек разбивается на некоторое число подмножеств 
. Далее для каждого из выделенных подмножеств строится выпуклая оболочка (можно использовать метод Грэхема). При построении выпуклой оболочки для используется информация об уже построенных к этому времени выпуклых оболочках 
. Введем понятие правой опорной точки выпуклого многоугольника 
. Правой опорной точкой выпуклого многоугольника относительно точки , называется такая точка 
, что любая другая точка многоугольника лежит по левую сторону от ориентированного отрезка 
. Ниже проиллюстрированы примеры опорных точек в случае, когда точка не лежит на многоугольнике, и в случае, когда принадлежит границе многоугольника:
|
|
|
Выпуклая оболочка для строится добавлением следующего ребра к построенному к этому времени участку выпуклой оболочки, но в отличие от алгоритма Джарвиса выбор кандидата делается из правых опорных точек многоугольников относительно некоторой текущей точки 
.
В процессе заворачивания алгоритм последовательно добавляет точки в выпуклую оболочку: с этой целью определяется множество правых опорных точек многоугольников относительно последней включенной вершины , и выбор следующей вершины 
ведется только среди этих опорных точек по следующему правилу: любая точка 
, должна лежать на ориентированном отрезке 
или левее этого отрезка.
На рисунке ниже показано как на некотором шаге алгоритма среди правых опорных точек 
и 
построенных относительно точки находится следующая точка выпуклой оболочки
На следующем рисунке показано как изменяется множество правых опорных точек относительно нового положения точки
При этом необходимо отметить два обстоятельства:
- Выпуклые оболочки для множеств , строятся ровно один раз. Внутренние точки множеств
в построении выпуклой оболочки всего множества участия не принимают. - Правые опорные точки для каждого из множеств строятся алгоритмом заново по мере построения выпуклой оболочки для всего множества.
Выберем параметр 
. Рассмотрим шаги алгоритма:
Шаг 1. Произвольно разбить исходное множество на 
подмножеств , каждое из которых содержит не более 
вершин.
Шаг 2. Для каждого 
построить выпуклую оболочку 
. Для этого можно использовать метод Грэхема.
Шаг 3. Выбрать точку 
, которая будет крайней точкой выпуклой оболочки 
. Например, за эту точку можно взять самую левую точку из точек с минимальной 
- координатой. Положить 
.
Шаг 4. для всех 
, 
, найти правую опорную точку 
выпуклого многогранника относительно , среди этих точек определить точку , так, чтобы все точки лежали слева от ориентированного отрезка 
. Если таких точек несколько, выбирается точка, наиболее удаленная от точки . Найденная точка является следующей точкой выпуклой оболочки. Положить 
и повторить шаг 4 до тех пор, пока заворачивание не приведет к исходной точке .
|
|
|
Временная сложность алгоритма зависит от значения параметра .
Очевидно, шаг 1 требует времени. Выпуклая оболочка для каждого из множеств может быть построена за время 
. Всего второй шаг требует 
времени. Начальная точка (шаг 3) может быть найдена за шагов.
Отдельно рассмотрим шаг 4. Нахождение одной правой опорной точки для с использованием двоичного поиска занимает 
времени, в пересчете на все множества 
, это составит 
времени. Поиск точки из множества вершин 
занимает 
шагов. Поэтому однократное выполнение шага 4 в целом займет 
времени. Поскольку шаг 4 выполняется раз, то всего потребуется 
времени. Всего имеем, 
времени. Выбирая 
, получим требуемую оценку. Однако внимательный читатель может заметить, что к началу решения задачи нам не известно значение . Выход заключается в подборе значения , при этом важно, чтобы подбор занимал константное время.
Рассмотрим следующий псевдокод
;
// Вызвать процедуру построения выпуклой оболочки для множества ,
// состоящего из вершин методом Чена с параметром ;
процедура построила выпуклую оболочку 
напечатать 
выйти из цикла;
Необходимо отметить, что при недостаточных значениях алгоритм после итераций не вернется к точке . В этом случае необходимо увеличить значение и повторно вызвать процедуру построения выпуклой оболочки с новым значением параметра. Заметим также, что при 
алгоритм завершает свою работу на шаге 2 построением выпуклой оболочки.
Алгоритм завершит работу при выполнении условия 
или 
. При фиксированном 
время работы алгоритма составляет 
. Поэтому время работы алгоритма оценивается сверху числом
.
Таким образом, нетривиальная комбинация подходов Грэхема и Джарвиса позволила получить алгоритм, который в среднем имеет трудоемкость , а в худшем случае работает времени.
[1] Хотя существуют специфические задачи, когда последовательность запросов направлена на определение некоторого сложного объекта (например, ведется поиск цепи в графе, а каждый запрос определяет некоторое звено в цепи). В этом случае информация, полученная на предыдущих шагах, может быть использована для оптимизации поиска в последующем.
[2] Задачи поиска формулируются и для мультимножеств, которые содержат одинаковые элементы. Алгоритмы поиска и сложность поиска в этом случае не значительно отличаются от случая, когда все элементы множества различны, и поэтому отдельно не рассматриваются.
|
|
|
[3] Хотя конечной целью поиска является информация, которая содержится в объектах, ассоциированных со значением ключа, по которому ведется поиск. Эта информация наряду с ключами может содержаться в самих объектах, или храниться отдельно. В этом случае ключ играет роль адреса доступа к нужной информации.
[4] В общем случае, на элементах множества можно задать приоритеты, и провести сортировку согласно установленным приоритетам.
[5] Множество приоритетов
[6] Определение дано для случая с уникальными ключами
[7] Бесплатным, как известно, бывает … Необходимо понимать, что упрощая процедуру поиска, мы усложняем текущий объект и расходуем дополнительную память
[8] Случай правого брата аналогичен
[9] Процесс корректировки меток может быть прерван досрочно, если метки некоторой промежуточной вершины не изменились
[10] Эта операция подробно рассмотрена в примере 3 введения
[11] Случай является двойственным и рассматривается аналогично
[12] Число 5 не принципиально – можно взять и другую нечетную константу, начиная с 3.
[13] Необходимо вспомнить, что.
[14] Напомним, что является множеством запросов
[15] Сложность обычно - константа
[16] Очевидно, является нижней оценкой, так как аргументом функции выступает строка длины
[17] см. Шенноновские нижние оценки при реализации булевых функций в некоторых классах управляющих систем
[18] При условии, что подмножество содержит более одной перестановки
[19] С точностью до перестановок одинаковых элементов
[20] Обычно операции, связанные с обменом, занимают больше времени, чем операции сравнения ключей. Но поскольку эта разница сильно зависит от модели вычислителя, мы для внутренней сортировки не будем различать сложность выполнения этих операций.
[21] В случае, когда одна из последовательностей имеет длину 1, говорят о включении соответствующего элемента в
[22] Название алгоритма происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень.
[23] Например, использование степеней двойки дает неэффективную реализацию, поскольку до последнего прохода элементы с четными индексами не сравниваются с элементами нечетными индексами.
[24] Если последовательности заданы списками, то можно обойтись без дополнительного списка, изменяя ссылки элементов исходной последовательности.
[25] См. раздел порядковые статистики
[26] Интересно, что сложность алгоритма зависит не только от размерности входных данных, но и от размерности выходных данных, поскольку перед решением задачи мы не знаем сколько вершин войдет в выпуклую оболочку.
[27] Здесь, говоря о разбиении можно закрыть глаза на то, что и содержат общую часть в виде прямой, проходящей через точки и.
|
|
|
