An efficient algorithm for computing the maximum empty rectangle in three dimensions
Given a set P of n points in three dimensions within a bounding hyper rectangle (BHR), the maximum empty hyper rectangle (MEHR) problem is to find a maximum volume or surface area hyper rectangle R within BHR such that R does not contain any point from the set P. We present an efficient algorithm for computing the MEHR. The worst and expected case time complexities of our algorithm are O(n3) and O(nlog4n), respectively. The worst and expected case space complexities of our algorithm are O(n2logn) and O(nlog3n), respectively. No previous algorithm was known for this problem.
three dimensions maximum empty hyper rectangle computational geometry space sweep paradigm segment-interval tree expected case complexity