找到形成凸多边形的最大点子集
zeu*_*ulb 15 algorithm polygon convex-hull convex
我正在寻找一种算法,用于寻找从给定点集形成凸多边形的最大点子集(通过最大数量,我的意思是数量).我认为这可能是使用DP解决的,但我不确定.是否可以在O(n ^ 3)中执行此操作？实际上我只需要最大子集的大小,因此它不需要有唯一的解决方案
编辑:
只是为了保持这个简单,
给定输入:2D中的一组点
期望输出:形成凸多边形的最大点数,如示例中输出为5(ABHCD是可能的凸多边形之一)
有一个类似的问题spoj.com/problems/MPOLY可以在O(N ^ 3)中使用DP解决,我的问题是关于该问题的概括,它不必包含(0,0)
这个问题已经在这些竞赛中发布：
- SPOJ 问题 BOYSCOUT
- USACO DEC08 问题“最大的栅栏”（页面上的最后一个问题）
其解决方案（O(N 3 ) 算法）可以在此页面找到：“USACO DEC08 Problem 'fence' Analysis”，作者：Bruce Merry 和 Jacob Steinhardt。
下面尝试解释一下这个算法。这也是我在 C++11 中对该算法的实现。此代码适用于 N<=250 和 0 .. 1023 范围内的整数坐标。任何三个点都不应在同一直线上。这是生成满足这些要求的测试数据的Python 脚本。
简化问题的O(N 2 ) 算法
简化的问题：找到形成凸多边形并包含给定集合的最左边点的点的最大子集（或者如果有多个最左边的点，则该多边形应包含其中的最上面的点）。
为了解决这个问题，我们可以通过有向线段连接每对点，然后（隐式）将每个线段视为一个图节点，如图所示：
这里父节点和相应的段具有蓝色。与其左子线段（红色）对应的线段从“父”线段的末尾开始，并且它是相对于“父”线段的方向最不可能左转的线段。其右子线段（绿色）对应的线段从“父”线段的起点开始，并且它也是相对于“父”线段的方向最不可能左转的线段。
任何以最左边点结束的段都对应于“叶”节点，即它没有子节点。这种图的构造保证了没有循环，换句话说，这个图是一个 DAG。
现在，要找到点的最大凸子集，找到该图中的最长路径就足够了。使用动态规划算法可以在 O(E) 时间内找到 DAG 中的最长路径，其中 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;
}
输入参数是最左边的点和形成当前线段的一对点（其中直接给出线段的起点，但给出终点作为按角度数组排序的索引）。此代码片段中的“左”一词有点过度使用：它表示最左边的点 ( i_left) 和包含图的左子节点的预处理数组 ( lefts[][])。
O(N 3 ) 算法
一般问题（最左边的点不固定）可以这样解决：
- 将点按左右方向排序
- 预处理这些点以获得两个数组：(a) 每个点按相对于彼此点的方向排序，(b) 线段末端的第一个数组中的位置，使相对于“父”线段方向的左转最少。
- 将每个点作为最左边的点，用“简化”算法找到最长的凸多边形。
- 定期修剪预处理数组中“最左边”点左侧的所有点。
- 选取第 3 步中找到的最长路径。
步骤 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% 的速度提升，很可能使用真正的超线程它会快得多。