algorithm - 连接点的最小线数

Question

在二维空间中给出了一组点。所有点的X坐标都是唯一的。

这些点必须由斜率在 -1 到 +1 之间的线连接。现在，如果两条或多条这样的线相互连接，如果整条线没有“掉头”，它将被算作一条线。

连接 (0,0) (1,1) 和 (0,2) 的线在 (1,1) 处“转向”。在这种情况下，连接 (0,0) 和 (1,1) 的线和 (1,1) & (0,2) 是分开的两条线，不能算作一条线。

如何确定此类“整体”线的全局最小数量(或至少近似解决方案)？它是某种已知算法吗？

所有最终数量的“总”线不需要相互接触或相交。

例如，如果我有点 {(1,1)(3,3)(5,5)}，答案是 1

如果我有点 {(1,1)(2,5)(3,3)(4,6)(5,1)} 答案是 2. 连接 (2,5)&(4 ,6)等加入其他点。

谢谢。

编辑:关于“周转”。

“总线”由斜率在-1 和+1 之间的线段组成。每条这样的“总线”必须是这样的，即不存在一条线 x=const 在多个地方切割“总线”。

目标是找到最少数量的这种“总线”。

Answer 1

让我们将给定的一组点视为有向图，其中点是顶点，并且两点之间存在一条边，前提是它们可以与斜率在 -1 和 1 之间的线段相连。为了处理没有转弯的情况，每个边缘都将向上定向(这将限制向下移动，从而限制转弯)。很明显，带有您的条件的一行对应于该图中的一条路径。

所以有了这样的图表，你的问题就变成了一个著名的问题。任务是用最少的方法覆盖一个有向无环图。你可以通过互联网找到很多关于这个主题的资料，例如看看这个:

• Minimum number of days required to solve a list of questions
• http://en.wikipedia.org/wiki/Vertex_cover

编辑:最初我错误地认为转向条件，我正在考虑 y=const 行。实际上，边缘必须朝向右侧 (x1 < x2) 或左侧 (x1 > x2)。