我正在寻找一种算法来查找从给定点集形成凸多边形的最大点子集（我的意思是数量上最大的）。我认为这可能可以使用 DP 解决，但我不确定。是否可以在 O(n^3) 中做到这一点？其实我只需要最大子集的大小，所以它不需要有唯一的解决方案
编辑 ：
只是为了保持简单，
给定输入：二维中的一组点
期望输出：形成凸多边形的最大点数，如示例中的输出为 5（ABHCD 是可能的凸多边形之一）
有一个类似的问题 spoj.com/problems/MPOLY 可以使用 O(N^3) 中的 DP 解决，我的问题是关于该问题的概括，它不必包含 (0,0)
我想我想出了一个算法，通过扩展安德鲁的凸包算法。
最初，我想出了一个 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 ) 算法）可以在此页面上找到： Bruce Merry 和 Jacob Steinhardt的“USACO DEC08 问题'围栏'分析”。
下面尝试解释这个算法。这也是我在 C++11 中对该算法的实现。此代码适用于 N<=250 和 0 .. 1023 范围内的整数坐标。没有三个点应该在同一条线上。这是生成满足这些要求的测试数据的Python 脚本。
简化问题：找到形成凸多边形并包含给定集合的最左边点的最大点子集（或者如果有几个最左边的点，则该多边形应该包含其中的最上面的点）。
为了解决这个问题，我们可以通过有向线段连接每对点，然后（隐式）将每个线段视为一个图形节点，如图所示：
这里父节点和相应的段有蓝色。与其左子（红色）对应的线段从“父”线段的末端开始，它是相对于“父”线段方向左转最少的线段。与其右孩子（绿色）对应的线段从“父”线段的起点开始，也是相对于“父”线段方向左转最少的线段。
在最左边点结束的任何段对应于“叶”节点，即它没有子节点。图的这种构造保证了没有循环，换句话说，这个图是一个 DAG。
现在要找到点的最大凸子集，只需在该图中找到最长的路径即可。DAG 中最长的路径可以通过动态规划算法在 O(E) 时间内找到，其中 E 是图中的边数。由于每个节点只有 2 条出边，每条对应一对点，这个问题可以在 O(N 2 ) 时间内解决。
如果我们预处理输入数据，所有这些都可以实现，从同一点开始按角度对有向线段进行排序。这允许在图中执行深度优先遍历。我们应该记住从每个处理过的节点开始的最长路径，以便每个图边最多被访问一次，并且我们有 O(E) = O(N 2 ) 时间算法（暂时忽略预处理时间）。空间要求也是 O(N 2 )，因为我们需要存储每对点的排序方向，并且每个节点使用一个值（这也是一对点）。
这是此动态编程算法的 C++ 实现：
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;
}
输入参数是最左边的点和形成当前线段的一对点（其中线段的起点直接给出，而终点作为按角度数组排序的索引给出）。此代码片段中的“left”一词被稍微过度使用：它表示最左边的点 ( i_left) 和包含图 ( ) 的左孩子的预处理数组lefts[][]。
一般问题（最左边的点不固定）可以这样解决：
第 4 步是可选的。它不会提高 O(N 3 ) 时间复杂度。但它通过排除不需要的点略微提高了 DP 算法的速度。在我的测试中，这提供了 33% 的速度提升。
预处理有几种选择。我们可以计算每个角度（用atan2）并对它们进行排序，就像 Bruce Merry 和 Jacob Steinhardt 在示例代码中所做的那样。这是一种最简单的方法，但atan2可能过于昂贵，尤其是对于较小的点集。
或者我们可以排除atan2和排序切线而不是角度，就像在我的实现中所做的那样。这有点复杂但速度更快。
这两种选择都需要 O(N 2 log N) 时间（除非我们使用一些分布排序）。第三种选择是使用众所周知的计算几何方法（排列和对偶）来获得 O(N 2 ) 预处理。但我认为它对我们的问题没有用：由于常数因子大，对于较小的点集可能太慢了，对于较大的点集，它可能会提高一些速度，但太微不足道了，因为第 3 步将大大超过第 2 步。而且实施起来要困难得多。
其他一些结果：我尝试实现迭代 DP 而不是递归；这并没有明显改变速度。此外，我尝试一次执行两个 DP 搜索，将每个搜索的步骤交错（类似于在软件中实现的光纤或超线程）；这可能会有所帮助，因为 DP 主要由具有高延迟和阻止 CPU 吞吐量的充分利用的内存访问组成；结果不是很令人印象深刻，只有大约 11% 的速度提升，很可能使用真正的超线程它会快得多。
这是我的动态编程 O(N^4) 算法，其想法来自 Nucleman 发布的 Andrew's Algorithm，我仍在寻找 O(N^3) 算法
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的 jan 示例。我还写了一个 php 类 concave-hull@phpclasses.org。