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

Question

Отказ от ответственности: Да, это домашнее задание, и я думаю об этом пару дней, но не смог найти способ.

Итак, есть n прямых линий (y = ax + b), и я хочу найти их верхние конверты (жирная часть на рисунке). Это должно быть в O (nlogn).

Я понимаю, что мне нужно найти способ игнорировать некоторые строки, потому что если я буду искать все строки, это не будет O (nlogn).

Я думаю о подходе «разделяй и властвуй», чтобы я мог разделить список на две части и рекурсивно продолжать до решения. Но тогда я не знаю, как избавиться от некоторых строк. Ясно, что мне не нужно рассматривать некоторые нижние строчки на картинке, потому что они не могут внести свой вклад в решение. Но мне ничего не пришло в голову. Любые советы приветствуются.

Answer 1

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

Решение: если вы обрабатываете каждую линию 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 - точка пересечения.

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

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

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

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

Answer 2

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

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

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

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

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

Теперь вернемся к новым деревьям.

Answer 3

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

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

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

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

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

Answer 4

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

РЕДАКТИРОВАТЬ : Хорошо, один из комментариев правильный - нет параллельных линий, которые не распространяются на конверт - причина в том, что они будут способствовать конверту за пределами точки перегиба. Но тот факт, что сегменты огибающей идут от линий в порядке их «а», остается верным (и это означает, что у вас всегда есть начальный и конечный сегменты).

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

Answer 5

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

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

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

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

Answer 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 = количество сегментов в ответе. По сути, это двойственная идея алгоритма выпуклой оболочки Чана

Answer 7

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

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

Step1) Создайте свой первый залп лучей {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) Создайте свой список точек конверта, сделав линию, пересекающую все последовательные уникальные линии в результатах.

Answer 8

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

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