Adaptive Techniques to find Optimal Planar Boxes

Details Adaptive Techniques to find Optimal Planar Boxes Adaptive Techniques to find Optimal Planar Boxes

2012-04-10

arxiv.org/abs/1204.2034v1

Computer Science

Computational Geometry

18 pages, 4 figures

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Adaptive Techniques to find Optimal Planar Boxes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Techniques to find Optimal Planar Boxes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Techniques to find Optimal Planar Boxes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-644206