The characteristic bisection method is an algorithm for finding approximate zeros of multi-dimensional functions. It is a generalization of the bisection method; it is described briefly here.
Apparently, the method first appeared in this paper by Vrahatis and Iordanidis. In Lemma 4.7 in that paper, the authors prove that the number of iterations required for an $\epsilon$-approximation is at least $\lceil \log_2(\Delta/\varepsilon) \rceil$, where $\Delta$ is the diameter of the initial polyhedron. The proof also seems to prove only a lower bound - since there are iterations in which the polyhedron does not change at all.
However, in later papers, such as this paper by Vrahatis, it is claimed (in Theorem 5) that the number of required iterations is exactly $\lceil \log_2(\Delta/\varepsilon) \rceil$.
I did not find a proof of an upper bound, but maybe it is there and I just missed it. QUESTION: what is the actual run-time complexity of this "characteristic bisection" method?
