A (slightly) faster algorithm for klee's measure problem
Timothy M. Chan · 2008
Given n axis-parallel boxes in a fixed dimension d ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(nd/2 log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time nd/22O(log*n), where log* denotes the iterated logarithm.