Алгоритм заметающей прямой

Алгоритм заметающей прямой или алгоритм выметания плоскости — это алгоритмическая парадигма, которая использует умозрительную выметающую прямую или выметающую поверхность для решения различных задач в евклидовом пространстве. Это одна из ключевых техник в вычислительной геометрии.

Анимация алгоритма Форчуна, техники заметающей прямой для построения диаграмм Вороного.

Идея алгоритмов этого типа заключается в представлении себе воображаемой прямой (чаще вертикальной), которая движется по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничены геометрическими объектами, которые или пересекаются, или примыкают к выметающей прямой, а полное решение доступно, когда прямая пройдёт через все объекты.

История

Этот подход можно отследить от алгоритмов построчного сканирования в компьютерной графике, затем этот подход использовался в ранних алгоритмах компоновки интегральных схем, в которых геометрическое описание интегральной схемы проводилось в виде параллельных полосок, поскольку полное описание не помещалось в память.

Приложения

Применение этого подхода привело к прорыву в вычислительной сложности геометрических алгоритмов, когда Шамос и Хоуи представили алгоритмы для пересечения отрезков на плоскости, и, в частности, они описали, как комбинация подхода сканирующей прямой с эффективными структурами данных (сбалансированных бинарных деревьев) делает возможным обнаружить, имеются ли пересечения N отрезков на плоскости, со сложностью O[1]. Тесно связанный алгоритм Бентли — Оттманна использует технику выметающей прямой, чтобы получить все K пересечений среди любых N отрезков на плоскости с временной сложностью и сложностью по памяти [2].

С того времени этот подход использовался для разработки эффективных алгоритмов для ряда задач, таких как построение диаграммы Вороного (алгоритм Форчуна) и триангуляции Делоне или булевых операций над многоугольниками.

Обобщения и расширения

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

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

Подход «выметания» может быть обобщён для более высоких размерностей.

Примечания
  1. Shamos, Hoey, 1976, с. 208–215.
  2. Souvaine, 2008.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.