找到点形成的凸多边形最大子集 [英] Finding largest subset of points forming a convex polygon

问题描述

我在寻找一种算法寻找点（由大我的意思是在数量上），形成从给定的点的凸多边形的最大的子集。 我想用DP，这可能是可以解决的，但我不知道。 是否有可能做到这一点的为O（n ^ 3）？ 其实我只需要最大的子集的大小，所以它并不需要有唯一解

I'm looking for an algorithm for finding largest subset of points (by largest i mean in number) that form a convex polygon from the given set of point. I think this might be solvable using DP but i'm not sure. Is it possible to do this in O(n^3) ? Actually i just need the size of the largest subset, so it doesn't need to have unique solution

编辑：

只是为了让这个简单，

由于输入： 在2D点集

Given input : a set of points in 2D

希望的输出：形成一个凸多边形，像本例中的输出是5个点的最大数量（ABHCD是可能的凸多边形之一）

Desired output : maximum number of points that form a convex polygon, like in the example the output is 5 (ABHCD is one of the possible convex polygon)

有一个类似的问题spoj.com/problems/MPOLY这是可解为O使用DP（N ^ 3），我的问题是关于这个问题的泛化而不必包含（0,0）

There's a similar problem spoj.com/problems/MPOLY which is solvable using DP in O(N^3), my question is about the generalization of that problem which doesn't have to contain (0,0)

推荐答案

此问题已被刊登在这些比赛：

This problem has been already published in these competitions:

• SPOJ问题BOYSCOUT
• USACO DEC08问题，最大的栅栏（最后在页面上的问题）

• SPOJ problem BOYSCOUT
• USACO DEC08 problem "Largest Fence" (last problem on the page)

和其解决方案（O（N ³ ）算法）可以在本页面发现：的USACO DEC08问题'篱笆'分析，由布鲁斯·梅利和雅各布·斯坦哈特的。

And its solution (O(N³) algorithm) could be found on this page: "USACO DEC08 Problem 'fence' Analysis" by Bruce Merry and Jacob Steinhardt.

下面是一个试图解释这一算法。此外这里是这个算法的C ++ 11的我的实现。这code当n＆LT; = 250和范围0整数坐标.. 1023无三点应该是在同一行。这里是 Python脚本生成测试数据满足这些要求。

The following is an attempt to explain this algorithm. Also here is my implementation of this algorithm in C++11. This code works for N<=250 and integer coordinates in range 0 .. 1023. No three points should be on the same line. Here is Python script that generates test data satisfying these requirements.

简化问题：发现形成凸多边形和包含给定组的最左边的点的点最大的子集（或如果有多个最左边的点，此多边形应该含有最顶层它们）

Simplified problem: find largest subset of points that form a convex polygon and contain the leftmost point of given set (or if there are several leftmost points, this polygon should contain topmost of them).

要解决这个问题，我们可以通过向线段连接每对点，然后（隐含）对待每一段为图节点，如图图：

To solve this problem we could connect each pair of points by directed line segment, then (implicitly) treat each segment as a graph node as shown in diagram:

下面父节点和相应的段有蓝色。相应于它的左子（红色）线段开始于母段的结尾，这是该线段使可能左转相对于父段的方向最少。相应于它的右子（绿色）线段开始于母段的开始并且它也是线段使得可能左转弯相对至少到父段的方向。

Here parent node and corresponding segment have blue color. Line segment corresponding to its left child (red color) starts at the end of "parent" segment and it is the line segment making least possible left turn relative to the direction of "parent" segment. Line segment corresponding to its right child (green color) starts at the start of "parent" segment and it is also the line segment making least possible left turn relative to the direction of "parent" segment.

不限于最左边的点结束段对应于一个叶节点，也就是说，它没有子节点。这样的结构的曲线图保证不存在任何周期，换句话说该曲线图是一个DAG

Any segment ending at leftmost point corresponds to a "leaf" node, i.e. it has no child nodes. Such construction of the graph guarantees that there are no cycles, in other words this graph is a DAG.

现在找到点最大凸子集就足够了发现在这个图中的最长路径。而在DAG最长的路径可以有动态规划算法的时间为O（E），其中E是图中的边数被发现。由于每个节点只有2出边，每一个对应于一对点，这个问题可能会在O解决（N ² ）时间

Now to find largest convex subset of points it is enough to find the longest path in this graph. And the longest path in DAG could be found with dynamic programming algorithm in time O(E), where E is number of edges in the graph. Since each node has only 2 outgoing edges, each corresponding to a pair of points, this problem could be solved in O(N²) time.

这一切是可以实现的话，我们preprocess输入数据，整理开始在相同的点由角度定向线段。这允许在图中执行深度优先遍历。我们应该记住每个处理节点开始的最长路径，让每一个图形边缘在访问最多一次，我们有O（E）= O（N ² ）时间的算法（忽略preprocessing时间了）。空间要求也O（N ² ），因为我们需要存储排序方向为每对点和记忆使用每个节点一个值（这也是一个对点）。

All this is possible to implement if we preprocess input data, sorting directed line segments starting at the same point by angle. This allows to perform depth-first traversal in the graph. We should memorize the longest path starting from each processed node, so that each graph edge is visited at most once, and we have O(E) = O(N²) time algorithm (ignoring preprocessing time for now). Space requirements are also O(N²) because we need to store sorted directions for each pair of points and memorization uses one value per node (which is also a pair of points).

下面是C ++实现这个动态规划算法：

Here is C++ implementation of this dynamic programming algorithm:

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;
}

输入参数是最左边的点和一对成形当前线段的点（其中，该段的起点被直接给予，但结束点给定为在排序由点角度阵列的索引）。在这code片段左字稍有过度使用：它意味着两个最左边的点（ i_left ），并包含离开孩子的为图preprocessed阵列（左派[] [] ）。

Input parameters are the leftmost point and a pair of points forming current line segment (where starting point of the segment is given directly but ending point is given as an index in sorted by angle array of points). The word "left" in this code fragment is slightly overused: it means both the leftmost point (i_left) and preprocessed array containing left childs for the graph (lefts[][]).

（其中，最左边的点是不固定的）一般问题可以解决这样：

General problem (where the leftmost point is not fixed) could be solved this way:

1. 排序在左右方向点
2. preprocess点以获得两个数组：（一）左转相对最小可能每个点依相对方向相互点和（b）的位置在线段的端部的第一阵列制作的方向父段。
3. 使用的每个点作为最左边的点，找到最长的凸多边形与简化的算法。
4. 在定期修剪所有点从preprocessed阵列的最左边的点的左侧。
5. 时间最长的第3步中找到的路径。

步骤4是可选的。它并不能改善O（N ³ ）的时间复杂度。但稍微排除不需要的点提高了DP算法的速度。在我的测试中，这给了33％的速度提升。

Step 4 is optional. It does not improve O(N³) time complexity. But it slightly improves speed of DP algorithm by excluding unneeded points. In my tests this gives 33% speed boost.

有用于preprocessing几种选择。我们可以计算出每一个角度（与 ATAN2 ），并对其进行排序，因为它是在样品code由布鲁斯·梅利和雅各布·斯坦哈特完成。这是一种最简单的方式，但 ATAN2 可能是过于昂贵，特别是对于较小的点集。

There are several alternatives for preprocessing. We could compute every angle (with atan2) and sort them, as it is done in sample code by Bruce Merry and Jacob Steinhardt. This is a simplest way but atan2 may be too expensive, especially for smaller point sets.

或者我们可以排除 ATAN2 和排序切线，而不是角度，因为它是在我的执行完成。这是一个比较复杂一点，但速度更快。

Or we could exclude atan2 and sort tangents instead of angles, as it is done in my implementation. This is a little bit more complicated but faster.

这两个方案需要O（N ² 日志N）的时间（除非我们使用一些分布排序）。第三种方法是采用众所周知的计算几何方法（安排和对偶），以获得O（N ² ）preprocessing。但我不认为这是对我们的问题非常有用：它可能是更小的点集，因为大常数因子太慢，对于较大的点集，可能会给一些速度改善，但太微不足道，因为第3步将大大超过步骤2.还它更难以实施。

Both these alternatives need O(N² log N) time (unless we use some distribution sorting). Third alternative is to use well known computational geometry methods (arrangements and duality) to get O(N²) preprocessing. But I don't think it is useful for our problem: it is probably too slow for smaller point sets because of large constant factor, as for larger point sets, it might give some speed improvement, but too insignificant because step 3 will greatly outweigh step 2. Also it is much more difficult to implement.

一些其他的结果：我试图执行，而不是递归迭代DP;这并没有显着改变的速度。我也试图执行两个DP搜索一次，交织步骤每次搜索（类似于在软件中实现纤维或超线程东西）的;这可能帮助，因为DP包括主要的内存访问具有高延迟和preventing CPU吞吐量的充分利用;结果都不是很IM pressive，只有约11％的速度提升，最有可能与真实的超线程那就快多了。

Some other results: I tried to implement iterative DP instead of recursion; this did not noticeably change the speed. Also I tried to perform two DP searches at once, interleaving steps of each search (something similar to fibers or HyperThreading implemented in software); this might help because DP consists mostly of memory accesses having high latency and preventing full utilization of CPU throughput; the results are not very impressive, only about 11% speed boost, most likely with real HyperThreading it would be much faster.

这篇关于找到点形成的凸多边形最大子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！