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

DOI10.1016/j.comgeo.2011.12.001zbMath1375.52006OpenAlexW2055560312MaRDI QIDQ419375

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

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) Data structures (68P05)

Related Items (4)

Faster algorithms for largest empty rectangles and boxes ⋮ Efficient transformations for Klee's measure problem in the streaming model ⋮ Speeding up many-objective optimization by Monte Carlo approximations ⋮ Computing the depth distribution of a set of boxes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A (slightly) faster algorithm for Klee's measure problem
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• 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?]
• Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
• 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
• An improved algorithm for computing the volume of the union of cubes

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