geometry - 一组带边距的点的最小跨越线

Question

我有一个与几何相关的简单编程问题！我可以用铅笔和纸解决它（在视觉模式下！！），但是我不确定我是否可以编程。我不需要代码本身，而是要实现的伪代码或想法。

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

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

p1: (1,1) p2: (2,1) p3: (5,1) p4: (7,2)

图示：

如图所示，结果是从 1 到 7 的线段，长度为 6。

另一个例子： p1: (2,1) p2: (3,2) p3: (4,1.5) p4: (6.5,0.5)

结果（下面的绿线）是从 2 到 6.5 的线段（长度：4.5）

Answer 1

最优结果的长度总是大于 max(x_i)-min(x_i) i=1,2,3,4

也很容易总是存在一个最优解，它的一个端点与 x_i 匹配，即您可以滚动生成最优结果以匹配一个点，例如 x_1。

从 $-\infty$ 扫到 $+\infty$。开始 x_1 并将其跨越其右边距。另外开始你可以的所有其他点（即他们的左边距已经开始的点）。换句话说，尽可能晚地开始第一个点，在它之后，尽快开始所有其他点。最后，如果有一个点 x_i，它的左边距在 x_1 之前开始，则将此差异称为 diff_i。将所有 diff_i 添加到所有 x_i 中，并找到结果的最终点之外的所有段（即 if (x_i+diff_i>current_end_position then current_end_position=x_i+diff_i.

感谢您的意见。