Improved Algorithm for Computing the Maximum-volume Bichromatic Separating Box

Abstract

We consider the problem of computing the largest-area bichromatic separating box among a set of $n$ red points and a set of $m$ blue points in three dimensions. Currently, the best-known algorithm to solve this problem takes $O(m^2(m+n))$ time and $O(m+n)$ space. In this paper, we come up with an improved algorithm for the problem, which takes $O(m^2+n)$ time.

18 pages, 14 figures

References in corpus (1)

• Finding the Maximal Empty Rectangle Containing a Query Point