A (slightly) faster algorithm for Klee's measure problem (Q1037647): Difference between revisions

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.