Пусть задано некоторое множество точек на плоскости. Выпуклая оболочка - наименьший выпуклый многоугольник, содержащий данные точки. Вообразим, что плоскость - это деревянная доска, утыканная гвоздями в каждой точке из данного множества. Теперь натянем вокруг гвоздей резиновое кольцо. Оно стянется и образует выпуклую оболочку, как показано на рисунке выше. Выпуклые оболочки очень важны в ряде геометрических положений не только сами по себе, но и как части других алгоритмов, использующих построение выпуклой оболочки в качестве элементарной операции. Асимптотика числа вершин выпуклой оболочки для n точек, равномерно распределенных внутри единичного круга - Theta(n1/3) равномерно распределенных внутри фиксированного выпуклого многоугольника - Theta(log n) подчиненных двумерному нормальному распределению - Theta((log n)1/2) В оценках ниже n - количество точек, h - количество точек выпуклой оболочки. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  Gift wrapping Простой алгоритм, время работы: Лучший случай, все точки внутри оболочки: O(n) Худший случай, все точки на оболочке: On2) Среднее время: nh 8  Алгоритм Грэхема Алгоритм состоит из двух частей: сначала точки сортируются по полярному углу - O(nlogn). Если взять точки в порядке возрастания полярного угла, то получается простой многоугольник. Выпуклую оболочку произвольного простого многоугольника за O(n) находит вторая часть алгоритма. 8  Алгоритм Мелькмана Находит выпуклую оболочку простого многоугольника за O(n) операций. 8  Quickhull Рекурсивный, простой алгоритм. На случайном наборе точек этот алгоритм работает быстрее всех. 8  Разделяй-и-властвуй

8  Gift wrapping 8  Алгоритм Грэхема 8  Алгоритм Мелькмана 8  Quickhull 8  Разделяй-и-властвуй