An improved algorithm for Kleeʼs measure problem on fat boxes

AbstractThe measure problem of Klee asks for the volume of the union of n axis-parallel boxes in a fixed dimension d. We give an O(n(d+2)/3) time algorithm for the special case of all boxes being cubes or, more generally, fat boxes. Previously, the fastest run-time was nd/22O(log⁎n), achieved by the general case algorithm of Chan [SoCG 2008]. For the general problem our run-time would imply a breakthrough for the k-clique problem