Maximum Box Problem on Probabilistic Points

Abstract

Given disjoint finite point sets R and B in the plane, where the elements of R are colored red and the elements of B are colored blue, the maximum box problem asks for an axis-aligned rectangle (i.e. box) containing the maximum number of red points and no blue point. We consider this problem when the input is imprecise. That is, we consider that each point of R∪B has its own and independent probability of being present in the final random point set. We prove that, given any k ≥ 2, computing the probability that there exists a box containing at least k red points and no blue point is #P-hard, as well as the problem of computing the expectation of the maximum number of red points that can be covered with a box not containing any blue point. We complement these results with a polytime algorithm computing the probability that there exists a box containing exactly two red points, no blue point, and a given point of the plane.