Конспект: заметающая прямая и двойственность

Понятия

Заметающая прямая - вертикальная прямая, которая идёт по плоскости слева направо и останавливается в событиях.

Событие - место, где что-то меняется: начало и конец отрезка, точка пересечения. Очередь событий упорядочена по x.

Статус - то, что прямая пересекает сейчас, в порядке, удобном для запросов: число, набор высот, отрезки по высоте.

Двойственность - точка (a, b) ↔ прямая y = a·x − b, прямая y = m·x + c ↔ точка (m, −c).

Конфигурация прямых - разбиение плоскости n прямыми на вершины, рёбра и грани.

Что унести

ЗАМЕТАНИЕ
события по x; порядок равных - по смыслу задачи
    встречи [s, e): при равном времени конец раньше начала
    замкнутые отрезки: начало, запрос, конец
статус меняется на один объект за событие → n · log n вместо n²
восемь встреч: 3 комнаты, впервые в 9:45
150 + 150 дорожек: 66 пересечений, 2932 шага Фенвика, 22 500 пар

ЕСТЬ ЛИ ПЕРЕСЕЧЕНИЕ (Шамос, Хой, 1976)        O(n · log n)
статус - активные отрезки снизу вверх
вставка по левому концу p: двоичный поиск, сравнение - поворот p
левый конец:  вставить, проверить с соседом снизу и сверху
правый конец: удалить, проверить бывших соседей друг с другом
почему хватает: перед самой левой точкой пересечения
    её отрезки становятся соседями
400 отрезков без пересечений: 920 проверок против 79 800 пар

ВСЕ ПЕРЕСЕЧЕНИЯ (Бентли, Оттман, 1979)        O((n + k) · log n)
+ событие «точка»: записать, поменять соседей местами,
  проверить новых соседей снизу и сверху
точку кладут в очередь, когда пара стала соседями и
    пересекается правее прямой; найденные пары помнить
точки - дробью (числитель, знаменатель), сравнение - крест-накрест
40 коротких: k = 11, 59 проверок;  40 длинных: k = 149, 377 из 780
k порядка n² - перебор пар выгоднее
оптимум n · log n + k - Шазелл, Эдельсбруннер (1992)
наложение карт и булевы операции: пересечения + двусвязный
    список рёбер

ДВОЙСТВЕННОСТЬ
сохраняет «лежит на» и «выше / ниже»
три точки на прямой  ↔  три прямые через точку
нижняя огибающая прямых  ↔  нижняя оболочка точек (m, c)
    равные наклоны: для минимума оставить меньший c
    60 тарифов → 5 на огибающей
конфигурация n прямых: вершин n(n − 1)/2, рёбер n², граней
    n(n + 1)/2 + 1; строится за O(n²) (теорема о зоне)
три точки на прямой: группировка направлений по НОД, O(n²);
    трудна для 3SUM (Гаджентаан, Овермарс, 1995)
40 точек: 71 тройка, 780 шагов против 9880

Ловушки джокера

Порядок равных событий наугад. Встречи «впритык» требуют лишней комнаты, касание концом то засчитывается, то нет.

Проверка только при вставке. Пара, разделённая третьим отрезком, становится соседями при его удалении.

Высоты в float для сравнения в статусе. Отрезок встаёт не на своё место - решает поворот.

Точка пересечения в float в очереди. Почти равные события меняются местами, и обмен ломает статус.

Без памяти о найденных парах. Пара, сошедшаяся дважды, обрабатывается дважды.

Бентли-Оттман при k порядка n². Он проигрывает перебору пар.

Наклоны дробями при группировке направлений. Округление разносит одно направление по двум группам.

Проверь себя

Что такое событие и статус и почему статус меняется на один объект за событие? Почему пересечься могут только соседи по высоте и почему проверка при удалении обязательна? Как Бентли-Оттман узнаёт о точках пересечения, которых нет в начале? Когда он выгоднее перебора? Что сохраняет двойственность и почему огибающая прямых - это оболочка точек? Сколько граней у конфигурации n прямых?

DCEL: у полуребра начало, близнец, next/prev и грань слева; у грани представитель каждой компоненты. Наложение требует разрезать рёбра и перенести пары исходных меток.

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий