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

DOI10.1016/j.comgeo.2009.01.007zbMath1180.65022MaRDI 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

volume; Klee's problem; coverage problem; axis-parallel box; point depth; union of boxes

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

65D17: Computer-aided design (modeling of curves and surfaces)

Related Items

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

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