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.

  • $\begingroup$ Thanks for the remark, I tried to formulate the question and the assumptions in a clearer way. In a broad sense, the problem is motivated by a variant of the Knapsack problem, but I fear I cannot go much into detail here. $\endgroup$ Feb 3 '17 at 19:08
  • $\begingroup$ One thought on how you could explore this further yourself: fix $k=2$, and compute the number for small values of $n$ (e.g., $n=1,2,3,\dots,10$) by writing a program to search all possibilities, and show in the question what numbers you've come up with (and check OEIS). $\endgroup$
    – D.W.
    Feb 3 '17 at 21:32
  • $\begingroup$ If we only consider the case of $f_i$'s in general position (no two are parallel, and no three intersect), then there is an alternative formulation in terms of permutations. Starting with the inverse permutation $n\;n-1\;\cdots\;1$, sort it by repeatedly transposing adjacent elements which are in the wrong order. Consider the first $k$ elements throughout this process. How many different sets can you see? $\endgroup$ Mar 9 '17 at 11:48
  • $\begingroup$ @D.W. Brute force is only feasible up to $n=6$ or $n=7$, see oeis.org/A005118. $\endgroup$ Mar 9 '17 at 11:57

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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.