A (slightly) faster algorithm for Klee's measure problem
type: Item
instance of: scholarly article
title: A (slightly) faster algorithm for Klee's measure problem
zbMATH Open document ID: 1180.65022
author: Timothy M. Chan
published in: Computational Geometry
publication date: 2009-11-16T00:00:00Z
review text: The paper describes a new improved algorithm for Klee's measure problem [\textit{V. Klee}, Am. Math. Monthly 84, 284--285 (1977; Zbl 1180.68163)]. Klee's measure problem comes under the standard problem in computational geometry and determinates how efficiently the measure of a union of \(n\) axis-parallel boxes in a fixed dimension \(d\) can be computed. The Klee's measure problem relates to other problems which are solved, and running time of the presented algorithms is improved, too. The first problem is computing the point depth in the arrangement of \(n\) axis-parallel boxes (the number of boxes containing the considered point) and the depth of the arrangement (the maximum depth over all points in the \(d\)-dimensional space). The second problem is the coverage problem (deciding whether the union of \(n\) axis-parallel boxes inside a fixed box covers this fixed box) which can be considered as a special case of both the measure and the depth problem.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65D17
zbMATH DE Number: 5633657
zbMATH Keywords: Klee's problem
zbMATH Keywords: union of boxes
zbMATH Keywords: volume
zbMATH Keywords: axis-parallel box
zbMATH Keywords: coverage problem
zbMATH Keywords: point depth
MaRDI profile type: Publication
full work available at URL: j.comgeo.2009.01.007
OpenAlex ID: W2022093184
cites work: Q3602886
cites work: Subquadratic algorithms for 3SUM
cites work: Voronoi diagrams in higher dimensions under certain polyhedral distance functions
cites work: On the parameterized complexity of \(d\)-dimensional point set pattern matching
cites work: Q3579411
cites work: Geometric applications of a randomized optimization technique
cites work: Semi-Online Maintenance of Geometric Optima and Measures
cites work: More algorithms for all-pairs shortest paths in weighted graphs
cites work: Geometric pattern matching in \(d\)-dimensional space
cites work: Static and Dynamic Algorithms for k-Point Clustering Problems
cites work: Q4028873
cites work: Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
cites work: Iterated nearest neighbors and finding minimal polytopes
cites work: Internet packet filter management and rectangle geometry
cites work: Lower bounds for dynamic algebraic problems
cites work: On the complexity of computing the measure of ∪[a i ,b i ]
cites work: Efficient algorithms for shared camera control
cites work: Q2934665
cites work: Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
cites work: The measure problem for rectangular ranges in d-space
cites work: Efficient partition trees
cites work: Reporting points in halfspaces
cites work: Range searching with efficient hierarchical cuttings
cites work: Q3688439
cites work: New Upper Bounds in Klee’s Measure Problem
cites work: On Dynamic Algorithms for Algebraic Problems
DOI: 10.1016/J.COMGEO.2009.01.007
description: scientific article; zbMATH DE number 5633657