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

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

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

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

История

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

Приложения

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

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

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

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

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

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

Литература

• Michael I. Shamos, Dan Hoey. Geometric intersection problems // Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76). — 1976. — С. 208–215. — doi:10.1109/SFCS.1976.16.
• Diane Souvaine. Line Segment Intersection Using a Sweep Line Algorithm. — 2008.