On the complexity of computing the measure of ∪[a i ,b i ]

DOI10.1145/359545.359553zbMath0378.68032DBLPjournals/cacm/FredmanW78OpenAlexW2077449861WikidataQ29400574 ScholiaQ29400574MaRDI QIDQ4157950

Bruce W. Weide, Michael L. Fredman

Publication date: 1978

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/359545.359553

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Real- or complex-valued set functions (28A10) Algorithms in computer science (68W99)

Related Items (27)

Periodic assignment and graph colouring ⋮ Approximate map labeling is in \(\Omega (n\log n)\) ⋮ An in-place algorithm for Klee's measure problem in two dimensions ⋮ Geometric complexity of some location problems ⋮ On optimal cuts of hyperrectangles ⋮ On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination ⋮ Klee's measure problem made oblivious ⋮ An improved algorithm for Klee's measure problem on fat boxes ⋮ Efficient transformations for Klee's measure problem in the streaming model ⋮ On the complexity of finding the convex hull of a set of points ⋮ An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals ⋮ Comparisons between linear functions can help ⋮ On the computational complexity of (maximum) class scheduling ⋮ The inequality-satisfiability problem ⋮ Parallel computational geometry of rectangles ⋮ An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model ⋮ On the computational complexity of (maximum) shift class scheduling ⋮ Visibility maps of segments and triangles in 3D ⋮ License class design: Complexity and algorithms ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Minimum node disjoint path covering for circular-arc graphs ⋮ Computing the depth distribution of a set of boxes ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ An O(n log n) Manhattan path algorithm ⋮ Calculation of Discrepancy Measures and Applications ⋮ Lower bounds on probabilistic linear decision trees

This page was built for publication: On the complexity of computing the measure of ∪[a _i ,b _i ]