A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(n \log n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.
翻译:地形是一个$x$-单调多边形,其下边界是一条单独的线段。我们提出了一种算法,可以在$O(n \log n)$的时间内在地形中找到最大面积的三角形,其中$n$是定义地形的顶点数。这个问题的先前最佳算法的运行时间为$O(n^2)$。