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

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

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

Алгоритм

Эта секция нуждается в расширении с: псевдокод алгоритма. Вы можете помочь добавляя к этому. (Март 2018 г.)

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

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

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

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

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

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

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