Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414321 | Computational Geometry | 2012 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Karl Bringmann,