一组具有边距的点的最小生成线

我有一个与几何有关的简单编程问题！我可以用铅笔和纸（在视觉模式!!）解决它，但是我不知道我是否可以编程。我不需要代码本身，而是需要一个伪代码或一个想法来实现。一组具有边距的点的最小生成线

这是在一个线的4个点，谁给的位置。每个点都需要在自己周围留出最小空间，这是在点的位置之后给出的。我们希望找到能够满足上述所有要求的最小（长度）线段。换句话说，我需要在这些点上的最小生成线，并且要求的空间最小。

例如： $ p_i $：（x，L），其中x表示位置（实数），L表示x周围的最小空间要求。

P1：（1,1） P2：（2,1） P3：（5,1） P4：（7,2）

图形表示： The graphical representation

，因为它被示出的结果是从1线段至7与长度为6

又如： P1：（2,1） P2：（3,2） P3：（4,1.5） P4：（6.5,0.5）

的结果（下面的绿线）是线段的2至6.5（长度：4.5） Another example

来源

2012-09-08 remo

这看起来像一个CPU的调度问题...你想排队p1-p4在一条线？顺便说一句，作为一个简单的解决方案，添加所有线的长度比你有完整的线...不知道这是否有帮助 – rekire

Erm ...如果我们将一个点定义为'（x，y）'对，其中'x'是位置，'y'是范围，您可以给出一个结果行不是（min x ，max x）？ – raina77ow

当然可以，但我认为当所有的点和跨度都足够小时，始终有一个起点（或终点） t），即结果的开始点或结束点与其他点中的一点相同！但是如果其中一个跨度很大，情况并非总是如此。仅测试两个方向的起点是否属实？ – remo

最佳结果的长度总是比最大（X_I）-min（X_I）我更= 1,2,3,4

总是有一个最佳解决方案，其中一个端点与x_i相匹配也很容易，也就是说，您可以滚动跨越最优结果以与点匹配，例如x_1。

从$ - \ infty $扫到$ + \ infty $。启动x_1并跨越其右边距。另外还可以启动所有其他积分（即指出它们的左边距已经启动）。换句话说，尽可能晚地开始第一点，然后尽快开始所有其他点。最后，如果有一个点x_i，其左边界已在x_1之前开始，则将此差值称为diff_i。所有diff_i添加到所有X_I S和发现所有细分出来的结果的最后时刻（即，如果（X_I + diff_i> current_end_position然后current_end_position = X_I + diff_i。

感谢您的意见。

来源

2012-09-09 11:27:55 remo

一组具有边距的点的最小生成线

回答

相关问题