Complexity of computing topological degree of Lipschitz functions in n dimensions (Q578854)

From authors' summary: We find lower and upper bounds on the complexity, comp, of computing the topological degree of functions defined on the n- dimensional unit cube \(C^ n\), \(f: C^ n\to R^ n\), \(n\geq 2\), which satisfy a Lipschitz condition with constant K and whose infinity norm at each point on the boundary of \(C^ n\) is at least d, \(d>0\), and such that K/8d\(\geq 1\). A lower bound, \(comp_{low}\simeq 2n(K/8d)^{n- 1}(c+n)\) is obtained for comp, assuming that each function evaluation costs c and elementary arithmetic operations and comparisons cost unity. We prove that the topological degree can be computed using \(([K/2d+1]+1)^ n-([K/2d+1]-1)^ n\) function evaluations. It can be done by an algorithm due to Kearfott.