algorithm - 寻找形成凸多边形的最大点子集

Question

我正在寻找一种算法，用于从给定的一组点中找到形成凸多边形的最大点子集(最大的我的意思是数量)。
我认为这可能可以使用 DP 解决，但我不确定。
是否可以在 O(n^3) 中做到这一点？
其实我只需要最大子集的大小，所以它不需要有唯一的解决方案

编辑 :

只是为了保持这个简单，

给定输入:
一组二维点

所需输出:形成凸多边形的最大点数，如示例中的输出为 5(ABHCD 是可能的凸多边形之一)



有一个类似的问题 spoj.com/problems/MPOLY 可以使用 O(N^3) 中的 DP 解决，我的问题是关于不必包含 (0,0) 的问题的泛化

Answer 1

我想我通过扩展 Andrew's algorithm for convex hulls 为它想出了一个算法。 .

最初，我想出了一个 O(N^4) 算法，但注意到它过于复杂并将其归结为 O(N^2) 算法。似乎代码中某处可能存在错误，至少在垂直点线的情况下会导致问题。这可能是一种特殊情况(需要更改几行代码)，或者是算法中存在较大缺陷的迹象。如果是后者，那么我倾向于说它是 NP 难的，并提供该算法作为启发式算法。我花了所有的时间来编码和调试它。在任何情况下，它似乎在其他情况下都可以正常工作。但是，当正确的算法似乎是 O(2^N) 时，很难测试其正确性。

def maximal_convex_hull(points):
    # Expects a list of 2D points in the format (x,y)


    points = sorted(set(points)) # Remove duplicates and sort
    if len(points) <= 1: # End early
        return points

    def cross(o, a, b): # Cross product
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


    # Use a queue to extend Andrew's algorithm in the following ways:
    # 1. Start a new convex hull for each successive point
    # 2. Keep track of the largest convex hull along the way
    Q = []
    size = 0
    maximal_hull = None
    for i,p in enumerate(points):
        remaining = len(points) - i + 1
        new_Q = []
        for lower, upper in Q: # Go through the queue
            # Build upper and lower hull similtanously, slightly less efficent
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                lower.pop()
            lower.append(p)
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) > 0:
                upper.pop()
            upper.append(p)

            new_size = len(lower) + len(upper)
            if new_size > size: # Check for a new highest maximal convex hull
                size = new_size
                maximal_hull = (lower, upper)


        # There is an odd bug? that when one or both if statements are removed
        #  xqg237.tsp (TSPLIB) gives slightly different solutions and is
        #   missing a number of points it should have.
        #  Seems like if the opposite should be true if anything since they
        #   were intended to be easy optimizations not required code.
            if remaining + new_size >= size: # Don't bother if not enough
                new_Q.append((lower, upper)) # Add an updated convex hulls
        if remaining > size: # Don't bother if not enough
            new_Q.append(([p], [p])) # Add a new convex hull
        Q = new_Q # Update to the new queue

    # Extract and merge the lower and upper to a maximium convex hull
    # Only one of the last points is ommited because it is repeated
    #    Asserts and related variables used for testing
    #    Could just have "return lower[:-1] + list(reversed(upper[:-1]))[:-1]"
    lower, upper = maximal_hull
    max_hull_set = set(lower) | set(lower) | set(upper)
    lower = lower
    upper = list(reversed(upper[:-1]))[:-1]
    max_convex_hull = lower + upper
    assert len(lower) + len(upper) == len(max_hull_set)
    assert max_hull_set == set(max_convex_hull)
    return max_convex_hull

编辑:这个算法不正确，但它为正确算法提供了灵感，因此我把它留在这里。