1
$\begingroup$

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)$.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.