logo标签列表

查找凸多边形的最大y坐标

algorithmgeometrymaxconvexconvex-polygon
5
我有一个数组V[1,2,....,n]，其中数组的每个元素表示凸多边形的一个顶点，以坐标对(x,y)的形式表示。
已知V[1]是具有最小x坐标的顶点，并且顶点V[1,2,....,n]按逆时针顺序排序，如图所示。还知道顶点的x坐标都不同，y坐标也都不同。 enter image description here 现在，我想找到具有最大y坐标值的顶点。我们都知道朴素的O(n)方法，但是否可能用O(log(n))的时间找到它？
我利用了V[1]是具有最小x坐标的顶点的信息，在O(log(n))的时间内找到了具有最大x坐标的顶点。但是否可能对于最大的y坐标做到这一点呢？
感谢您的帮助！
你能在V[1]和x坐标最大的顶点之间运行一个三分搜索吗？ - Peter de Rivaz
@PeterdeRivaz 我对三分搜索一无所知。它能行吗？ - Ank
我认为是这样，但我可能没有正确理解问题。我假设您已经使用三分搜索来查找最大的x坐标，因此您应该熟悉这种技术。您用什么方法找到最大的x？也许它也可以帮助找到最大的y？ - Peter de Rivaz
@PeterdeRivaz 我计算了中间两个元素之间的差异，以确定方向，并沿着增加的方向移动，在每次迭代中将数组大小减半。 - Ank
看起来你找到了比三元运算符更好的方法，我已经回答了一个链接，将你的方法推广到任意方向。 - Peter de Rivaz
4个回答
2

长版

二分查找被认为是在一些地方的解决方案，但它只适用于某些情况。

顶点的分布可以以许多不同的方式变化。您可以有许多聚集在一个点附近，另一个孤立地存在，您可以有形成抛物线形状的顶点（以您的图表为例，删除顶点 7、8 和 9），您可以具有类似对数的分布（例如仅顶点 1、2、3 和 4），或者真正的其他数量的可能性。在所有这些不同的情况中，您将拥有不同数量和位移的局部最大值和最小值。

很有可能您需要组合方法来估计分布，然后应用适合类型分布的策略。

让我们尝试描述这样的策略：

首先，请记住您有一个这样的顶点数组，以严格顺序列出，以逆时针旋转。这很重要，并且是随后所有假设和推理的基础。

观察 V[n] 的行为。如果V[n]具有 y 坐标V[n].y小于 V[1] 的 y 坐标，或者 V[n].y < V[1].y，您可以得出结论，所有其他顶点V[2，n-1]的 y 坐标也必须低于V[1]（考虑为什么这必须是这种情况）。因此，V[1]具有最大的 y 坐标。

现在，剩下的分析需要我们改变多边形的概念模型，以简化其表示及要解决的问题。而不是绘制点 (V[i].x, V[i].y) 以获得多边形的形状，相反绘制 (i, V[i].y) 以代表一种想象的连续函数 f(i) = V[i].y。现在我们问题的解决方案是找到函数f(i) = V[i].y 的全局最大值的解决方案。

考虑到这一点，对于所有其他情况，其中V[n].y > V[1].y，我们必须执行二分查找，但我们有两种可能的情况：

  1. V[2]的 y 坐标小于 V[1]。
  2. V[2]的 y 坐标大于 V[1]。

这很重要，因为情况 1 告诉我们V[1]不是局部最小值，而情况 2 告诉我们V[1]是局部最小值（再次考虑为什么这必须是这种情况）。

案例2是一个简单的案例，因为V [1]是一个局部最小值。这意味着只能在V [n]处有一个附加的局部最小值，或者根本没有其他局部最小值。因此，我们可以执行二进制搜索或类似二进制的搜索，以便逐渐收敛于曲线上唯一的局部最大值。
您的图表是案例1的示例，这是更难的情况。 V [1]不是局部最小值，而是局部最大值。更重要的是，您有两个可能的局部最大值，它们位于V [1]和V [n-k]处，其中n-k> 1。为了帮助可视化，如果绘制函数f（i）= V [i] .y的点，您将看到抛物线形状或正弦形状。因此，第二个局部最大值在V [n-k]处将是抛物线的最右端，或正弦曲线的峰值。
（注意：此段是可选的优化步骤。）让我们考虑如何确定我们正在处理哪种类型的局部最大值：如果V [n]具有比V [n-1]更大的y坐标，则V [n]必须是第二个局部最大值（再次考虑为什么这必须是真的），实际上，我们可以立即确定V [n]具有最大的y坐标。否则，存在一些k使得V [n-k]是我们的局部最大值，这意味着我们需要执行搜索。
现在只剩下如何进行搜索的考虑，以避免无意中收敛于V [1]（我们需要找到一个局部最大值，因为V [1]是一个局部最大值，我们可能会意外地收敛它）。
执行具有以下约束条件的二进制搜索：
  • 对于给定的V [i]，如果V [i] .y < V [1] .y，则向V [n]收敛。
  • 如果V [i] .y > V [1] .y，则朝着增加y的方向收敛（只需比较V [i-1]和V [i + 1]与V [i]即可）。
这应该使您安全地收敛于最右侧的局部最大值，并在log（n）时间内隔离该值。
现在，我们已经涵盖了V [1] .y <V [n] .y的两种不同情况，让我们注意到这个约束二进制搜索在案例2中的效果与在案例1中一样准确。因此，我们可以通过遵循受限制的二进制搜索的规则来概括对案例1和案例2的搜索。这显着降低了算法复杂度。
总的来说，您应该能够在任何一般情况下实现O(log n)的时间复杂度，同时处理几个O(1)的边缘情况。
总结：
这个问题的诀窍在于将多边形的概念分解，绘制点(i, V[i].y)而不是(V[i].x, V[i].y)，并将这些点想象为连续函数上的点。然后，这个问题的解决方案就变成了解决“f(i)=V[i].y的全局最大值是什么？”这个问题。由于凸多边形的属性和顶点的排序方式，我们可以确定V[1]肯定是一个局部极大值。考虑到这一点，要么V[1]是全局最大值，要么它不是，这是我们可以在一开始就以恒定的时间确定的。如果它不是全局最大值，那么我们可以执行受限二进制搜索，防止我们收敛于V[1]，从而允许我们在对数时间内确定全局最大值。如果我们感觉特别复杂，我们还可以确定V[n]是否为全局最大值，作为额外的优化步骤，在恒定时间内完成。
简短版本：
当V[1].y>V[n].y时，最大值是V[1].y。只有在V[1].y
基本情况：如果V[1].y>V[i].y，则向V[n]的方向收敛。
标准情况：如果V[i].y
还有一个可选的优化，适用于V[1].yV[n-1].y的边缘情况。这个优化可以安全地跳过，并且可以使解决方案的概念化和实现更简单。
相应算法的伪代码如下：
带优化的解决方案：
如果V[1].y>V[n].y，则V[1].y是最大值。
如果V[1].y < V[n].y并且V[n].y > V[n-1].y，那么V[n].y是最大值。
如果V[1].y < V[n].y并且V[n].y < V[n-1].y，则执行约束二分查找。
此策略有两个O(1)边缘情况和一个标准的O(log n)情况。 无优化解决方案 如果V[1].y > V[n].y，那么V[1].y是最大值。
如果V[1].y < V[n].y，则执行约束二分查找。
此策略有一个O(1)边缘情况和一个标准的O(log n)情况。
在第二种情况下，为什么V [1]和V [2]都可以是局部最小值？ - Ank
@Ank 很好的问题！当我写下这个答案时，我有点误解了。我的推理是，在特殊情况下，即 V[1].y < V[2].y 的情况下，对于任何 i > 2，我们必须有 V[i].y > V[2].y。如果相反，我们有 V[i].y < V[2].y，那么多边形就不能是凸多边形。但是，在我的概念模型中，它们不会同时成为局部最小值。我将修正我的答案以反映这一点。 - B. Fleming
"Minima" 是 "minimum" 的复数形式。一个点可以是局部或全局的 "minimum"。它不能同时是同一函数的两个或更多的 "minima"。只是说一下。 - n. m.
1
@zaira，我很难理解如果问题描述中的约束条件——即V [1]始终是最左边的顶点，并且顶点严格按逆时针顺序放置——防止在将V [1]放置在原点时发生V [2]可能位于第二象限的情况。在问题的约束条件下，这是不可能的。 - B. Fleming
1
@zaira 不用担心！像这样忽略一些小细节很容易，你花时间提出可能的错误是很好的。我发布这个答案已经过去几年了，所以回顾一下以确保准确性是一个不错的练习 :) - B. Fleming
显示剩余3条评论
1
你可以使用二分搜索来找到任何方向上的极点，如此处所述。
基本思想是检查端点和中点处的向量，并使用它来确定要扩展的部分。
我不理解链接中给出的描述。它是如何工作的？他们选择了一个在a和b之间的顶点c，并“假设”V [a，c]和V [c，b]都是单调的。但这怎么能保证呢？V [a，c]或V [c，b]中都可能出现局部最大值。 - Ank
1
因为多边形是凸的，所以相邻点之间的向量角度从 270 度（向下，记作 -90 度）单调递增，通过 0 度（向右），90 度（向上），180 度（向左）等，当您从一个点移动到下一个点时。
因此，您可以进行二进制搜索，以查找大于 180 度的最小角度。向下或向左转变为向下的多边形的位置是下一个点的向量大于 180 度的位置（在您的示例中为 V[8]），该点必须具有最大的 Y 坐标。
我认为 Peter 链接的文章也说了同样的事情，但这对于如此简单的想法来说是很多的文字。
这是一个不错的方法，但如果我将V[5]和V[1]连接起来，那么就没有这样的角度了。 - Ank
0

让V[m]为具有最大y坐标的顶点。

最简单的情况是考虑，当V[2].y < V[1].y > v[n].y时。由于排除了这种情况，后续的推理会更简单，我们将假设已经对此进行了初步检查。

考虑一条以起点V[i]为原点的边E[i]，其中1。给定所有x和y坐标都不同的约束条件，E[i]必须位于以下4个平面象限之一：

enter image description here

鉴于我们已经排除了 m=i=1 的情况，对于 E[i] 位于第一、二或四象限的情况，必须满足 m>i。如果 E[i] 位于第三象限，则有 m=i，当且仅当 V[i].y > V[i-1].y 为真，或者 m<i。

我们可以将此推理用作二分搜索的基础，在每次迭代中执行以下操作：

if E[i] lies in Quadrant III
   if V[i].y > V[i-1].y then m=i
   else consider left half
else
   consider right half

这里有一些Java代码来说明：

static Point maxY(Point[] v)
{       
    // check for max at origin
    if(v[1].y < v[0].y && v[v.length-1].y < v[0].y)
    {
        return v[0];
    }

    int left = 0; 
    int right = v.length-1;     
    Point maxY = null;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(v[(mid+1)%v.length].y < v[mid].y && v[(mid+1)%v.length].x < v[mid].x)
        {
            // Quadrant III
            if(v[mid].y > v[mid-1].y) 
            {
                maxY = v[mid];
                break;
            }
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
    }
    return maxY;
}

还有一些简单的测试用例：

public static void main(String[] args)
{
    Point[][] tests = {
            {new Point(0, 10), new Point(10, 0), new Point(9, 5)},
            {new Point(0, 0), new Point(9, 5), new Point(10, 10)},
            {new Point(0, 0), new Point(10, 10), new Point(5, 8)},
            {new Point(0, 5), new Point(9, 0), new Point(10, 10)},
            {new Point(0, 5), new Point(6,0), new Point(10, 6), new Point(5,10)}};

    for(Point[] coords : tests) 
        System.out.println(maxY(coords) + " : " + Arrays.toString(coords));
}

输出：

(0, 10) : [(0, 10), (10, 0), (9, 5)]
(10, 10) : [(0, 0), (9, 5), (10, 10)]
(10, 10) : [(0, 0), (10, 10), (5, 8)]
(10, 10) : [(0, 5), (9, 0), (10, 10)]
(5, 10) : [(0, 5), (6, 0), (10, 6), (5, 10)]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接