Примеры задач, к которым может быть сведена сортировка.

Напомним важную теорему 2 из Лекции 2:

Если задача z₁ сводится к задаче z₂ за время g(N) и задача z₁ имеет нижнюю оценку времени решения j₁(N), то задача z₂ имеет нижнюю оценку времени решения j₂(N) = j₁(N) - g(N).

Напомним также, что при создании алгоритмов, решающих рассматриваемую задачу, изначально фиксируется набор допустимых операций, используемых в алгоритмах, и задаются времена выполнения этих операций. Для исследования нижних оценок времени решения задачи сортировки мы рассматривали алгоритмы на основе дерева решений. Это задавало нам набор допустимых операций с возможностью задания времени работы каждой операции. Далее в данной лекции мы будем использовать тот же самый набор допустимых операций. Т.е. все рассматриваемые задачи будут решаться на основе алгоритмов, основанных на сравнениях.

Таким образом, если мы докажем, что решение задачи сортировки может быть сведено за линейное время к решению некоторой другой задачи z, то мы сразу докажем, что у задачи z в классе алгоритмов, основанных на сравнениях, имеется нижняя оценка времени решения задачи j(N)=O(N log N).

Данная лекция будет, по сути, состоять из довольно большого количества чисто геометрических доказательств. В лекции будет использоваться довольно много чисто геометрических утверждений. Если эти факты очевидны и их доказательство элементарно делается на уровне школьной геометрии, то для сокращения объема лекции их доказательства производиться не будут.

Построение выпуклой оболочки

Определение. Множество точек S на плоскости называется выпуклой оболочкой множества точек {A₁ ,…, A_N } на плоскости, если S является наименьшим выпуклым множеством, содержащим точки {A₁ ,…, A_N }.

Отметим, что вместо стандартного определения выпуклого множества (M – выпукло, если для любых A,BÎM: [A,B] ÎM) в школе дают другое определение выпуклого многоугольника: многоугольник M – выпуклый, если для любой прямой l, проходящей через ребро M, M лежит в одной полуплоскости с границей l. Доказательство эквивалентности этих определений в одну сторону (M – выпуклый многоугольник Þ M – выпуклое множество) элементарно (полуплоскость – выпукла, а пересечение выпуклых множеств выпукло), а в другую все же требует одного шага (докажем, что если многоугольник лежит по две стороны от прямой, лежащей на ребре, то он не выпуклый; для доказательства рассмотрим такую окрестность некоторой точки X на этом ребре, что с одной стороны ребра точки окрестности принадлежат M, а с другой – нет; осталось соединить X с точкой многоугольника на второй стороне прямой и мы сразу получим, что M не выпуклый).

Существование такого множества доказывается элементарно: рассмотрим все выпуклые множества, содержащие {A₁ ,…, A_N }. Пересечение всех этих множеств является выпуклым множеством и (по построению) содержится в любом выпуклом множестве, содержащем {A₁ ,…, A_N }. Т.о. полученное множество точек и дает требуемую выпуклую оболочку точек {A₁ ,…, A_N }.

Приведем без доказательства довольно очевидную (здесь не сказано, что тривиальную) теорему:

Теорема 1. Выпуклой оболочкой конечного множества точек на плоскости {A₁ ,…, A_N } является некоторый выпуклый многоугольник с вершинами, принадлежащими множеству {A₁ ,…, A_N }.

Везде далее фраза множество точек лежит по одну сторону от прямой l будет синонимом (сокращением) фразы множество точек лежит в одной полуплоскости с границей, лежащей на прямой l.

Для каждой пары точек A_i , A_j , принадлежащих {A₁ ,…, A_N }, верно одно из двух утверждений: либо все остальные точки множества {A₁ ,…, A_N } лежат в одной полуплоскости с границей (A_i , A_j), либо точки из множества {A₁ ,…, A_N } присутствуют с двух сторон относительно (A_i , A_j). При этом выполняется следующая

Теорема 2. Если для (A_i , A_j) все точки множества {A₁ ,…, A_N } лежат в одной полуплоскости с границей (A_i , A_j), то [A_i , A_j] принадлежит границе многоугольника выпуклой оболочки {A₁ ,…, A_N }, т.е. является, как минимум, частью некоторого ребра многоугольника выпуклой оболочки.

Теорема легко доказывается от противного. Назовем многоугольник выпуклой оболочки M. [A_i , A_j] принадлежит M, т.к. выпуклая оболочка – выпуклое множество и точки A_i и A_j принадлежат этому множеству. Здесь A_i , A_j – такие точки из множества {A₁ ,…, A_N }, что все точки множества {A₁ ,…, A_N } лежат в одной полуплоскости с границей (A_i , A_j).

Допустим, некоторая точка P отрезка [A_i , A_j] не принадлежит границе выпуклой оболочки. Тогда P – внутренняя точка многоугольника M. Но поскольку многоугольник – замкнутое множество точек, то получаем, что P принадлежит M вместе с некоторой своей окрестностью. Т.о. мы получаем, что по обе стороны от отрезка [A_i , A_j] присутствуют точки из M. Рассмотрим полуплоскость π с границей (A_i , A_j), внутри которой находятся все точки из {A₁ ,…, A_N }. Рассмотрим многоугольник M’= MÇπ. M’ является выпуклым многоугольником (т.к. M’ есть пересечение выпуклого многоугольника и полуплоскости). По построению M’ содержит все точки {A₁ ,…, A_{N }}. M содержит точки, не принадлежащие M’. Но это противоречит тому, что M является наименьшим выпуклым множеством, содержащим {A₁ ,…, A_N }. Из полученного противоречия следует, что весь [A_i , A_j] принадлежит границе M.

¢

Следствие из Теоремы 2. Объединение всех отрезков [A_i , A_j] таких, что все точки множества {A₁ ,…, A_N } лежат в одной полуплоскости с границей (A_i , A_j), представляет собой границу многоугольника выпуклой оболочки {A₁ ,…, A_N }.

Доказательство следствия элементарно: с одной стороны, если отрезок [A_i , A_j] обладает указанным в следствии свойством, то по тереме 2 он принадлежит границе выпуклой оболочки. С другой стороны, если отрезок [C ,D] является ребром многоугольника выпуклой оболочки {A₁ ,…, A_N }, то по теореме 1 и определению выпуклого множества он является некоторым отрезком [A_i , A_j] и все точки множества {A₁ ,…, A_N } лежат в одной полуплоскости с границей (A_i , A_j).

¢

Данное следствие сразу дает алгоритм построения выпуклой оболочки M конечного множества точек {A₁ ,…, A_N }. Несмотря на очевидную идею, алгоритм состоит из нескольких нетривиальных этапов:

1. Рассмотрим все пары точек из данного множества {A_i , A_j}. Прямым перебором всех оставшихся точек определяем, лежат ли остальные точки по одну сторону от (A_i , A_j), включая саму прямую. Если лежат по одну сторону, то [A_i , A_j] является частью границы выпуклой оболочки и мы добавляем точки A_i , A_j к списку Q точек, принадлежащих выпуклой оболочке (при этом, мы за линейное время проверяем, есть ли эти точки уже в списке, и если есть, то добавление не происходит), а отрезок [A_i , A_j] к списку отрезков R.

2. Далее за кубическое время выбрасываем из полученного списка Q все такие точки A, что в списке Q есть точки B и C такие, что A, B, C лежат на одной прямой и A находится между B и C. Т.о. в списке Q останутся только вершины многоугольника выпуклой оболочки.

3. Далее в списке R оставляем только отрезки с вершинами из Q (это можно сделать за кубическое время, исходя из того, что в списке отрезков O(N²) элементов, а в списке вершин O(N) элементов).

4. Теперь для каждой вершины T многоугольника M в списке R находится всего два отрезка с концом в T и мы имеем возможность за квадратичное время восстановить последовательность вершин и ребер многоугольника M.

По построению данный алгоритм будет работать за время O(N³).

Следует отметить, что выбранные в алгоритме отрезки [A_i , A_j] не обязаны быть ребрами многоугольника выпуклой оболочки, но обязаны им (ребрам) принадлежать. В обосновании алгоритма также используется следующий факт, который элементарно доказать: каждое ребро многоугольника выпуклой оболочки является одной из выбранных выше пар точек A_i , A_j.

Теорема 3. В рамках алгоритмов, основанных на сравнениях, j(N)=O(N log N) является нижней оценкой времени решения задачи нахождения многоугольника выпуклой оболочки множества точек {A₁ ,…, A_N }.

Для доказательство теоремы докажем, что задача сортировки сводится к задаче нахождения выпуклой оболочки за время O(N). Рассмотрим множества вещественных чисел {x₁ ,…, x_N }. На числовой плоскости построим множество точек {(x₁ , x₁²), (x₂ , x₂²)…, (x_N , x_N²) }. Т.е. каждой точке x_i сопоставим точку на стандартной параболе (x_i , x_i²). Для построенного множества точек решим задачу построения выпуклой оболочки. Найдем точку (x_i , x_i²) с минимальным значением x_i. Последовательный перебор вершин построенного многоугольника даст набор точек с отсортированными значениями x_j .

¢

Теорема 4. Пусть M – выпуклая оболочка множества точек {A₁ ,…, A_N }. P – внутренняя точка некоторого треугольника (A_i,A_j,A_k), то P – внутренняя точка M.

Доказательство теоремы элементарно: если P – внутренняя точка треугольника A_i,A_j,A_k, то она принадлежит данному треугольнику вместе с некоторой своей окрестностью O. A_i,A_j,A_k ÎM, M – выпукло, то [A_j,A_k]ÎM. Пусть для каждой точки XÎO точка S=[A_j,A_k]Ç [A_i,X], то SÎM, тогда [A_i,S]ÎM, тогда XÎM. Т.о. OÎM и P – внутренняя точка M.

¢

Для нахождения верхней оценки времени решения задачи нахождения выпуклой оболочки предъявим алгоритм, который решает данную задачу за время O(N log N), что докажет точность предъявленных верхней и нижней оценок.

Требуется найти выпуклую оболочку множества точек на плоскости {A₁ ,…, A_N } (N>2). За линейное время проверим, все ли точки лежат на одной прямой. Если все точки лежат на одной прямой, то задачу легко решить за линейное время. Иначе, выберем три точки, не лежащие на одной прямой и рассмотрим точку O – точку пересечения медиан треугольника с вершинами в найденных точках. По теореме 4 точка O будет лежать внутри выпуклой оболочки точек {A₁ ,…, A_N }.

Упорядочим множество точек {A₁ ,…, A_N } лексикографически по паре значений (полярный угол, расстояние от O до данной точки) (пусть угол отсчитывается по часовой стрелке), отсчитываемому от точки O. Обозначим отсортированное множество точек {B₁ ,…, B_N }. Будем считать, что B₁ – самая левая точка в множестве (точка с минимальной абсциссой). Этого легко добиться циклическим сдвигом полученного отсортированного множества точек. Легко увидеть, что B₁ лежит на границе выпуклой оболочки. Для доказательства этого рассмотрим луч, направленный вверх из B, B₁Q и точку B_k с минимальным углом QB₁B_k. Пусть B₁Q’ – луч направленный из B₁ вниз. Все остальные точки из рассматриваемого множества будут лежать в угле Q’B₁B_k, т.е. все они будут лежать в одной полуплоскости с границей (B₁B_k). Тогда по теореме 2 [B₁B_k] принадлежит границе выпуклой оболочки точек {A₁ ,…, A_N }.

Будем последовательно перебирать точки B_i и добавлять их к двусвязному списку L граничных точек выпуклой оболочки. На каждом шаге (после добавления точки B_i к границе M) будем проверять точку B_i-1 на величину угла α=(B_i-2 B_i-1 B_i) (угол отсчитывается против часовой стрелки). Если α≥180, то точка B_i-1 исключается из списка L и процедура проверки выполняется заново до тех пор, пока точка B_i-1 не останется в списке. После этого переходим на следующий шаг добавления точки к списку. Полученная в конце обхода последовательность точек {B_i1, B_i2, …,B_ik} будет последовательностью вершин многоугольника выпуклой оболочки.

Для обоснования этого факта надо заметить, что полученный многоугольник будет выпуклым (т.к. все его углы <180). Пусть {B_m1, B_m2, …,B_ml} – последовательность вершин многоугольника выпуклой оболочки {B₁, B₂, …,B_N}. Доказательство корректности данного алгоритма строится по индукции на основе простого факта: для любого j: m_k<j<m_(k+1) верно: B_jÎD(O,B_mk,B_m(k+1)), гдеD(O,B_mk,B_m(k+1)) – треугольник с вершинами O,B_mk,B_m(k+1) без отрезка [O,B_mk].

B_m1= B_i1 (i₁= m₁=1) и эта точка не будет удалена из создаваемого списка точек по построению. Таким образом мы получаем основание индукции.

Пусть в процессе построения списка точек B_mk= B_ik. Из вышеприведенного факта непосредственно следует, что при последующем построении списка точек B_mk не будет исключена из списка (отметим, что если бы мы изначально упорядочивали последовательность точек только по полярному углу, то вышеприведенный факт не имел бы место, и данное свойство не было бы верным). При переборе точек в какой-то момент мы дойдем до точки B_m(k+1) и по построению и по вышеприведенному факту ни одна из точек A_j (m_k<j<m_(k+1)) не останется в списке. Что завершает обоснование шага индукции.

В описанном алгоритме мы добавляем к списку не более N точек и удаляем из списка не более N точек, поэтому процедура обхода полученного множества точек {B₁ ,…, B_N } выполняется за линейное время. Данная процедура обхода носит название обхода Грэхема.

Итак, алгоритм, использующий упорядочивание точек по полярному углу и обход Грэхема получившейся последовательности точек, имеет верхнюю оценку времени работы F(N)=O(N log N).

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

Для улучшения (неулучшаемой J ) оценки имеет смысл рассмотреть частный случай: пусть количество ребер выпуклой оболочки малО. Тогда имеет смысл построить алгоритм создания выпуклой оболочки, имеющий другую верхнюю оценку времени работы алгоритма. В худшем случае данный алгоритм будет работать медленнее алгоритма на основе обхода Грэхема, но если количество ребер многоугольника выпуклой оболочки будет существенно меньше log N, то алгоритм окажется более успешным (например, в случае, когда есть уверенность, что многоугольник выпуклой оболочки имеет O(1) ребер). Данный алгоритм носит название алгоритма на основе обхода Джарвиса или алгоритм заворачивания подарка. Идея алгоритма проста: на k-м шаге алгоритма мы имеем k последовательных точек границы выпуклой оболочки {p₁,…,p_k} множества точек {A₁ ,…, A_N }.Следующая точка p_k+1 ищется из соображений минимальности величины пары (угол между лучами [p_k-1, p_k) и [p_k, x), расстояние от p_k до x) (здесь обход идет по часовой стрелке и угол отсчитывается по часовой стрелке), где в качестве x рассматриваются все оставшиеся точки множества {A₁ ,…, A_N }. Пары сравниваются лексикографически (т.е. сначала сравнивается угол, а если углы равны, то сравниваются расстояния). Исходя из построения алгоритма, имеем следующую теорему о времени работы данного алгоритма.

Теорема 5. Алгоритм построения выпуклой оболочки множества точек {A₁ ,…, A_N } на основе обхода Джарвиса имеет верхнюю оценку времени работы алгоритма F(N)=O(N M), где M – количество ребер границы многоугольника выпуклой оболочки.