3D Rectangulations and Geometric Matrix Multiplication
The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case in which P is a 3D histogram. It runs in O(m log m) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n x n matrices A and B with nonnegative integer