An improved algorithm for Klee's measure problem on fat boxes

DOI10.1016/J.COMGEO.2011.12.001zbMATH Open1375.52006OpenAlexW2055560312MaRDI QIDQ419375FDOQ419375

Authors Karl Bringmann

Publication date 18 May 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2011.12.001

zbMATH Keywords

geometric data structuresunion of cubes

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Spherical and hyperbolic convexity (52A55)

Recommendations

• Klee's measure problem on fat boxes in time \(\partial(n^{(d+2)/3})\)
• A (slightly) faster algorithm for Klee's measure problem
• Computing Klee's measure of grounded boxes
• scientific article; zbMATH DE number 1302378
• An in-place algorithm for Klee's measure problem in two dimensions

Cites work

• scientific article; zbMATH DE number 6381708 (Why is no real title available?)
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• A (slightly) faster algorithm for Klee's measure problem
• An improved algorithm for computing the volume of the union of cubes
• Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
• Computing the volume of the union of cubes
• New Upper Bounds in Klee’s Measure Problem
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Semi-Online Maintenance of Geometric Optima and Measures
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions

Cited in

(10)

• Speeding up many-objective optimization by Monte Carlo approximations
• Klee's measure problem on fat boxes in time \(\partial(n^{(d+2)/3})\)
• Faster algorithms for largest empty rectangles and boxes
• Efficient transformations for Klee's measure problem in the streaming model
• Computing Klee's measure of grounded boxes
• On Klee's measure problem for grounded boxes
• A (slightly) faster algorithm for Klee's measure problem
• An in-place algorithm for Klee's measure problem in two dimensions
• Bringing order to special cases of Klee's measure problem
• Computing the depth distribution of a set of boxes

This page was built for publication: An improved algorithm for Klee's measure problem on fat boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q419375)