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

Постановка задачи

Для точек a₁, …, a_n, где n≥1, a_i=(a_i,1, a_i,2)ÎR² при i=1, …, n, указать вершины b₁, …, b_m выпуклой оболочки Conv(a₁, …, a_n) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a₁, …, a_n) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки - сама эта точка.

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

Для решения задачи (см. [3]) построения Conv(a₁, …, a_n) мы из точек a₁, …, a_n выберем точки с минимальной первой координатой, среди которых затем найдем точку c, имеющую минимальную вторую координату. Таким образом, точка c= lexmin(a₁, … ,a_n) является лексикографическим минимумом точек a₁, … ,a_n и поэтому представляет собой вершину выпуклой оболочки Conv(a₁, …, a_n). Именно с нее мы и начнем обход границы против часовой стрелки, положив b₁=c и осуществив перед этим для удобства промежуточных вычислений параллельный перенос системы координат так, чтобы ее начало совпало с точкой c. После такого переноса на точках a₁, …, a_n удается определить такой линейный порядок ( ≤ ), что для c₁,c₂ Î{a₁-c, … ,a_n–c} имеет место c₁ ≤ c₂, если либо det(c₁,c₂)>0, либо (det(c₁,c₂)=0)&( (c_1,1)²+(c_1,2)²) < (c_2,1)²+(c_2,2)² ).

Геометрический смысл такого упорядочения можно проиллюстрировать, если ввести полярную систему координат φ, r (-p<φ ≤p, r³0) с центром в точке c и далее положить, что c₁ ≤ c₂, если (φ₁,r₁) лексикографически не превосходит (φ₂,r₂), где числа φ_i, r_i являются полярными координатами точки c_i, i = 1,2.

Таким образом, c₁ ≤ c₂, если либо φ₁ < φ_2, либо (φ₁ = φ₂ )&(r₁ ≤ r₂). Как только линейный порядок на элементах (точках) a₁, …, a_n определен, немедленно можно воспользоваться сортировкой, для того чтобы отсортировать эти элементы по неубыванию в соответствии с введенным линейным порядком. После этого мы произведем за время O(n) просмотр отсортированного массива с целью получения итоговых точек b₁, …, b_m исходя из того условия, что точка b_i+1 располагается строго слева от вектора, идущего из точки b_i-1 в точку b_i, что эквивалентно требованию того, чтобы det(b_i-b_i-1,b_i+1-b_i)>0.

Описанные действия конкретизируются алгоритмом, представляемым процедурой CONV_SORT (a, n), на вход которой подается массив точек a[1], …, a[n]. Итоговые точки b₁, …, b_m, являющиеся решением задачи, будут представлены в той же последовательности в первых m элементах a[1], …, a[m] массива a. Отметим также, что в процедуре CONV_SORT используется подпрограмма сортировки СОРТИРОВКА (a, n), выдающая отсортированный по неубыванию массив a.

procedure CONV_SORT (var a, n);

begin

c:= a[1]; m:= 1;

for i:= 2 to n do if a[i][1]<c[1] then begin

c:= a[i]; m:= i;

end else if a[i][1]=c[1] then if a[i][2]<c[2] then begin

c:= a[i]; m:= i;

end;

a[1]Ûa[m]; m:= 1;

for i:= 1 to n do a[i]:= a[i]-c;

СОРТИРОВКА(a, n);

for i:= 2 to n do if a[i] ¹ a[m] then begin

if m ³ 2 then while (m ³ 2)&(det(a[m]-a[m-1],a[i]-a[m]) £0) do m:= m-1;

m:= m+1; a[m]Ûa[i];

end;

for i:= 1 to m do a[i]:= a[i]+c;

end;

Временная сложность алгоритма построения выпуклой оболочки точек в случае, если используется СОРТИРОВКА с помощью d–кучи, где d³2, есть величина O(n×log n), если же используется быстрая СОРТИРОВКА, то временная сложность алгоритма оценивается сверху величиной O(n²), а в среднем алгоритм выполняется за время O(n×log n).

Задания для лабораторной работы № 6

Предлагается попарное сравнение различных использующих сортировку алгоритмов построения выпуклой оболочки n точек на плоскости с целочисленными координатами.

Варианты выбора пары алгоритмов A и B для сравнения:

Вариант d=2, …, 101

· А - используется сортировка d-кучей,

· В - используется сортировка (d+1)-кучей;

Вариант d=102, …., 200

· А - используется сортировка (d-100)-кучей,

· В - используется быстрая сортировка.

Задание.

1. Написать программу, реализующую алгоритм А и алгоритм В.

2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:

· количество n точек в исходном массиве a,

· натуральные числа q и w для псевдослучайного размещения всех n точек в двух режимах:

(1) в прямоугольнике со сторонами длиныq и w,

(2) на границе (на сторонах) этого прямоугольника.

Выходом данной программы должно быть время работы Т_А алгоритма А и время работы Т_В алгоритма В в секундах.

3. Провести эксперименты на основе следующих данных:

3.1. q = 10⁶, w = 10⁶, n = 1, …, 10⁶+1 с шагом 10⁴, размещение точек псевдослучайное:

· в режиме (1),

· в режиме (2)

(нарисовать графики функций T_А(n) и Т_В(n) для обоих случаев),

3.2. q = w = 0, …, 10⁶ с шагом 10⁴, n = 10⁶, размещение точек псевдослучайное:

· в режиме (1),

· в режиме (2)

(нарисовать графики функций T_А(n) и Т_В(n) для обоих случаев),

4. Сформулировать и обосновать вывод (на основе практических данных, для получения которых можно провести дополнительные эксперименты) о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.