Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
From MaRDI portal
Publication:3405831
DOI10.2307/2318871zbMath1180.68163MaRDI QIDQ3405831
Publication date: 11 February 2010
Published in: The American Mathematical Monthly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2318871
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
28A99: Classical measure theory
Related Items
Unnamed Item, Calculation of Discrepancy Measures and Applications, Klee's measure problem made oblivious, Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, An improved algorithm for Klee's measure problem on fat boxes, Ectropy of diversity measures for populations in Euclidean space, An in-place algorithm for Klee's measure problem in two dimensions, Efficient transformations for Klee's measure problem in the streaming model, Approximating the volume of unions and intersections of high-dimensional geometric objects, Efficient covariance matrix update for variable metric evolution strategies, A (slightly) faster algorithm for Klee's measure problem, Approximate counting in SMT and value estimation for probabilistic programs, Computing the depth distribution of a set of boxes, Online algorithms for the maximum \(k\)-interval coverage problem, Computing Klee's measure of grounded boxes