Соедините четное количество узлов без пересечения

У меня есть два набора из n узлов. Теперь я хочу соединить каждый узел из одного набора с другим узлом из другого набора. Полученный граф не должен иметь пересечений.

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

Каждый узел из одного набора может быть соединен с любым другим узлом в другом наборе.

Любые указатели на (эффективный) алгоритм, решающий эту проблему? Нет необходимости в реализации.

EDIT1:

Вот одно из решений проблемы для n=7:

Проблема пересечения

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

EDIT2:

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


algorithm intersection graph-theory line-segment planar-graph
person Soift    schedule 29.06.2016    source источник
comment
Вот пример задачи без решения: Нарисуйте любой отрезок длины 4. Поставьте красную точку на левом (или нижнем) конце и еще одну красную точку на 1 единицу вправо (или вверх) вдоль линии отсюда. Поставьте черную точку на правом (или верхнем) конце и еще одну черную точку на 1 единицу влево (или вниз) от него. т.е. схема выглядит как R R B B. Все возможные пары черно-красных прямых пересекаются на всем отрезке длины 1.   -  person j_random_hacker    schedule 29.06.2016
comment
Думали ли вы об этом как о проблеме оптимизации? под этим я подразумеваю, что вы хотите найти оптимизированный набор ребер и рекурсивно проверяете для каждого возможного ребра правильность набора с краем или без него. Я могу направить вас больше, если вы думаете, что это хорошее направление.   -  person Gal Dreiman    schedule 29.06.2016
comment
Если точки фиксированы, решение не всегда существует. Самый простой встречный пример — представить все узлы на одной линии, черные узлы посередине, а красные — по обеим сторонам.   -  person Ivaylo Strandjev    schedule 29.06.2016
comment
@j_random_hacker Да, бывают случаи, когда это не работает. Я забыл упомянуть, что эти крайние случаи никогда не возникают. Есть ли решение, если предположить, что никогда не будет черно-красных линий, параллельных друг другу?   -  person Soift    schedule 29.06.2016
comment
Я говорю, нарисуйте эти линии случайным образом или с помощью для каждой точки одного набора нарисуйте линию к ближайшей незанятой точке из другого набора, затем, если какие-либо две линии пересекаются, поменяйте местами точки с обеих сторон. Это должно закончиться в конце концов, но я думаю, что следует оптимизировать, чтобы, если одна линия пересекает более одной из других, поменяйте местами конец этой линии с первым.   -  person Vesper    schedule 29.06.2016
comment
@Vesper Вот что я имел в виду под методом грубой силы, однако он кажется крайне неэффективным.   -  person Soift    schedule 29.06.2016

Ответы (1)


arrow_upward
7
arrow_downward

Когда решение существует (см. мой комментарий с примером, где его нет), его можно найти, найдя сопоставление минимального веса в полном двудольном графе, который содержит вершину (красную или черную) для каждой точки и для каждой красной вершины u и черной вершины v ребро (u, v) из веса, равного евклидову расстоянию между их соответствующими точками. Это можно решить оптимально за время O (V ^ 4).

Почему это должно работать? Основная идея, которую я взял из ответа Дэвида Эйзенстата на аналогичный вопрос, заключается в том, что всякий раз, когда у нас есть пара отрезков AB и CD, которые пересекаются в некоторой точке X, можно использовать неравенство треугольника, чтобы показать, что выбор любая конечная точка каждого и их замена дает пару отрезков с меньшей или равной общей длиной:

A
|\
| \
|  \ X
C---+-----D
     \   /
      \ /
       B

AX + XC >= AC (tri. ineq.)
BX + XD >= BD (tri. ineq.)
AX + XC + BX + XD >= AC + BD (sum both sides)
(AX + BX) + (XC + XD) >= AC + BD (rearrange LHS)
   AB     +    CD     >= AC + BD (combine pairs of segments on LHS)

Предполагая далее, что треугольники AXC и BXC невырождены, >= становится >. (Достаточным условием для этого является то, что никакой набор из 3 точек, содержащих по крайней мере 1 красную и 1 черную точку, не лежит на одной прямой.) Итак, для любого заданного решения (сопоставление красных узлов черным узлам), если это решение содержит пересечение, то его общая сумма длин сегментов линии может быть уменьшена на ненулевую величину, если поменять местами красные (или черные) конечные точки двух пересекающихся сегментов линии.

Другими словами,

Solution contains a crossing => sum of segment lengths is not minimal.

Принимая противное, сразу получаем

Sum of segment lengths is minimal => solution contains no crossing.

Поскольку алгоритм сопоставления минимального веса возвращает решение минимально возможного веса, это подтверждает его корректность.

(Обратите внимание, что нет необходимости беспокоиться о том, действительно ли замена конечных точек гарантирует, что новая пара отрезков AC и BD не пересекается — хотя кажется очевидным, что они не будут пересекаться, все, что нам действительно нужно для доказательство правильности состоит в том, чтобы показать, что crossing exists => sum not minimal.)

person j_random_hacker    schedule 29.06.2016
comment
не нужно беспокоиться о том, действительно ли замена конечных точек гарантирует, что новая пара отрезков линии AC и BC не пересекается - AD я полагаю. Но, если бы они пересеклись после смены концов, то замена их СНОВА приведет к AB и CD, сумма длин которых больше суммы AD и BC, чего быть не может. Поэтому они не пересекаются. - person Vesper; 29.06.2016