Как переместить отрезки, чтобы устранить пересечения с минимальными движениями?

Question

Существует ли какой-либо алгоритм или связанная работа для следующей задачи?

Учитывая набор отрезков в 2D, как перемещать отрезки (по горизонтали или по вертикали), чтобы устранить пересечения, чтобы минимизировать общие перемещения?Пересечения в конечных точках могут быть разрешены.

Answer 1

Если вы хотите минимизировать количество движений сегмента:

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

см .: http://en.wikipedia.org/wiki/Vertex_cover_problem