Как найти верхние огибающие пересекающихся линий в O (nlogn)?

Ответ 1

Сначала мы построим два разных дерева двоичного поиска для строк, одно с линиями, отсортированными по их a, а другое в соответствии с их b.

Теперь мы начинаем рассматривать линии lmin, lmax, которые являются линиями с наименьшим и самым большим a; они будут вносить свой вклад с точками, указанными на пересечениях со второй самой маленькой и второй по величине линиями, и мы добавим к этим двум точкам верхнюю огибающую.

Теперь рассмотрим пересечение (xi,yi) между lmin и lmax, и мы идеально рисуем вертикальную линию x = xi. Теперь мы должны идентифицировать линии, которые пересекают x = xi в координате y0 s.t. y0 <= yi и удаляют все эти строки из обоих деревьев.

Как мы можем идентифицировать эти строки? Мы находим все строки с b s.t. lmin <= b <= lmax, используя второе дерево.

В конце мы также удалим lmin и lmax из деревьев.

Теперь мы займемся новыми полученными деревьями.

Ответ 2

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

Решение. Если вы обрабатываете каждую строку y=ax+b как точку (a,b) и добавляете дополнительную "точку" в (0, -infinity), вы должны иметь возможность подавать ее в любой алгоритм двумерного выпуклого корпуса и получать правильное решение.

Примечание. Напротив, любое решение этой проблемы также может быть использовано для построения 2D-выпуклого алгоритма оболочки того же O().

Изменить: запрос на его подтверждение...

Если точка (x,y) находится над определенной линией y=ax+b, у вас есть неравенство ax - y + b > 0.

Это неравенство также эквивалентно тому, что точка (-a,b) находится над линией (b)=x(-a)+y, где x - наклон, а y - перехват.

Этот duality позволяет рассматривать точки как линии и линии как точки: любое доказательство или алгоритм на точках и линиях можно отобразить в одинаково действительный с перестановкой строк и точек.

В этом случае: выпуклая оболочка множества двумерных точек определяет "крайние" точки, которые не являются выпуклыми комбинациями других, а также линии между последовательными крайними точками. Соответственно, двойной вариант выпуклой оболочки определяет те "крайние" линии, которые не являются выпуклыми комбинациями других, а также точки пересечения между последовательными крайними линиями. Это огибающая данного набора строк.

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

Обратно, любое решение этой задачи может быть использовано для определения верхней выпуклой оболочки множества точек. Запустив его дважды, один раз для строк {(a, b)} и снова для строк {(-a, -b)}, вы получите полную выпуклую оболочку.

Ответ 3

Если я вижу это правильно, строки всегда вносят вклад в "конверт" в порядке их значения "а". Так что сортируйте их по. Если у вас есть два с одинаковыми a, они параллельны, а b решает, что выше другого (вы можете опустить нижний). Если вы знаете порядок строк, вы можете вычислить точку пересечения для двух передовых линий в O (1). Таким образом, в основном это не что иное, как сортировка, а это O (n log n).

EDIT: Хорошо, один из комментариев прав - нет параллельных строк, которые не распространяются на конверт - причина в том, что они будут способствовать конверту за пределы точки перегиба. Но тот факт, что сегменты огибающей от строк в порядке их "а" остается правильным (и это означает, что у вас всегда есть начальный и конечный сегменты).

Вопрос в том, как вы определяете, какая строка способствует конверту, а какая нет. Вы сканируете один раз над массивом, чтобы найти точку поворота (где должен находиться знак "a" ). Вы начинаете оттуда один раз вниз (уменьшая a) и однажды вверх (увеличивая). Вы вычисляете точку пересечения со следующей строкой - если она на неправильной стороне (не уменьшается/увеличивается) x, пропустите ее. Сканирование, чтобы удалить параллели (с равным а), вы все равно должны применять после сортировки, так как это исключает патологический случай при вычислении точки пересечения.

Ответ 4

Это комментарий к ответу Симонов, который, как я считаю, неверен.

Теперь мы начинаем рассматривать линии lmin, lmax, которые являются линиями с самый маленький и самый большой a; они будут точек, полученных от пересечений со вторым наименьшим и вторая по величине линия, и мы добавляем к этим двум точкам верхнюю конверт.

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

Кроме того, исключая все строки с y = li при x = xi, представляется разумным. Но эти строки НЕ идентифицируются с помощью значения b между b_lmin и b_lmax (если это то, что вы имеете в виду, это немного неясно). Примером встречного примера является:

Надеюсь, я не неправильно понял ваше описание вашего алгоритма. Если у меня есть, пожалуйста, дайте мне знать!

Ответ 5

Я не знаю, как это решить, но обратите внимание, что вы знаете самые левые и самые правые строки (поскольку x стремится к минус и плюс бесконечность), так как они будут иметь наименьшие и наибольшие значения a (as x становится большим ax доминирует над любым значением b).

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

Ответ 6

Вот выходной чувствительный алгоритм:

for t = 0, 1, 2 ... do
     k = 2^(2^t)
     arbitrarily partition the segments into ceiling(n/k) subsets each of size at most k
     run any O(nlogn) time algorithm on each group yielding ceiling(n/k) monotone polygonal chains
     find the upper envelope of these monotone polygonal chains, and abort if the output size exceeds k
end for

время выполнения: O (nlogk), где k = количество сегментов в ответе. Это, по сути, двойственная идея алгоритма выпуклого хана Чан

Ответ 7

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

Проблема, похоже, не разрешима каким-либо прямым аргументом. На самом деле, как оказалось, большинство алгоритмов с делением и поколением достигают времени выполнения O (n log n a (n)), содержащего обратную функцию Аккермана a (n).

Однако есть бумага, обеспечивающая приятное, но не тривиальное решение: http://www.sciencedirect.com/science/article/pii/0020019089901361

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

Ответ 8

Я полагаю, что лучи передаются с (0, + INFINITY) на наш набор линий. Первая точка столкновения лучей является частью нашей оболочки. Если любые три последовательных столкновения не являются колинейными, большее количество лучей отправляется между точками 1 и 2 столкновения, а 2 и 3. Для последовательных столкновений, которые попадают в одну и ту же линию, только один должен быть записан в выходной набор. Затем вы использовали набор столкнутых линий для создания фактической вершины между каждой парой линий.

К сожалению, это дало бы большую оценку огибающей, но не точный ответ ( "так как вам понадобится бесконечно много лучей?" ).

Шаг1) Выделите свой первый залп лучей {0, -Pi/4, -3Pi/4, -Pi}

R | L
1 | Line8
2 | Line2
3 | Line2
4 | Line1

Шаг 2) Литые лучи между последовательными ударами уникальных линий (1 и 2, и 3 и 4). Вставка в результаты и отбраковка внутренних повторов (штрихи строк, которые имеют одну и ту же линию с обеих сторон).

R | L
1 | Line8
5 |  Line8 * culled out
6 |  Line8
7 |  Line5
8 |  Line2
2 | Line2 * culled out
3 | Line2 * culled out
9 |  Line2 * culled out
10|  Line2
11|  Line1
12|  Line1 * culled out
4 | Line1

Шаг 3) Повторите шаг 2 до тех пор, пока не будет достигнута метка точности.

Шаг 4) Создайте свой список точек конверта, выполнив линию, пересекающуюся между всеми последовательными уникальными строками в результатах.