4

我有一个数组V[1,2,....,n]，其中数组的每个元素以坐标对 (x,y) 的形式表示凸多边形的一个顶点。

给定V[1]是具有最小 x 坐标的顶点，并且顶点V[1,2,....,n]按逆时针方向排列，如图所示。还假设顶点的 x 坐标都是不同的，顶点的 y 坐标也是如此。 在此处输入图像描述

现在，我想找到具有最大 y 坐标值的顶点。我们都知道朴素的 O(n) 方法，但是有可能在 O(log(n)) 中找到它吗？

我使用V[1]具有最小 x 坐标的顶点的信息在 O(log(n)) 时间内找到具有最大 x 坐标的顶点。但是有可能做到最大y坐标吗？

谢谢您的帮助！

4

4 回答 4

2

长版

二进制搜索在这里的一些地方被认为是解决方案，但它仅适用于某些情况。

顶点的分布可以以多种不同的方式变化。您可以在一个点附近聚集许多，而在其他地方隔离一个，您可以有形成抛物线形状的顶点（以您的图表为例，消除顶点 7、8 和 9），您可以有类似对数的分布（例如只有顶点 1、2、3 和 4），或者实际上是任何其他数量的可能性。在所有这些不同的情况下，您将有不同的局部最大值和最小值的数量和位移。

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

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

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

观察 的行为V[n]。如果V[n]y 坐标V[n].y小于V[1], 或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]where n-k > 1。为了帮助可视化，如果您绘制函数 的点f(i) = V[i].y，您将看到抛物线形状或正弦形状。因此，第二个局部最大值V[n-k]将是抛物线的最右端，或者是正弦曲线的峰值。

（注意：本段是一个可选的优化步骤。）让我们考虑如何确定我们正在处理哪种类型的局部最大值：如果V[n]y 坐标大于V[n-1]，则V[n]必须是第二个局部最大值（再次考虑为什么会这样一定是真的），事实上我们可以立即确定它V[n]具有最大的 y 坐标。否则，存在一些 kV[n-k]是我们的局部最大值，这意味着我们需要执行搜索。

现在我们只需要考虑如何进行搜索，以避免无意中收敛V[1]（我们需要找到一个局部最大值，因为这V[1]是一个局部最大值，我们可能会不小心收敛到它上面）。

使用以下约束执行二进制搜索：

  • 对于一个给定的V[i]，如果V[i].y < V[1].y然后收敛于V[n]。
  • 如果V[i].y > V[1].ythen 收敛于 y 增加的方向（只需比较V[i]和V[i-1]）V[i+1]。

这应该允许您安全地收敛到最右边的局部最大值并在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[n].y。这种二分搜索必须遵守以下约束，给定一个任意的V[i]：

  • 基本情况：如果V[1].y > V[i].y，收敛于 的方向V[n]。
  • 标准情况：如果V[i].y < V[i+1].y，收敛于V[n]；else if V[i].y < v[i-1].y，收敛于V[1]; 否则V[i].y是最大值。

还有一个可选的优化，可以针对 whereV[1].y < V[n].y和的边缘情况执行V[n].y > V[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)案例。

于 2018-09-10T04:41:35.970 回答
1

You can find the extreme point in any direction using a binary search as described here.

The essential idea is to examine the vector at the end points and the midpoint and use this to determine which part to expand.

于 2018-09-09T21:18:09.757 回答
1

因为多边形是凸的，所以当你移动时，连续点之间的向量角度从 270 度（向下。称为 -90 度）到 0（右）、90（上）、180（左）等单调增加从多边形周围的一个点到下一个点。

因此，您可以通过二进制搜索找到大于 180 度的最小角度。到下一个点的向量变为 > 180 度（在您的示例中为 V[8]）的点是多边形从向上或向左转向向下的位置，并且该点必须具有最大的 Y 坐标。

我认为彼得链接到的文章说了同样的话，但是对于这样一个简单的想法来说，要读很多话。

于 2018-09-09T23:32:42.680 回答
0

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

要考虑的最简单的情况是m=1，何时V[2].y < V[1].y > v[n].y。由于排除这种情况使后续推理更简单，我们假设对这种情况进行了初始检查。

考虑一条以 V[i] 为原点的边 E[i]，其中1<i<=n. 鉴于所有 x 和 y 坐标都不同的约束，E[i] 必须位于 4 个平面象限之一中：

在此处输入图像描述

鉴于我们已经排除了 的情况m=i=1，对于位于象限 I、II 或 IV 中的 E[i]，它必须是 的情况m>i。如果 E[i] 位于象限 III 中，则为 ，如果或m=i，则为真。V[i].y > V[i-1].ym<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)]
于 2018-09-10T06:48:38.777 回答