Алгоритм замітаючої прямої

Алгоритм замітання прямою або алгоритм замітання площини — це алгоритмічна парадигма, яка використовує уявну замітальну пряму або замітальну поверхню для розв'язування різних задач у евклідовому просторі. Це одна з ключових технік обчислювальної геометрії.

Анімація алгоритму Форчуна, методу замітання прямою для побудови діаграм Вороного.

Ідея алгоритмів цього типу полягає у використанні уявної прямої (частіше вертикальної), яка рухається площиною і зупиняється у деяких точках, де відбуваються обчислення. Геометричні операції обмежені геометричними об'єктами, які або перетинаються, або прилягають до замітальної прямої, а повний розв'язок доступний, коли пряма пройде через усі об'єкти.

Історія

Цей підхід можна простежити від алгоритмів порядкового сканування в комп'ютерній графіці, потім його використано в ранніх алгоритмах компонування інтегральних схем, у яких геометричний опис інтегральної схеми робився у вигляді паралельних смужок, оскільки повний опис не поміщався в пам'ять.

Застосування

Застосування цього підходу призвело до прориву в обчислювальній складності геометричних алгоритмів, коли Шеймос і Гоуї (англ. Dan Hoey) представили алгоритми пошуку перетину відрізків на площині, і, зокрема, вони описали, як комбінація підходу замітання прямою з ефективними структурами даних (збалансованими двійковими деревами) дозволяє виявити, чи є перетини N відрізків на площині, зі складністю O${\displaystyle (N\log N)}$. Тісно пов'язаний алгоритм Бентлі — Оттманна використовує техніку замітання прямою, щоб отримати всі K перетинів серед будь-яких N відрізків на площині з часовою складністю ${\displaystyle O((N+K)\log N)}$ та складністю за пам'яттю ${\displaystyle O(N)}$.

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

Узагальнення та розширення

Топологічне замітання — це вид замітання площини з ослабленням вимог до порядку опрацювання точок, що дозволяє уникнути повного сортування точок і дозволяє алгоритму замітання прямою працювати ефективніше.

^[en] для побудови геометричних алгоритмів можна вважати різновидом замітання в проєктивно двоїстій площині — проєктивна двоїстість перетворює нахил прямої в площині в x-координату точки в двоїстій площині, так що проходження прямої упорядковано за її нахилом. Таким чином, алгоритм обертового кронциркуля є двоїстим для процесу проходження через точки, відсортовані за їх x-координатами, в алгоритмі замітання площини.

Підхід «замітання» можна узагальнити для більших розмірностей.

Примітки

1. Shamos, Hoey, 1976, с. 208–215.
2. Souvaine, 2008.

Література

• 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.