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

Question

我有一个数组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坐标吗？

谢谢您的帮助！

Answer 1

长版

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

顶点的分布可以多种不同方式变化。您可以在一个点附近有许多聚类，而在另一点处一个孤立，您可以拥有形成抛物线形状的顶点（以图表为例，消除顶点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的所有其他情况，我们必须执行二进制搜索，但是要考虑两种可能的情况：


V[2]的y坐标小于V[1]。
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]的y坐标大于V[n-1]，则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]与V[i-1]和V[i+1]进行比较）。


这样可以使您安全地收敛到最右边的局部最大值，并在log(n)时间内隔离该值。

现在，我们已经介绍了V[1].y < V[n].y的两种不同情况，让我们注意，这种受约束的二进制搜索将在情况2中与在情况1中一样准确地工作。因此，我们可以对情况1和情况进行概括两种情况都遵循约束二分法搜索的规则。这显着降低了算法复杂度。

总之，对于任何一般情况，只要有几个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]方向收敛；否则，如果V[i].y < v[i-1].y，则朝V[1]方向收敛；否则V[i].y为最大值。


对于V[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)案例。