Алгоритм Киркпатрика – Зейделя

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

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

Алгоритм

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

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

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

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

См. также

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

Ссылки

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

[1] Киркпатрик, Дэвид Г.; Зайдель, Раймунд (1986). «Идеальный алгоритм плоской выпуклой оболочки?». SIAM Journal по вычислительной технике . 15 (1): 287–299. дои : 10.1137/0215021 . hdl : 1813/6417 .

[2] МакКуин, Мэри М.; Туссен, Годфрид Т. (январь 1985 г.). «Об окончательном алгоритме выпуклой оболочки на практике» (PDF) . Буквы для распознавания образов . 3 (1): 29–34. Бибкод : 1985ПаРеЛ...3...29М . дои : 10.1016/0167-8655(85)90039-X . Результаты показывают, что, хотя алгоритмы O( n Log h ) могут быть «совершенными» в теории, они не имеют практической ценности с точки зрения времени работы.

[3] Оригинальная статья Киркпатрика/Зейделя (1986), стр. 10, теорема 3.1

[1]

[2]

[3]