A (slightly) faster algorithm for Klee's measure problem

DOI10.1016/j.comgeo.2009.01.007zbMath1180.65022OpenAlexW2022093184MaRDI QIDQ1037647

Timothy M. Chan

Publication date: 16 November 2009

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

volumeKlee's problemcoverage problemaxis-parallel boxpoint depthunion of boxes

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer-aided design (modeling of curves and surfaces) (65D17)

Related Items (9)

Klee's measure problem made oblivious ⋮ An improved algorithm for Klee's measure problem on fat boxes ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ Efficient transformations for Klee's measure problem in the streaming model ⋮ Maximum-weight planar boxes in \(O(n^2)\) time (and better) ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Unnamed Item ⋮ Computing Klee's measure of grounded boxes ⋮ Calculation of Discrepancy Measures and Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• Reporting points in halfspaces
• Efficient partition trees
• Geometric pattern matching in \(d\)-dimensional space
• Iterated nearest neighbors and finding minimal polytopes
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Geometric applications of a randomized optimization technique
• Lower bounds for dynamic algebraic problems
• Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
• On the parameterized complexity of \(d\)-dimensional point set pattern matching
• Subquadratic algorithms for 3SUM
• On Dynamic Algorithms for Algebraic Problems
• Can the Measure of ∪ n 1 [ a i , b i be Computed in Less Than O(n logn) Steps?]
• More algorithms for all-pairs shortest paths in weighted graphs
• The measure problem for rectangular ranges in d-space
• 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
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Efficient algorithms for shared camera control

This page was built for publication: A (slightly) faster algorithm for Klee's measure problem