algorithm - 选择几何最接近原始点的子集

Question

我有 list n (n < 500)代表高程剖面的正整数。我最多需要选择 m (m < 255)他们的要点使新几何体尽可能与原始几何体相似。输入[10, 21, 15, 2, 8, 35, 94, 223, 370, 575, 701, 661, 592, 356] and m = 8我要回[10, 0, 0, 0, 8, 0, 94, 0, 370, 575, 701, 0, 592, 356] ( 0 意味着我们跳过那个数字)。因为当我们用线连接点时，我们有几何图形 [10.0, 9.5, 9.0, 8.5, 8.0, 51.0, 94.0, 232.0, 370.0, 575.0, 701.0, 646.5, 592.0, 356.0] ，点的错误是 [0.0, 11.5, 6.0, 6.5, 0.0, 16.0, 0.0, 9.0, 0.0, 0.0, 0.0, 14.5, 0.0, 0.0]所以最大错误是16

我尝试了动态规划方法，其中 dp[i][j]是不早于 i 开始的数组的解决方案位置和使用不超过j元素。为每个 k 计算它来自 i至 n如果 k，我计算最大误差是第一个元素并取其最大值和dp[k + 1][j - 1] .

我们可以花钱吗O(1)每个 k 的时间计算点的最大距离 [i .. k - 1]到线路连接点i - 1和 k ？有谁知道如何解决 O(n^2) 中的整个问题吗？ ？

Answer 1

O(n^2 log n) 对于最大误差目标是可行的。在高层次上，我们计算每个 O(n^2) 线段的最大误差，对这些值进行排序，然后在可能的误差限制上使用二分搜索，并在点的有向无环图中使用广度优先搜索可以按照给定误差限度的其他点来确定最小最大误差。这三个步骤中的每一个都需要 O(n^2 log n) 时间。空间使用量为O(n^2)。

为了确定每个线段的最大误差，我们对每个 O(n) 点作为左端点重复以下 O(n log n) 过程一次。维护到目前为止扫描的点的上下船体(使用 Andrew 的 Graham scan 变体)，按顺序扫描每个可能的右端点。在上(分别，下)船体上使用二进制搜索来找到其前面线段的斜率大于(分别小于)或等于连接当前正在考虑的端点的线并且其后续线段的斜率小于的点(分别大于)那个。该点位于线段上方(分别为线段下方)最远的位置。