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

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

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

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

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

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

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

Техника вращающегося кронциркуля^[англ.] для построения геометрических алгоритмов может также быть проинтерпретирована как вид выметания в проективной двойственной плоскости — проективная двойственность преобразует наклон прямой в плоскости в 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.