On the minimum total length of interval systems expressing all intervals, and range-restricted queries

Abstract

In this paper, we study the classical one-dimensional range-searching problem, i.e., expressing any interval {i, .... j} subset of {1, ..., n} as a disjoint union of at most k intervals in a system of intervals, though with a different lens: we are interested in the minimum total length of the intervals in such a system (and not their number, as is the concern traditionally). We show that the minimum total length of a system of intervals in {1, ..., n} that allows to express any interval as a disjoint union of at most k intervals of the system is Theta(n(1+2/k)) for any fixed k. We also prove that the minimum number of intervals k = k(n, c), for which there exists a system of intervals of total length cn with that property, satisfies k(n, c) = Theta(n(1/c)) for any integer c >= 1. We also discuss the situation when k = Theta(log n). (c) 2008 Elsevier B.V. All rights reserved.