我正在寻找一种算法，用于从给定点集中找到形成凸多边形的最大点集（所谓最大是指点数最多）。
我认为可以使用DP来解决这个问题，但我不确定。
能否在O(n^3)的时间复杂度内完成呢？
实际上，我只需要知道最大子集的大小，因此它不需要具有唯一的解决方案。
编辑：
为了简化问题，假设输入为一个二维平面上的点集。
期望输出：能够形成凸多边形的最大点数。例如，对于给定的数据，输出为5（ABHCD是可能的凸多边形之一）。
这里有一个类似的问题 spoj.com/problems/MPOLY，可以使用DP在O(N^3)的时间复杂度内解决，我的问题是关于该问题的推广，即不一定包含（0,0）点。
我想通过扩展Andrew的凸包算法为它设计了一个算法。
起初，我提出了一个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
编辑：这个算法并不正确，但它启发了正确算法的诞生，因此我将其保留在这里。
它的解决方案（O（N 3 ）算法）可以在这个页面上找到：“USACO DEC08问题'fence'分析”由Bruce Merry和Jacob Steinhardt。
以下是尝试解释此算法。此外，这里是我在C ++ 11中实现的代码。此代码适用于N＆lt; = 250和范围为0 .. 1023的整数坐标。不应有三个点在同一条线上。这里是Python脚本，可生成满足这些要求的测试数据。
简化问题：查找包含给定集合的最左侧点（或如果有多个最左侧点，则此多边形应包含其中最高的点）的最大点子集。
要解决这个问题，我们可以通过有向线段连接每对点，然后（隐式地）将每个线段视为图节点，如下图所示：
这里父节点和相应的线段具有蓝色。其左子节点（红色）对应的线段从“父”线段的末端开始，它是相对于“父”线段方向做最小可能左转的线段。其右子节点（绿色）对应的线段从“父”线段的起点开始，它也是相对于“父”线段方向做最小可能左转的线段。
以左侧最点结束的任何线段都对应于“叶”节点，即它没有子节点。这种图的构建保证没有循环，换句话说，这个图是一个DAG。
现在要找到最大的凸点子集，只需要在此图中找到最长路径即可。 DAG中的最长路径可以在O（E）的时间内使用动态编程算法找到，其中E是图中的边数。由于每个节点仅具有2个出站边，每个对应于一对点，因此可以在O（N 2 ）时间内解决此问题。
如果我们预处理输入数据，将以相同点为起点的有向线段按角度排序，则可以实现这一点。这样可以在图中执行深度优先遍历。我们应该记住从每个处理节点开始的最长路径，以便每个图边最多被访问一次，并且我们有O(E) = O(N^2)时间复杂度算法（暂时忽略预处理时间）。空间要求也是O(N^2)，因为我们需要为每对点存储排序的方向，并且记忆化使用每个节点一个值（这也是一对点）。unsigned dpStep(ind_t i_left, ind_t from, ind_t to_ind)
{
ind_t child = sorted[from][to_ind];
while (child < i_left)
child = sorted[from][++to_ind];
if (child == i_left)
return 1;
if (auto v = memorize[from][child])
return v;
const auto x = max(dpStep(i_left, child, lefts[from][child]) + 1,
dpStep(i_left, from, static_cast<ind_t>(to_ind + 1)));
memorize[from][child] = static_cast<ind_t>(x);
return x;
}
i_left），也表示包含图形左侧子节点的预处理数组（lefts[][]）。
通用问题（最左边的点不固定）可以通过以下方式解决：
第4步是可选的。它不会改善O(N3)时间复杂度。但是它通过排除不需要的点略微提高了DP算法的速度。在我的测试中，这可以提高33%的速度。
有几种预处理的替代方法。我们可以计算每个角度（使用atan2）并对它们进行排序，就像Bruce Merry和Jacob Steinhardt在示例代码中所做的那样。这是一种最简单的方法，但是atan2可能太昂贵了，特别是对于较小的点集。
或者，我们可以排除atan2，并对切线而不是角度进行排序，就像我实现的那样。这有点更复杂，但更快。
这两种替代方法都需要O(N2 log N)时间（除非使用某些分布排序）。第三种替代方法是使用众所周知的计算几何方法（排列和对偶性）进行O(N2)预处理。但我认为它对我们的问题没有用处：对于较小的点集，由于大的常数因子，它可能太慢了，因为对于较大的点集，步骤3将大大超过步骤2。而且它要更难实现。
其他一些结果：我尝试实现迭代DP而不是递归；这并没有明显改变速度。我还尝试同时执行两个DP搜索，交错每个搜索的步骤（类似于纤程或在软件中实现的超线程）；这可能有所帮助，因为DP主要由具有高延迟的内存访问组成，阻止了CPU吞吐量的充分利用；结果并不是非常令人印象深刻，只有约11%的速度提升，最可能使用真正的超线程会快得多。
upper_hull(most left point, previous point, current point)
{
ret = 0
if (current point != most left point) /* at anytime we can decide to end the upper hull and build lower_hull from current point ending at most left point */
ret = min(ret,lower_hull(most left point, -1, current point))
for all point on the right of current point /* here we try all possible next point that still satisfy the condition of convex polygon */
if (cross(previous point,current point,next point) >= 0) max(ret,1+upper_hull(most left point, current point, next point))
return ret;
}
lower_hull(most left point, previous point, current point)
{
if (current point == most left point) return 0;
ret = -INF /* it might be impossible to build a convex hull here, so if it does it will return -infinity */
for all point on the left of current point and not on the left of most left point
if (cross(previous point,current point,next point) >= 0) max(ret,1+lower_hull(most left point, current point, next point))
return ret;
}
首先根据x轴对点进行排序，然后在平局的情况下按y轴排序，然后尝试将所有点作为最左边的点运行upper_hull(p,-1,p)，请告诉我此算法是否有任何缺陷。
您可以使用Delaunay三角剖分并删除最长的边和顶点。我使用类似的算法来查找凸包。您可以在人口数据基础上找到一个示例，链接为http://www.phpdevpad.de/geofence。我还编写了一个名为concave-hull的php类，可在phpclasses.org上找到。