###
Adaptive Techniques to find Optimal Planar Boxes.

####
Jérémy Barbay, Gonzalo Navarro, and Pablo Pérez-Lantero

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 intersection 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(A1),* *f(A2))* for every subset
*A subset-or-equal P* and every partition *{A1,A2}* 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 MCS
Splay tree data structure supporting insertions and deletions
with the dynamic finger property, improving upon previous
results [Cortés et al., J.Alg. 2009].