Покрытие прямоугольника Sweep Line

Мне дали упражнение, к сожалению, я сам не справился.

Существует множество прямоугольников и прямоугольник R 0 . Используя алгоритм подметания плоскости, определите, полностью ли покрыто R 0 набором R 1 . , R n .$R_{1}..R_{n}$$R_{0}$$R_{0}$$R_{1}..R_{n}$

Более подробную информацию о принципе алгоритмов стреловидной линии смотрите здесь .

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

• набор точек событий (он хранит конечные точки сегментов и точек пересечений)$Q$
• состояние (динамическая структура для множества сегментов, пересекающих линию развертки)$T$

Общая идея: предположим, что линия развертки - это вертикальная линия, которая начинает приближаться к набору прямоугольников слева. Сортируйте все координаты x прямоугольников и сохраняйте их в Q в возрастающем порядке - нужно взять O ( n log n ) . Начните с первой точки события, для каждой точки определите набор прямоугольников, которые пересекаются с заданной координатой x , идентифицируйте непрерывные сегменты прямоугольников пересечения и проверьте, полностью ли они покрывают R 0 в текущей координате x . С T в качестве двоичного дерева это займет O ( $l$$x$$Q$$O(n\log n)$$x$$R_{0}$$x$$T$ . Если какая-либо часть R 0 остается открытой, то R 0 не полностью покрыта.$O(\log n)$$R_{0}$$R_{0}$

Детали: Идея алгоритма пересечения сегментов заключалась в том, что пересекаются только смежные сегменты. Основываясь на этом факте, мы создали статус и поддерживали его в течение всего алгоритма. Я попытался найти аналогичную идею в этом случае, и пока безуспешно, единственное, что я могу сказать, это то, что два прямоугольника пересекаются, если их соответствующие координаты x и y перекрываются.$T$$x$$y$

$T$$T$

$T$

$n$$R_i$$i\ge 1$

• $R_i$$R_i$
• $R_i$$R_i$

$O(\log n)$

$R_0$$R_0$$O(n\log n)$$O(n)$

В общем случае очевидный трюк не такой быстрый. Используйте стандартный алгоритм линии развертки, чтобы вычислить все плоское подразделение, индуцированное прямоугольниками.

$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$ по размеру, поэтому мы используем столько места в худшем случае, поэтому время является «экзистенциально оптимальным», но не «чувствительным к выходу».

$R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

$O(n\log n)$$O(n^2\log n)$