Параллельный алгоритм нахождения выпуклой оболочки

Задача:

Пусть нам даны точки на плоскости. Нужно найти выпуклую оболочку на этих точках.

Определение:

Выпуклая оболочка — минимальная последовательность точек такая, что последовательное соединение этих точек дает выпуклый многоугольник, и в этом многоугольнике содержатся все точки.

Последовательный алгоритм

Как мы будем двигаться

Давайте первым делом найдем самую левую A (при нескольких таких выбрать нижнюю) и самую правую B (при нескольких таких выбрать самую верхнюю) точку на плоскости.

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

Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение за <tex>O(n)<\tex>.