Optimal Interval Partitionings for Range Minimum Queries (Bachelor thesis)

We developed a general notion of these data structure, called k-coverings, where the k stands for the maximal number of intervals we combine to answer each query. This allowed us to discover tight bounds for 2-, 3- and k-coverings with k ≥ 3. In this talk we will look at multiple k-covering data structures, derive upper bounds from them and
understand the proof for the tight bound Θ(n log(log n)) for 3-coverings.