Klee's measure problem on fat boxes in time ∂( n ( d +2)/3 )
Karl Bringmann · 2010
The measure problem of Klee asks for the volume of the union of n axis-parallel boxes in a fixed dimension d. We give an ∂(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/2 2∂(log*n), achieved by the general case algorithm of Chan [SoCG 2008]. For the general problem our run-time would imply a complexity theoretic breakthrough for the k-clique problem and can thus be considered extremely unlikely.