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 $\ell$ and a polygonal chain monotone with respect to the line segment $\ell$. Usually, $\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 maximum area inside a $1.5$D terrain in $I\!\!R^2$. We present an $O(n^2\log n)$ time algorithm for this problem, where $n$ is the number of vertices of the terrain. Finally, we show that the maximum area axis-parallel rectangle inside the terrain yields a $\frac{1}{2}$ factor approximation result to the maximum area convex quadrilateral problem.