选择几何形状与原始形状最接近的点子集

Question

选择几何形状与原始形状最接近的点子集

3

我有一个列表n (n < 500)，其中包含表示海拔高度的正整数。我需要选择其中最多m (m < 255)个点，以使新几何形状与原始几何形状尽可能相似。对于输入[10, 21, 15, 2, 8, 35, 94, 223, 370, 575, 701, 661, 592, 356] 和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-1和k的线的最大距离吗？有人有想法如何在O(n^2)中解决整个问题吗？

- stawny

2

假设第一个和最后一个点总是被选中，以便能够在整个范围内进行插值？或者您可以将它们留出来，并从最接近的值进行外推？ - jdehesa

这里的 'm' 是什么？你是说当 m = 8 时，我想要返回长度大于8的 [10, 0, 0....]。 - SomeDude

1

@Alerra，你说得对，我忘了提到并选择了错误的例子，因为这些数字保证是正数。 - stawny

你想从输入中选择锚点吗？还是可以选择任意的锚点来减少误差？你想要像你问题中那样的绝对差错吗？还是平方距离也可以（甚至更合适）？ - Nico Schertler

1

如果“足够接近”而不是最接近的话，您可以尝试使用https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm。 - dmuir

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

最大误差目标的时间复杂度为 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 变体），按顺序扫描每个可能的右端点。在上（或下）凸壳上使用二分搜索，找到前面的线段斜率大于（或小于等于）当前考虑的端点相连线段的点，并且后面的线段斜率小于（或大于）该点。这个点是离线段最远的点。