Есть ли какой-либо алгоритм или связанная работа для следующей проблемы?
Учитывая набор линейных сегментов в 2D, как перемещать линейные сегменты (по горизонтали или вертикали), чтобы исключить пересечения и свести к минимуму общие перемещения? Пересечения в конечных точках могут быть разрешены.
Если вы хотите минимизировать количество движений сегмента:
Вы можете преобразовать задачу об отрезке линии в задачу о графе: каждый отрезок является вершиной графа, и между двумя вершинами существует ребро, если два отрезка пересекаются. Вы хотите найти минимальное количество вершин, содержащих хотя бы одну конечную точку всех ребер (потому что, если вы переместите все эти сегменты, пересечений больше не будет). Это проблема вершинного покрытия, которая, к сожалению, является NP-сложной, но существуют алгоритмы аппроксимации.
см.: http://en.wikipedia.org/wiki/Vertex_cover_problem
