Looking for algorithm (or at least name) for this optimization problem

Question

Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$.

Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$

The problem is, given some arbitrary target $\Delta_0$, to find $s^*$ such that $\Delta(s^*) = \Delta_0$. (NB: There may be no such $s^*$. For example, $n = 2$, and $t_0 = (0, -1, 0), t_1 = (0, 0, 1)$, then $\Delta(s)$ has constant value $2$, so the problem has a solution, infinitely many in fact, only if $\Delta_0 = 2$.)

I'm looking for an algorithm to solve this problem, or at least some search terms (keywords, author names, etc) that I may try when searching online for such an algorithm.

FWIW, for the special case I'm working with, the following additional conditions/considerations apply:

1. $x_0 < x_1$;
2. $l_0 = r_0 = l_1 = r_1 = 0$;
3. $l_i < r_i, \forall \, i > 1$;
4. only positive solutions $s^*$ are of interest;
5. $\Delta_0 \geq \max_{i,j} (r_j - l_i)$.

Answer 1

If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s > 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \Delta_0$ (namely $s = (\Delta_0 - \beta_k)/\alpha_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha_l + \beta_l \leq \Delta_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.