2015/05/12 by Jérémy Barbay, Barbay, Jérémy, Pablo Pérez-Lantero +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1505.02855
openalex publication_date 2015/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The KLEE'S MESURE of n axis-parallel boxes in ℝd is the volume of their union. It can be computed in time within O(nd/2) in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size h, and yields a solution running in time within O(nlog2d-2h+ hd/2) ⊆ O(nd/2). The second technique takes advantage of instances where no d-dimensional axis-aligned hyperplane intersects more than k boxes in some dimension, and yields a solution running in time within O(n log n + n k(d-2)/2) ⊆ O(nd/2). The third technique takes advantage of instances where the intersection graph of the input has small treewidth ω. It yields an algorithm running in time within O(n4ωlog ω+ n (ωlog ω)d/2) in general, and in time within O(n log n + n ωd/2) if an optimal tree decomposition of the intersection graph is given. We show how to combine these techniques in an algorithm which takes advantage of all three configurations.