Алгоритм Киркпатрика – Зейделя - Википедия - Kirkpatrick–Seidel algorithm

В Алгоритм Киркпатрика – Зейделя, предложенный его авторами как потенциальный «алгоритм окончательной плоской выпуклой оболочки», является алгоритм для вычисления выпуклый корпус множества точек на плоскости, с временная сложность, куда количество входных точек и - количество точек (недоминируемых или максимальных точек, как называется в некоторых текстах) в корпусе. Таким образом, алгоритм чувствительный к выходу: время его работы зависит как от размера ввода, так и от размера вывода. Другой алгоритм, чувствительный к выходу, алгоритм упаковки подарков, был известен намного раньше, но алгоритм Киркпатрика – Зайделя имеет асимптотическое время работы, которое значительно меньше и всегда улучшает границы алгоритмов, не чувствительных к выходу. Алгоритм Киркпатрика – Зейделя назван в честь его изобретателей, Дэвид Г. Киркпатрик и Раймунд Зайдель.[1]

Хотя алгоритм является асимптотически оптимальным, он не очень практичен для задач среднего размера.[2]

Алгоритм

Основная идея алгоритма - это своего рода разворот алгоритм разделяй и властвуй для выпуклой оболочки Препарата и Хонг, названный авторами «браком до завоевания».

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

Алгоритм Киркпатрика – Зейделя разделяет вход, как и раньше, путем нахождения медиана из Икс-координаты точек входа. Однако алгоритм меняет порядок последующих шагов: его следующий шаг - найти края выпуклой оболочки, которые пересекают вертикальную линию, определяемую этой медианной координатой x, что, как оказывается, требует линейного времени.[3] Точки на левой и правой сторонах линии разделения, которые не могут повлиять на конечную оболочку, отбрасываются, и алгоритм рекурсивно переходит к оставшимся точкам. Более подробно, алгоритм выполняет раздельную рекурсию для верхней и нижней частей выпуклой оболочки; в рекурсии для верхнего корпуса отбрасываются нерасширяющие точки, расположенные ниже края моста по вертикали, тогда как в рекурсии для нижнего корпуса отбрасываются точки над краем моста по вертикали.

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

Смотрите также

Рекомендации

  1. ^ Киркпатрик, Дэвид Дж .; Зайдель, Раймунд (1986). «Окончательный алгоритм плоской выпуклой оболочки?». SIAM Журнал по вычислениям. 15 (1): 287–299. Дои:10.1137/0215021. HDL:1813/6417.
  2. ^ Маккуин, Мэри М .; Туссен, Годфрид Т. (январь 1985 г.). «Об алгоритме конечной выпуклой оболочки на практике» (PDF). Письма с распознаванием образов. 3 (1): 29–34. Дои:10.1016 / 0167-8655 (85) 90039-X. Результаты показывают, что хотя O (п Бревно час) алгоритмы могут быть «окончательными» в теории, они имеют небольшую практическую ценность с точки зрения времени выполнения.
  3. ^ Оригинальная статья Киркпатрика / Зайделя (1986), стр. 10, теорема 3.1