时间戳

首页 > 解决方案 > 凸面船体由最大。n 点

algorithm - 凸面船体由最大。n 点

问题描述

给定一组 2D 点 X，我想找到一个由最大 n 个点组成的凸包。当然，这并不总是可能的。因此，我正在寻找一个由 max 组成的近似凸包。最大程度覆盖点集 X 的 n 个点。

更正式地说，如果 F(H,X) 返回凸包 H 覆盖的 X 点的数量，其中 |H| 是建造船体的点数，然后我寻求以下数量：

H_hat = argmax_H F(H,X), st |H|<=n

考虑这个问题的另一种方法是找到由 max 组成的多边形的任务。集合 X 的 n 个角，使其最大程度地覆盖所述集合 X。

我想出的方法如下：

X = getSet() \\ Get the set of 2D points
H = convexHull(X) \\ Compute the convex hull
while |H| > n do
    n_max = 0
    for h in H:
        H_ = remove(h,H) \\ Remove one point of the convex hull
        n_c = computeCoverage(X,H_) \\ Compute the coverage of the modified convex hull.
        \\ Save which point can be removed such that the coverage is reduced minimally.
        if n_c > n_max:
            n_max = n_c
            h_toremove = h
    \\ Remove the point and recompute the convex hull.
    X = remove(h,X)
    H = convexHull(X)

但是，这是一种非常缓慢的方法。我有很多点，n（约束）很小。这意味着原始凸包包含很多点，因此 while 循环会迭代很长时间。有没有更有效的方法来做到这一点？或者对于近似解决方案还有其他建议吗？

标签： algorithmgeometrypolygoncomputational-geometryconvex-hull

解决方案

几个想法。

  1. 我们在删除顶点时排除的点位于由该顶点和凸包上与其相邻的两个顶点形成的三角形中。删除任何其他顶点不会影响可能排除的点集。因此，我们只需要为每个删除的顶点重新计算覆盖率两次。

  2. 说到重新计算覆盖率，我们不一定要查看每一点。这个想法并没有改善最坏的情况，但我认为它在实践中应该是一个很大的改进。保持点索引如下。选择一个随机顶点作为“根”，并将由根和其他两个顶点形成的三角形包含它们的点分组（O（m log m）时间，使用好的算法）。每当我们删除一个非根顶点时，我们将两个点集合并并过滤出涉及已删除顶点的三角形。每当我们重新计算覆盖率时，我们只能扫描两个相关三角形中的点。如果我们删除了这个根，选择一个新的并重做索引。预计此维护的总成本将为 O(m log^2 m)，其中 m 是点数。但是，很难估计计算覆盖的成本。

  3. 如果点在船体内合理均匀分布，则可以使用面积作为覆盖范围的代理。将顶点存储在一个优先级队列中，该队列由它们的邻居（耳朵）形成的三角形面积排序。每当我们删除一个点时，更新它的两个邻居的耳朵区域。这是一个 O(m log m) 算法。

推荐阅读