Planar Maximum Box Problem

摘要

Given two finite sets of points X~+ and X~- in R~d, the maximum box problem asks to find an axis-parallel box B such that B∩X~-= 0 and the total number of points from X~+ covered is maximized. In this paper we consider the version of the problem for d=2 (and find the smallest solution box). We present an O(n~3 log~4n) runtime algorithm, thus improving previously best known solution by almost quadratic factor.