Article ID Journal Published Year Pages File Type
414321 Computational Geometry 2012 9 Pages PDF
Abstract

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 O(n(d+2)/3)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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,