  Given a set $P$ of $n$ planar points, two axes and a real-valued score
function $f()$ on subsets of $P$, the Optimal Planar Box problem consists in
finding a box (i.e. axis-aligned rectangle) $H$ maximizing $f(H\cap P)$. We
consider the case where $f()$ is monotone decomposable, i.e. there exists a
composition function $g()$ monotone in its two arguments such that
$f(A)=g(f(A_1),f(A_2))$ for every subset $A\subseteq P$ and every partition
$\{A_1,A_2\}$ of $A$. In this context we propose a solution for the Optimal
Planar Box problem which performs in the worst case $O(n^2\lg n)$ score
compositions and coordinate comparisons, and much less on other classes of
instances defined by various measures of difficulty. A side result of its own
interest is a fully dynamic \textit{MCS Splay tree} data structure supporting
insertions and deletions with the \emph{dynamic finger} property, improving
upon previous results [Cort\'es et al., J.Alg. 2009].
