Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?

DOI10.2307/2318871zbMath1180.68163OpenAlexW2327699610MaRDI QIDQ3405831

Victor Klee

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical measure theory (28A99)

Related Items (15)

An in-place algorithm for Klee's measure problem in two dimensions ⋮ Approximate counting in SMT and value estimation for probabilistic programs ⋮ 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 ⋮ Efficient transformations for Klee's measure problem in the streaming model ⋮ Ectropy of diversity measures for populations in Euclidean space ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Efficient covariance matrix update for variable metric evolution strategies ⋮ Computing the depth distribution of a set of boxes ⋮ Unnamed Item ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Online algorithms for the maximum \(k\)-interval coverage problem ⋮ Computing Klee's measure of grounded boxes ⋮ Calculation of Discrepancy Measures and Applications

This page was built for publication: Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?