2017/05/29 by Jérémy Barbay, Barbay, Jérémy, Pablo Pérez-Lantero +3
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #F.2.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1705.10022
openalex publication_date 2017/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the analysis of range queries in databases, we introduce the computation of the Depth Distribution of a set B of axis aligned boxes, whose computation generalizes that of the Klee's Measure and of the Maximum Depth. In the worst case over instances of fixed input size n, we describe an algorithm of complexity within O(n^(d+1)/(2)log n), using space within O(nlog n), mixing two techniques previously used to compute the Klee's Measure. We refine this result and previous results on the Klee's Measure and the Maximum Depth for various measures of difficulty of the input, such as the profile of the input and the degeneracy of the intersection graph formed by the boxes.