# Minimal set of subintervals that 'covers' any subinterval in K subintervals

I have a big interval $$I = [a, b]$$ of size n.

I want an asymptotically minimal set of subintervals of $$I$$ (let's call it $$S$$) one can use to construct any subinterval of $$I$$, by concatenating at most $$K$$ subintervals - specifficaly I'm interested in $$K = 3, K=5$$ only, but general solution would be interesting too.

In other words, for any subinterval $$i$$ of $$I$$ I want to take at most $$K$$ (3, 5) elements of $$S$$ to get $$i$$. So if $$i = [2, 28]$$, one can take for example $$[2, 10], [10, 20], [20, 28]$$, if such subintervals exists in $$S$$ and $$K=3$$.

I've come up with solutions that are in $$O(n^2)$$ where $$n = |I|$$, but that is the same as naive approach of taking all the subintervals. I can get to about $$1/K$$ of that by having intervals of size $$m$$ to generate also the $$K$$ bigger intervals, but it seems it is in the spirit of the puzzle to have asymptotically better solution than $$O(n^2)$$, at least for $$K=5$$.

• Please credit the original source of the problem. – Apass.Jack Dec 18 '18 at 20:17

Let's consider the case $$K = 2$$. Given an interval $$[1,n]$$ of length $$n$$, we can construct the required set as follows:

• If $$n = 1$$, take the entire interval.
• Otherwise, let $$m = \lfloor n/2 \rfloor$$, and take the following intervals:
1. A solution for $$[1,m]$$.
2. A solution for $$[m+1,n]$$.
3. All intervals of the form $$[i,m]$$.
4. All intervals of the form $$[m,j]$$.

Denoting by $$A(n)$$ the number of intervals constructed in this way, we get the recurrence $$A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n,$$ with initial value $$A(1) = 1$$. The solution of this recurrence is $$A(n) = \Theta(n\log n)$$.

Now let us proceed to prove a matching lower bound. Let $$\ell_i = 2^i-1$$, and let $$I$$ be the maximum value such that $$\ell_i \leq n/2$$; note that $$I = \Theta(\log n)$$. For each $$1 \leq i \leq I$$, consider the $$n/2$$ intervals $$[1,\ell_i],\ldots,[n/2,n/2+\ell_i-1]$$ of length $$\ell_i$$. Each of these is the union of at most two intervals in $$S$$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $$2^{i-1} > \ell_{i-1}$$. In total, this gives a collection of $$n/2$$ intervals in $$S$$ of length between $$\ell_{i-1}+1$$ and $$\ell_i$$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $$n/2$$ intervals). This shows that $$S$$ must contain at least $$n/4$$ intervals of size between $$\ell_{i-1}+1$$ and $$\ell_i$$, and so $$\Omega(nI) = \Omega(n\log n)$$ overall.

Here is a better construction for $$K=4$$. Divide the interval $$[1,n]$$ into $$m=n/\log n$$ subintervals $$I_1,\ldots,I_m$$ of length $$\log n$$. We construct the required set as follows:

• Apply the construction recursively inside each $$I_i$$.
• Every prefix and suffix of each $$I_i$$, $$2n$$ intervals in total.
• The $$K=2$$ construction applied to $$[1,m]$$ and then blown up to $$I_1,\ldots,I_m$$ by replacing each interval $$[i,j]$$ to $$I_i,\ldots,I_j$$.

Let us first show that we can cover each interval $$I$$ using at most 4 intervals in the set. If $$I \subseteq I_i$$ for some $$i$$, then this is clear. Otherwise, suppose that $$I \subseteq I_i \cup \cdots \cup I_j$$, where $$i$$ is maximal and $$j$$ is minimal. So $$I$$ consists of a suffix of $$I_i$$, all the intervals $$I_{i+1},\ldots,I_{j-1}$$ (if any), and a prefix of $$I_j$$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $$B(n)$$ the number of intervals used in this construction. This quantity satisfies the recurrence $$B(n) = \frac{n}{\log n} B(\log n) + O(n).$$ Opening this up, we get $$B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots,$$ where the hidden constant is the same for all big O’s. The number of summands is $$\log^* n$$ (which is the number of $$\log$$s you have to apply to $$n$$ to reduce it below some constant), and so $$B(n) = O(n\log^* n).$$ We can repeat this construction once again, for $$K=6$$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $$O(n)$$ intervals for $$K=\omega(1)$$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.

• Lovely solution and proof! I got a bit stuck trying to interpret "Each of these is covered by at most two intervals in $S$" but in the end realised the right interpretation was "For each of these intervals $X$, there is a pair of intervals $Y, Z \in S$ such that $X=YZ$". – j_random_hacker Jan 18 at 16:44