# Algorithm to find largest hypercube that excludes a given set of "intruding" points

I have a (unit) hypercube containing several points. I want to partition it, and take "slices" (also hypercubes) off it until all these previously contained points are outside the resulting final hypercube. I want to end up with the hypercube that retains the greatest volume compared to the original hypercube.

I'm looking for an algorithm that will achieve this... and finding nothing. I wonder if I were to take each point in turn, consider the hyperplane partitions I could make through that point, select the one which "shaves" the least amount of volume from the hypercube, and repeat for all points... would that be guaranteed to yield the result I seek?

• Do the edges of the hypercube align with (parallel) the coordinate axes? Sep 10, 2015 at 1:53
• Yes - and you can normalise the hypercube any way you like to make all coordinate axes have equal weighting - it need not strictly be a unit hypercube. Sep 10, 2015 at 1:56
• P.S. I've convinced myself that my proposed algorithm does not always yield the result I seek, but elegant proofs are welcome, and pointers to algorithms that do work are even more appreciated. Sep 10, 2015 at 1:57
• Even in dimension 2 this is not trivial. See en.wikipedia.org/wiki/Largest_empty_rectangle.
– lhf
Sep 10, 2015 at 2:39
• Thanks for that reference. I realised that if one draws a line from three-quarters of the way up the left edge of a square to halfway along the top edge of the square, then it is possible to select a set of points on this line in order from left to right such that one always takes slices off the left side of the square... and ends up with as little as half the square. However, visiting the points in reverse order always slices off the top of the square and leaves three-quarters of the square remaining. In the absence of general solutions, I'm exploring heuristics to give an acceptable result. Sep 10, 2015 at 5:11