Алгоритм Киркпатрик , предложенный ее авторы как потенциальный «конечный планарные выпуклым алгоритм корпуса», является алгоритмом для вычисления выпуклой оболочки набора точек на плоскости, с временная сложность , где количество входных точек и - количество точек (недоминируемых или максимальных точек, как это называется в некоторых текстах) в корпусе. Таким образом, алгоритм чувствителен к выводам : время его работы зависит как от размера ввода, так и от размера вывода. Другой алгоритм, чувствительный к выходным данным, алгоритм упаковки подарков , был известен намного раньше, но алгоритм Киркпатрика – Зейделя имеет асимптотическое время работы, которое значительно меньше и всегда улучшаетграницы алгоритмов, не чувствительных к выходу. Алгоритм Киркпатрика – Зайделя назван в честь его изобретателей Дэвида Г. Киркпатрика и Раймунда Зайделя . [1]
Хотя алгоритм является асимптотически оптимальным, он не очень практичен для задач среднего размера. [2]
Алгоритм
Основная идея алгоритма - это своего рода реверсия алгоритма « разделяй и властвуй» для выпуклых оболочек Препараты и Хонга, названного авторами «браком до завоевания».
Традиционный алгоритм «разделяй и властвуй» разделяет входные точки на две равные части, например, вертикальной линией, рекурсивно находит выпуклые оболочки для левого и правого подмножеств входных данных, а затем объединяет две оболочки в одну, находя " края моста », боковые касания , соединяющие два корпуса сверху и снизу.
Алгоритм Киркпатрик разбивает входной сигнал , как и прежде, путем нахождения медианы из х -координат входных точек. Однако алгоритм меняет порядок последующих шагов: его следующий шаг - найти ребра выпуклой оболочки, которые пересекают вертикальную линию, определяемую этой медианной координатой x, что, как оказывается, требует линейного времени. [3] Точки на левой и правой сторонах линии разделения, которые не могут повлиять на конечную оболочку, отбрасываются, и алгоритм рекурсивно переходит к оставшимся точкам. Более подробно, алгоритм выполняет отдельную рекурсию для верхней и нижней частей выпуклой оболочки; в рекурсии для верхнего корпуса отбрасываются точки, не входящие в состав моста, те, которые находятся ниже края моста по вертикали, тогда как в рекурсии для нижнего корпуса отбрасываются точки над краем моста по вертикали.
На -го уровня рекурсии алгоритм решает не более подзадачи, каждая размером не более . Общее количество рассмотренных подзадач не более, поскольку каждая подзадача находит новое выпуклое ребро оболочки. Наихудший случай имеет место, когда никакие точки нельзя отбросить, а подзадачи настолько велики, насколько это возможно; то есть когда есть ровно подзадачи на каждом уровне рекурсии до уровня . В этом наихудшем случае есть уровни рекурсии и баллы учитываются на каждом уровне, поэтому общее время работы составляет как указано.
Смотрите также
Рекомендации
- ^ Киркпатрик, Дэвид G .; Зайдель, Раймунд (1986). «Окончательный алгоритм плоской выпуклой оболочки?». SIAM Journal on Computing . 15 (1): 287–299. DOI : 10.1137 / 0215021 . hdl : 1813/6417 .
- ^ Маккуин, Мэри М .; Туссен, Годфрид Т. (январь 1985 г.). «Об алгоритме окончательной выпуклой оболочки на практике» (PDF) . Письма о распознавании образов . 3 (1): 29–34. DOI : 10.1016 / 0167-8655 (85) 90039-X .
Результаты показывают, что, хотя алгоритмы O ( n Log h ) могут быть «окончательными» в теории, они имеют небольшую практическую ценность с точки зрения времени выполнения.
- ↑ Оригинальная статья Киркпатрика / Зайделя (1986), стр. 10, теорема 3.1