In search of the Giant Convex Quadrilateral hidden in the Mountains

A $1.5$D terrain is a simple polygon bounded by a line segment $\mathrm{\ell }$ and a polygonal chain monotone with respect to the line segment $\mathrm{\ell }$. Usually, $\mathrm{\ell }$ is chosen aligned to the $x$-axis, and is called the base of the terrain. In this paper, we consider the problem of finding a convex quadrilateral of largest area inside a $1.5$D terrain in ${\mathbb{R}}^2$. We present an $O(n^2)$ time algorithm for this problem, where $n$ is the number of vertices of the terrain. Finally, we show that the largest area axis-parallel rectangle inside the terrain yields a $\frac{1}{2}$-approximation result to the largest convex quadrilateral problem.