Abstract: Given a set of n points, inside a bounding box, in a d-dimensional
Euclidean space, we seek to find the largest volume empty axis parallel cube.
We also consider a bichromatic variant of this problem. Given a set of
n red points and a set of n blue points in a d-dimensional Euclidean space,
find an axis parallel cube that contains as many blue points as possible, but
no red points. Combining our results with previous work we now have
near linear time algorithms for both problems in two dimensions, polynomial time
sweep-plane algorithms in any fixed dimensions, and we know that both problems
are NP-complete if the dimension d is part of the input.

This is joint work with Jonathan Backer