Sum of k smallest values of affine functions Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f_i(x) = a_i x + b_i$ for $i \in N = \{1,\ldots,n\}$.

Consider some fixed value $k \in \{0,\ldots,n\}$. Let $S_k : \mathbb{R} \mapsto 2^N$ (power set) denote a function mapping some value $x \in \mathbb{R}$ to the set of indices of the $k$ smallest functions at $x$, so for all $x \in \mathbb{R}$, it holds that $|S_k(x)| = k$ and $f_i(x) \leq f_j(x)$ if $i \in S_k(x)$ and $j \notin S_k(x)$.

The question is: If we hold $f_1,\dots,f_n,k$ fixed and allow $x$ to vary, how many different sets can $S_k$ map to? In other words, which cardinality can the image of $S_k$ have?

For $k=0$ or $k=n$, there is only one possible set for all $x$ (either $\emptyset$ or $N$). Similarly, for $k=1$ or $k=n-1$, there are $n$ different sets each (since this is equal to the maximum or minimum element, which can change $n$ times while x increases).

But is there a general formula for arbitrary values of $k$? It seems that the maximum is attained at $k = \frac{n}{2}$.

Note that an upper bound is given by $O(n^2)$ since this is the maximum number of intersection points of the involved functions, which, thus, bounds the number of orderings. However, I think this bound is too rough. In computational experiments I have never seen a value of $2n$ or more.
I recently found out that my problem is known as the k-th level problem, which itself is equivalent to the k-set problem in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set_(geometry)