Parametric search

In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique invented by Nimrod Megiddo (1983) for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an optimization algorithm (find the best solution). It is frequently used for solving optimization problems in computational geometry.

The basic idea of parametric search is to simulate a test algorithm that takes as input a numerical parameter ${\displaystyle X}$, as if it were being run with the (unknown) optimal solution value ${\displaystyle X^{*}}$ as its input. This test algorithm is assumed to behave discontinuously when ${\displaystyle X=X^{*}}$, and to operate on its parameter ${\displaystyle X}$ only by simple comparisons of ${\displaystyle X}$ with other computed values, or by testing the sign of low-degree polynomial functions of ${\displaystyle X}$. To simulate the algorithm, each of these comparisons or tests needs to be simulated, even though the ${\displaystyle X}$ of the simulated algorithm is unknown. To simulate each comparison, the parametric search applies a second algorithm, a decision algorithm, that takes as input another numerical parameter ${\displaystyle Y}$, and that determines whether ${\displaystyle Y}$ is above, below, or equal to the optimal solution value ${\displaystyle X^{*}}$.

...
Wikipedia