Эффективные алгоритмы для задачи вертикальной видимости

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

Проблема: нам дан двумерный квадратный прямоугольник со стороной $n$ , стороны которого параллельны осям. Мы можем посмотреть на это через верх. Тем не менее, есть также $m$ горизонтальных сегментов. Каждый сегмент имеет целочисленную координату $y$ ( $0 \le y \le n$ ) и координаты $x$ ( $0 \le x_1 < x_2 \le n$ ) и соединяет точки $(x_1,y)$ и $(x_2,y)$ (посмотрите на картинка ниже).

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

$x \in \{0,\dots,n-1\}$$\max_{i:\ [x,x+1]\subseteq[x_{1,i},x_{2,i}]} y_i$

Пример: с учетом и m = 7 сегментов, расположенных, как на рисунке ниже, получается результат (5, 5, 5, 3, 8, 3, 7, 8, 7) . Посмотрите, как глубокий свет может попасть в коробку.$n=9$$m=7$$(5, 5, 5, 3, 8, 3, 7, 8, 7)$

К счастью для нас, как $n$ и $m$ является достаточно малы , и мы можем сделать вычисление офф-лайн.

Самым простым алгоритмом, решающим эту проблему, является перебор: для каждого сегмента пересекайте весь массив и обновляйте его при необходимости. Однако это дает нам не очень впечатляющий .$O(mn)$

Значительным улучшением является использование дерева сегментов, которое способно максимизировать значения в сегменте во время запроса и считывать окончательные значения. Я не буду описывать это дальше, но мы видим, что временная сложность составляет .$O((m+n) \log n)$

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

Контур:

1. Сортируйте сегменты в порядке убывания -координаты (линейное время, используя вариацию сортировки отсчета). Теперь обратите внимание, что если какой-либо сегмент единицы ранее был покрыт каким-либо сегментом, то ни один следующий сегмент больше не может ограничивать луч света, проходящий через этот сегмент единицы. Затем мы сделаем разметку линии сверху донизу коробки.х $y$$x$$x$

2. Теперь давайте введем несколько определений: сегмент единицы - это воображаемый горизонтальный сегмент на развертке, координаты которого являются целыми числами и длина которого равна 1. Каждый сегмент в процессе развертки может быть либо без опознавательных знаков (то есть луч света, идущий от верх коробки может доходить до этого сегмента) или отмечен (противоположный случай). Рассмотрим единичный сегмент с , всегда без опознавательных знаков. Давайте также введем множества . Каждый набор будет содержать целую последовательность последовательных отмеченных сегментов единиц (если они есть) с последующей неотмеченнойx x x 1 = n x 2 = n + 1 S 0 = { 0 } , S 1 = { 1 } , … , S n = { n } $x$$x$$x$$x_1=n$$x_2=n+1$$S_0=\{0\}, S_1=\{1\}, \dots, S_n=\{n\}$ $x$ сегмент.

3. Нам нужна структура данных, которая способна эффективно работать с этими сегментами и устанавливает их. Мы будем использовать структуру find-union, расширенную полем, содержащим максимальный индекс сегмента unit (индекс немаркированного сегмента).$x$

4. Теперь мы можем эффективно обрабатывать сегменты. Допустим, мы сейчас рассматриваем сегмент по порядку (назовем его «запрос»), который начинается в и заканчивается в . Нам нужно найти все немаркированные сегменты блока, которые содержатся внутри сегмента (это именно те сегменты, на которых луч света закончит свой путь). Мы сделаем следующее: во-первых, мы найдем первый немаркированный сегмент внутри запроса ( найдите представителя набора, в котором содержится и получите максимальный индекс этого набора, который по определению является немаркированным сегментом ). Тогда этот индексx 1 x 2 x i x 1 x y x x + 1 x ≥ x $i$$x_1$$x_2$ $x$$i$$x_1$$x$находится внутри запроса, добавьте его к результату (результат для этого сегмента - ) и отметьте этот индекс ( объединение наборов, содержащих и ). Затем повторяйте эту процедуру, пока мы не найдем все неотмеченные сегменты, то есть следующий запрос Find даст нам индекс .$y$$x$$x+1$$x \ge x_2$

Обратите внимание, что каждая операция find-union будет выполняться только в двух случаях: либо мы начинаем рассматривать сегмент (что может произойти раз), либо мы просто пометили сегмент unit (это может произойти раз). Таким образом, общая сложность равна ( - обратная функция Аккермана ). Если что-то не понятно, я могу подробнее остановиться на этом. Может быть, я смогу добавить несколько фотографий, если у меня будет время.x n O ( ( n + m ) α ( n ) ) $m$$x$$n$$O((n+m)\alpha(n))$$\alpha$

Теперь я достиг "стены". Я не могу придумать линейный алгоритм, хотя кажется, что он должен быть. Итак, у меня есть два вопроса:

• Существует ли алгоритм линейного времени (то есть ), решающий проблему видимости горизонтального сегмента?$O(n+m)$
• Если нет, что является доказательством того, что проблема видимости ?$\omega(n+m)$

1. Сначала сортировать как и координаты линий в двух отдельных массивов и . х 2 А Б О ( м $x1$$x2$$A$$B$$O(m)$
2. Мы также поддерживаем размер вспомогательного битового массива для отслеживания активных сегментов.$n$
3. Начните подметать слева направо:
4. для$(i=0,i<n,i++)$
5. {
6. ..if со значениемy c O ( 1 $\exists x1=i$$y$$c$ $O(1)$
7. .. {
8. .... найти ( )$\max$
9. .... магазин ( )O ( 1 $\max$$O(1)$
10. ..}
11. ..if со значениемy c O ( 1 $\exists x2=i$$y$$c$ $O(1)$
12. .. {
13. .... найти ( )$\max$
14. .... магазин ( )O ( 1 $\max$$O(1)$
15. ..}
16. }

find ( ) может быть реализован с использованием битового массива с битами. Теперь всякий раз, когда мы удаляем или добавляем элемент в мы можем обновить это целое число, установив бит в true или false соответственно. Теперь у вас есть две опции в зависимости от используемого языка программирования, и предположение относительно мало, то есть меньше, чем которое составляет не менее 64 бит или фиксированное количество этих целых чисел:п л п л о н г л ø н г я н $\max$$n$$L$$n$$long long int$

• Получение младшего значащего бита в постоянное время поддерживается некоторыми аппаратными средствами и gcc.
• Преобразовав в целое число вы получите максимум (не напрямую, но вы можете вывести его).O ( 1 $L$$O(1)$

Я знаю, что это довольно хак, потому что он принимает максимальное значение для и, следовательно, можно рассматривать как константу тогда ...$n$$n$

У меня нет линейного алгоритма, но кажется, что это O (m log m).

Сортировать сегменты по первой координате и высоте. Это означает, что (x1, l1) всегда предшествует (x2, l2) всякий раз, когда x1 <x2. Кроме того, (x1, l1) на высоте y1 предшествует (x1, l2) на высоте y2 всякий раз, когда y1> y2.

Для каждого подмножества с одинаковыми первыми координатами мы делаем следующее. Пусть первый отрезок будет (x1, L). Для всех других сегментов в подмножестве: Если сегмент длиннее первого, измените его с (x1, xt) на (L, xt) и добавьте его в L-подмножество в правильном порядке. В противном случае бросьте это. Наконец, если следующее подмножество имеет первую координату меньше, чем L, то разделите (x1, L) на (x1, x2) и (x2, L). Добавьте (x2, L) к следующему подмножеству в правильном порядке. Мы можем сделать это, потому что первый сегмент в подмножестве выше и охватывает диапазон от (x1, L). Этот новый сегмент может быть тем, который покрывает (L, x2), но мы не узнаем об этом, пока не посмотрим на подмножество, которое имеет первую координату L.

После того, как мы пройдем все подмножества, у нас будет набор сегментов, которые не перекрываются. Чтобы определить значение Y для данного X, нам нужно только пройти через оставшиеся сегменты.

Так в чем же здесь сложность: сортировка O (m log m). Цикл по подмножествам равен O (m). Поиск также O (м).

Таким образом, кажется, что этот алгоритм не зависит от n.