# Given a finite set of points, does there exist a linear function pass through a point and strictly below the other points for all the points?

I guess my question is a follow up question of this one: usul, Existence of a strictly convex function interpolating given gradients and values, version: 2019-04-13.

In usul's question, the answer proves the existence of such a convex function. I think the assumption the question has - "For each point, we are given a linear function through it and strictly below the others" is very interesting. It's not difficult for us to construct such a convex function if the assumption is true. However, I am more interested in what conditions could make the assumption to be true?

In other words, I think my question is: suppose we are given a finite set $$C$$ with cardinality $$T$$ of pairs $$(x,y) \in C$$, with $$x \in \mathbb{R}^d$$ and $$y \in \mathbb{R}$$, under what conditions of $$X = \{x_1, \dotsc, x_T\}$$ and $$Y = \{y_1, \dotsc, y_T\}$$, can we construct $$T$$ linear functions $$L =\{l_1, \dotsc, l_T\}$$ such that each linear function $$l_i$$ passes through $$(x_i, y_i)$$ and is strictly below other points?

The mathematical formula for the above question may be written as the following: let each linear function $$l_i = k_i(x - x_i) + y_i$$, then the above question is to decide whether there exist a sequence of $$K = \{k_1, \dotsc, k_T\}$$ such that $$l_i(x_i) > l_j(x_i)$$, i.e., $$y_i > k_j(x_i - x_j) + y_j \,\, \forall i\neq j.$$ Then I think the question is to decide the existence of such a sequence of $$K$$ which I am not sure about the answer. Also, I don't know if the above mathematical representation is the best way to solve this problem. Feel free to come up with your own method if my initial thinking doesn't work.

Updated: an image from usul's question so this question could be more intuitive: • Maybe I don't understand the question ... isn't the condition just that each point should lie below the line joining the two points to either side of it? Apr 14, 2020 at 21:09
• MathJax supports links, so I combined the separate text-and-URLs into a single link. Since you were concerned with pointing to a specific revision, I linked that, too. Also, the problem has two answers; I picked the one that seemed more likely and linked that. I hope that all this is agreeable. Apr 14, 2020 at 22:19
• Nik's understanding is correct, but my question is what kind of sequences of $X$ and $Y$ can make this condition (i.e. each point should lie below the line joining the two points to either side of it) be satisfied? For example, give some points $\{(0,1), (1,0), (2,1)\}$ (i.e. $f(x) = (x-1)^2$), we know we can construct 3 linear functions as desired. However, if we are given a set of $\{(0,-1), (1, 0), (2, -1)\}$ then we can't construct such linear functions. Therefore, my question is: if we are given a set of points, can we construct such linear functions? Apr 15, 2020 at 2:37
• To be more specific, my question is like the following: given variable sequence $\{ x_t \}_{t \in [T]}$ and function value sequence $\{ y_t \}_{t \in [T]}$, when would it be possible to find a concave function $u$ such that $u(x_t) = y_t$. Apr 15, 2020 at 3:22
• I think another problem here is that my $x$ is in $d$ dimension. Therefore, we don't have such kind of "neighboring relationship from Nik's comment" for the points, i.e. we don't have an ordering for the $\{x_t\}_{t\in T}$ so we don't have neighboring points for each point. Apr 20, 2020 at 20:39