1

以下问题是否有任何算法或相关工作？

给定一组二维线段，如何移动线段（水平或垂直）以消除交叉点，从而最小化整体移动？可以允许端点处的交叉点。

4

1 回答 1

0

如果要最小化段移动的数量：

您可以将线段问题转换为图问题：每个线段是图的一个顶点，如果两个线段彼此相交，则两个顶点之间有一条边。您想找到包含所有边的至少一个端点的最小顶点数（因为如果您移动所有这些线段，将不再有交叉点）。这是顶点覆盖问题，不幸的是 NP 很难，但是存在近似算法。

见：http ://en.wikipedia.org/wiki/Vertex_cover_problem

于 2011-04-08T14:24:32.120 回答