Эффективные объединения и пересечения в 2D-плоскости, когда y_min = 0

Question

Если возникла следующая проблема:

Учитывая серию прямоугольников, определенных {x_min, height и x_max}, я хочу эффективно вычислить их пересечение и объединение, создав новую серию. Например, если я получу S1 = [{1,3,3}] и S2 = [{2,3,5}], объединение приведет к S3 = [{1,3,5}] и пересечению в S3 = [{2,3,3}]. Это был бы довольно простой случай, но когда S1 и S2 представляют собой список прямоугольников (неупорядоченный). Это становится немного сложнее.

Моя идея - попытаться использовать стратегию «разделяй и властвуй», например, используя модифицированную сортировку слиянием, и на этапе слияния попробуйте также объединить эти здания. Но я немного не уверен, как это сделать. В принципе, я не могу написать, как сравнить два прямоугольника с этими координатами и решить, должны ли они быть в S3, или мне нужно создать новый (для пересечения).

Для объединения I Я думаю, что идея должна быть довольно похожа, но отрицание (то есть, если они не интересуют) сортировать это. В настоящее время мой первый подход - O (n ^ 2).

Любая помощь, как уменьшить сложность?

PD: Реализация, которую я делаю, находится в Python

Answer 1

Я попытался записать все это в псевдокоде и обнаружил, что он был слишком псевдо-y, чтобы быть полезным, и слишком кодирован, чтобы быть читаемым. Вот основная идея c:

Вы можете отсортировать каждый из своих входных списков в O (n * log (n)).

Поскольку мы предполагаем, что в каждой серии нет перекрытий, теперь мы можем заменить каждый из этих списков списками вида {start, height}. Мы можем отбросить атрибут "end", если начать с элемента height-0 там, где должен был закончиться последний элемент . (или нет, если два элемента уже прилегали.)

Теперь вы можете пройти / рекурсировать / пролистать оба списка за один проход, создавая новый список выходных данных {start, height}, как вы go. Я не вижу причин, по которым вы не могли бы одновременно создавать списки объединения и пересечения.

Очистка (преобразование в минимальное представление в исходном формате) будет еще одним проходом, но все равно O (n) .

Так что проблема в O (n * log (n)), и может быть в O (n), если бы вы могли найти способ предварительно отсортировать ввод.