06.11.2020

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


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

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

История

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

Приложения

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

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

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

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

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

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


Похожие новости:

Функция Гёделя

Функция Гёделя
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел. Определение Функцией Геделя Γ ( x

Болезни прямой кишки (часть 2)

Болезни прямой кишки (часть 2)
Выпадение прямой кишки. Выпадением прямой кишки называется выпячивание из заднепроходного отверстия большей или меньшей части прямой кишки, причем она вывернута слизистой оболочкой наружу. Выпадение

Болезни прямой кишки (часть 1)

Болезни прямой кишки (часть 1)
Врожденные ненормальности прямой кишки. К ним можно отнести отсутствие заднепроходного отверстия (ануса) и свищ в мочевой пузырь или влагалище. Отсутствие заднего прохода наблюдают у новорожденных

Исследование через прямую кишку (часть 2)

Исследование через прямую кишку (часть 2)
При появлении сильного сокращения кишки следует воздержаться от дальнейшей пальпации до наступления расслабления. Грубая пальпация и неосторожное продвижение руки могут вызвать разрыв кишки.
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Как выбрать двухъярусную кровать для детей
Как выбрать двухъярусную кровать для детей
При обустройстве детской спальни родители всегда особое внимание уделяют выбору спального места –...
Как выбрать обувницу в прихожую
Как выбрать обувницу в прихожую
Правильное хранение обуви обеспечит сохранность вещей, надлежащее санитарное состояние прихожей....
Создание вентиляции промышленных помещений – выбираем надежную компанию
Создание вентиляции промышленных помещений – выбираем надежную компанию
Создание эффективной вентиляционной системы является достаточно сложным процессом, требующим...
Все новости