View publication
| Title | Computing the Depth Distribution of a Set of Boxes |
| Authors | Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma |
| Publication date | June 2021 |
| Abstract |
Motivated by the analysis of range queries in databases, we introduce the computation of the depth distribution of a set B of n d-dimensional boxes (i.e., axis aligned d-dimensional hyperrectangles), which generalizes the computation of the Klee's measure and maximum depth of B. We present an algorithm to compute the depth distribution running in time within O(n^{(d+1)/2} log n), using space within O(n log n), and refine these upper bound for various measures of difficulty of the input instances. Moreover, we introduce conditional lower bounds for this problem which not only provide insights on how fast the depth distribution can be computed, but also clarify the relation between the Depth Distribution problem and other fundamental problems in computer science. |
| Downloaded | 14 times |
| Pages | 69-82 |
| Volume | 883 |
| Journal name | Theoretical Computer Science |
| Publisher | Elsevier Science (Amsterdam, The Netherlands) |
|
|
| Reference URL |
|