Finding a Largest-Area Triangle in a Terrain in Near-Linear Time

Sergio Cabello, Arun Kumar Das, Sandip Das +1

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, w…