Minimal number of function evaluations for computing topological degree in two dimensions

Sikorski, Krzysztof A.

A lower bound n-min roughly equal log-2 (diam(T)/m) is established for the minimal number of function evaluations necessary to compute the topological degree of every function f in a class F. The class F consists of continuous functions f = (f1, f2) defined on a triangle T, f: T → R squared, such that the minimal distance between zeros of f1 and zeros of f2 on the boundary of T is not less than m, m > 0. Information is exhibited which permits the computation of the degree for every f in F with at most 2n-min function evaluations. An algorithm, due to Kearfott, uses this information to compute the degree. These results lead to tight lower and upper complexity bounds for this problem.


More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-093-84
Published Here
October 26, 2011