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

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

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

Алгоритм

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

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

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

На ${\displaystyle i}$-го уровня рекурсии алгоритм решает не более ${\displaystyle 2^{i}}$ подзадачи, каждая размером не более ${\displaystyle {\frac {n}{2^{i}}}}$. Общее количество рассмотренных подзадач не более ${\displaystyle h}$, поскольку каждая подзадача находит новое выпуклое ребро оболочки. Наихудший случай имеет место, когда никакие точки нельзя отбросить, а подзадачи настолько велики, насколько это возможно; то есть когда есть ровно ${\displaystyle 2^{i}}$ подзадачи на каждом уровне рекурсии до уровня ${\displaystyle \log _{2}h}$ . Для этого наихудшего случая есть ${\displaystyle {\mathcal {O}}(\log h)}$ уровни рекурсии и ${\displaystyle {\mathcal {O}}(n)}$ баллы учитываются на каждом уровне, поэтому общее время работы ${\displaystyle {\mathcal {O}}(n\log h)}$ как указано.

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

• Алгоритмы выпуклой оболочки

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

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