Алгоритм замітання прямою
Алгоритм замітання прямою або алгоритм замітання площини — це алгоритмічна парадигма, яка використовує уявну замітальну пряму або замітальну поверхню для розв'язування різних задач у евклідовому просторі. Це одна з ключових технік обчислювальної геометрії.
Ідея алгоритмів цього типу полягає у використанні уявної прямої (частіше вертикальної), яка рухається площиною і зупиняється у деяких точках, де відбуваються обчислення. Геометричні операції обмежені геометричними об'єктами, які або перетинаються, або прилягають до замітальної прямої, а повний розв'язок доступний, коли пряма пройде через усі об'єкти.
Історія ред.
Цей підхід можна простежити від алгоритмів порядкового сканування в комп'ютерній графіці, потім його використано в ранніх алгоритмах компонування інтегральних схем, у яких геометричний опис інтегральної схеми робився у вигляді паралельних смужок, оскільки повний опис не поміщався в пам'ять.
Застосування ред.
Застосування цього підходу призвело до прориву в обчислювальній складності геометричних алгоритмів, коли Шеймос і Гоуї (англ. Dan Hoey) представили алгоритми пошуку перетину відрізків на площині, і, зокрема, вони описали, як комбінація підходу замітання прямою з ефективними структурами даних (збалансованими двійковими деревами) дозволяє виявити, чи є перетини N відрізків на площині, зі складністю O [1]. Тісно пов'язаний алгоритм Бентлі — Оттманна використовує техніку замітання прямою, щоб отримати всі K перетинів серед будь-яких N відрізків на площині з часовою складністю та складністю за пам'яттю [2].
Відтоді цей підхід використовувався в розробці ефективних алгоритмів для низки задач, таких як побудова діаграми Вороного (алгоритм Форчуна) і тріангуляції Делоне або булевих операцій над многокутниками.
Узагальнення та розширення ред.
Топологічне замітання — це вид замітання площини з ослабленням вимог до порядку опрацювання точок, що дозволяє уникнути повного сортування точок і дозволяє алгоритму замітання прямою працювати ефективніше.
Техніку обертового кронциркуля[en] для побудови геометричних алгоритмів можна вважати різновидом замітання в проєктивно двоїстій площині — проєктивна двоїстість перетворює нахил прямої в площині в x-координату точки в двоїстій площині, так що проходження прямої упорядковано за її нахилом. Таким чином, алгоритм обертового кронциркуля є двоїстим для процесу проходження через точки, відсортовані за їх x-координатами, в алгоритмі замітання площини.
Підхід «замітання» можна узагальнити для більших розмірностей.
Примітки ред.
- ↑ Shamos, Hoey, 1976, с. 208–215.
- ↑ Souvaine, 2008.
Література ред.
- Michael I. Shamos, Dan Hoey. Geometric intersection problems // Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76). — 1976. — С. 208–215. — DOI:
- Diane Souvaine. Line Segment Intersection Using a Sweep Line Algorithm. — 2008.