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

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

История

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

Приложения

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

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

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

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

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

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

Примечания

Литература

• Michael I. Shamos, Dan Hoey. Geometric intersection problems // Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76). — 1976. — С. 208–215. — doi : .
• Diane Souvaine. . — 2008.