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].