View publication
| Title | Adaptive Techniques to find Optimal Planar Boxes |
| Authors | Jérémy Barbay, Gonzalo Navarro, Pablo Pérez-Lantero |
| Publication date | 2012 |
| Abstract | 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. an 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 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]. |
| Downloaded | 4 times |
| Pages | 79-84 |
| Conference name | Canadian Conference on Computational Geometry |
|
|
| Reference URL |
|