求凸多边形的最大 y 坐标

Question

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

\n\n

已知V[1]是具有最小 x 坐标的顶点，并且顶点V[1,2,....,n]按逆时针顺序排列，如 \xef\xac\x81gure 中所示。还假定顶点的 x 坐标都是不同的，顶点的 y 坐标也是不同的。\n

\n\n

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

\n\n

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

\n\n

谢谢您的帮助！

\n

Answer 1

长版

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

顶点的分布可以以多种不同的方式变化。你可以有许多聚集在一个点附近，而一个在其他地方孤立，你可以有形成抛物线形状的顶点（以你的图表为例，消除顶点 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]

由于V[1]是局部最小值，案例 2 是一个很好、简单的案例。这意味着 处只能存在一个额外的局部最小值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 和情况 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]；否则，如果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)情况。