Description
A hyper-rectangle is commonly used as a bounding predicate in tree-based access methods in databases. To reduce the number of I/O's per query, we would like to reduce the volume of this bounding predicate by cutting chunks out of the corners of the bounding hyper-rectangle. Ideally, one would like to remove the largest hyper-rectangular chunk that does not contain any points. In this paper, we formalize the problem and then show that the problem of finding the largest possible chunk is NP-complete. We accomplish this through a reduction from 3-SAT to our problem.